Posted on

缓冲区总是有大小限制的，当我们写一个日志 API 时，往往隐藏了这种细节，而用户可能偶尔会遇到日志被默默截断的情况。

而当开发者输出一堆 id 并且截断点正好在分隔符上时，就会造成极大的困扰了。

因此日志库不妨在截断时，将最后几个字符改成... 或者 <truncated>

Posted on | Edited on

range 的常见流程

  1. 客户端发起 get，不带 range
  2. 服务器返回内容，带有 Accept-Ranges: bytes
  3. 客户端知晓服务端支持 range，可使能当前任务的暂停功能，继续时使用 range 跳过已下载部分
  4. 若客户端带有 Range: bytes=0-100 则服务端带有 Content-Range: bytes 0-100/100000

http range 请求，是 http 的可选实现功能，服务器/客户端均可不实现此功能。

http range 目的是实现断点续传，并非用于随机访问的场景，也有基于 http range 构造的 DoS 攻击，原理是构造跨度较大的 http range 请求以提高服务器准备数据的代价，http 服务器应防备这一点，对不合理的 range 请求进行拒绝，不过这可能误伤部分所谓的多线程下载软件，这些软件往往可选的使用多个 TCP 连接同时下载文件的不同部分。

部分防火墙屏蔽下载的原理是识别并拒绝Range: bytes=n-x的 http 请求

Posted on | Edited on

题目

Given a string, find the length of the longest substring without repeating characters.

求给定字符串中，不包含重复字符的最长字字符串的长度

此题与 LeetCode#2 Add Two Numbers 一样属于串的算法。解法也类似，使用 map 保存过去的值，对原字符串只遍历一次。关键点在于发现重复字符时回退的计算、index 记录的擦除。

代码

这里给出 golang 的最优解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func lengthOfLongestSubstring(s string) int {
    m := make(map[byte]int)
    current := 0
    count := 0
    for i := 0; i != len(s); {
        c := s[i]
        if _, ok := m[c]; !ok {
            m[c] = i
            current++
            if (current > count) {
                count = current
            }
            i++
        } else {
            end := m[c]
            m[c] = i
            start := i - current
            
            fmt.Println(start, end)
            for j:= start; j < end; j++ {
                delete(m, s[j])
            }
            fmt.Println(m)
            current = i - end
            i++
        }
        //fmt.Println(i,c)
    }
    return count;
}

上解中，有对 map 的删除操作，假设原字符串实际上长度有限，可以省略掉 map 的删除，进一步空间换时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func lengthOfLongestSubstring(s string) int {
    m := make(map[byte]int)
    current := 0
    count := 0
    for i := 0; i != len(s); {
        c := s[i]
        if existIndex, ok := m[c]; existIndex < i-current || !ok {
            m[c] = i
            current++
            if (current > count) {
                count = current
            }
            i++
        } else {
            end := m[c]
            m[c] = i
            current = i - end
            i++
        }
    }
    return count;
}

此版本运行结果为

Runtime: 8 ms, faster than 84.25% of Go online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 3.1 MB, less than 49.12% of Go online submissions for Longest Substring Without Repeating Characters.

如果极端追求更少的代码行数，可以参考官网解答中给出的 java 解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}

官网也提供了把原字符串中字符当做 128bit 的 ASCII，使用 bit map 替代 map/hashmap 的解法，应自行斟酌。

Posted on | Edited on

thread annotations 之 GUARDED_BY

leveldb 中 thread_annotations.h 有如下宏定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#if defined(__clang__)

#define THREAD_ANNOTATION_ATTRIBUTE__(x)   __attribute__((x))
#else
#define THREAD_ANNOTATION_ATTRIBUTE__(x)   // no-op
#endif

#endif  // !defined(THREAD_ANNOTATION_ATTRIBUTE__)

#ifndef GUARDED_BY
#define GUARDED_BY(x) THREAD_ANNOTATION_ATTRIBUTE__(guarded_by(x))
#endif

#ifndef PT_GUARDED_BY
#define PT_GUARDED_BY(x) THREAD_ANNOTATION_ATTRIBUTE__(pt_guarded_by(x))
#endif

no-op macro

其中有用到 no-op macro，一般有几种声明方式

1
2
3
#define do_nothing(x)
#define do_nothing(x) (void)0
#define do_nothing(x) do {} while(0)

线程安全注解(thread safety annotations)

线程安全注解(thread safety annotations) 是 clang 提供的用于编译期检查锁的使用的一系列宏。其功能为编译时检查锁的使用，提示编译警告或错误

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
类拥有加锁解锁的成员函数
 LOCKABLE
类对锁的使用遵循 RAII
 SCOPED_LOCKABLE
函数进入时确保未加锁，函数退出时已加锁
 EXCLUSIVE_LOCK_FUNCTION
 SHARED_LOCK_FUNCTION  
尝试加锁并返回成功与否
 EXCLUSIVE_TRYLOCK_FUNCTION, SHARED_TRYLOCK_FUNCTION
函数进入时确保已加锁，退出时已释放
 UNLOCK_FUNCTION
数据被访问时确保已加锁
 GUARDED_BY, PT_GUARDED_BY
函数被调用时确保已经加锁
 EXCLUSIVE_LOCKS_REQUIRED, SHARED_LOCKS_REQUIRED
函数被调用时确保未加锁
 LOCKS_EXCLUDED
死锁监测，确保锁的加锁顺序
 ACQUIRED_BEFORE, ACQUIRED_AFTER

链接中有不少实例，C++ 网络库 muduo 也几乎全面添加了线程安全注解

链接

Thread Safety Analysis — Clang 3.5 documentation
Hutchins_ThreadSafety.pdf

Posted on | Edited on

题目链接

Two Sum - LeetCode

一道经典题目，网上很多资料和最优解

这里给出 golang 版本的最优解，遍历一遍 nums，期间查找和插入 map

1
2
3
4
5
6
7
8
9
10
func twoSum(nums []int, target int) []int {
    m := make(map[int] int)
    for i,n := range nums {
        if j, ok := m[target - n]; ok {
            return []int{j, i}
        }
        m[n] = i
    }
    return []int{}
}

运行结果

Runtime: 4 ms, faster than 100.00% of Go online submissions for Two Sum.
Memory Usage: 3.7 MB, less than 51.62% of Go online submissions for Two Sum.

Posted on | Edited on

ARTS 是极客时间《左耳听风》发起的挑战，缘起于发起人陈皓(酷壳 站长)有感于技术领域近年来发展越来越快，新老更迭使得我们不得不始终保持不断的学习才能跟上时代。

为了有计划的积累量变诱导质变，此项目分四个方面来提高技术人员的水平。

  1. Algorithm 算法，主要指在在线平台如 leetcode 进行的编程训练
  2. Review 阅读英文技术文章，深入学习经典的英文原文，跟踪关注技术博客(公司和个人)
  3. Tip 知识点，整理零散的知识点，起到提醒或备忘的作用
  4. Share 建立影响力，可通过技术博客，讲课等方式

在这个知识爆炸的年代，努力学习工作当然重要、但如果能善用网络，找到像极客时间这样的有助于了解学习本身的网站，已算是走了捷径。如果喜欢上网学习技术大佬的博客，通过 RSS 订阅等方式跟踪前辈的学习步伐，甚至是自发的翻阅英文原文，了解国外技术的最新动态的话，大概就算是技术里的少数了。如果能够把所看所学进行实践，融会贯通运用到业务中或者有自己的感悟能够成文，就俨然是一位大佬了。

链接：
极客时间《左耳听风》发起的ARTS挑战怎么参加？【知乎】

Posted on | Edited on

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment