Golang: 一个 map 里面有多个相同的 key?

最近在 v2ex 看到这篇有趣的帖子,里面的问题很有意思,用来水篇博客再合适不过了

The Problem

楼主使用 fiber 这个 web 框架,每次接受请求时从url 解析一个 id 参数,然后对一个全局的 counter 进行累加操作。这个全局的 counter 是一个 map[string]int。锁什么的都用得很正确,但是神奇的是,println 时发现,map 里面有许多个相同的 key。这与 map 的特性相悖,一个 map 里面 key 应该是唯一的。
在最后我通过一个 demo 复现了这个 case。具体的代码在下面再一步一步解释。

初步定位

原帖在第三次 append 时,给出了一个可以复现的示例代码。
首先把原帖的代码贴上来:

package main

import (
    "fmt"
    "sync"
    "time"

    "github.com/gofiber/fiber/v2"
)

type Counter struct {
    sync.RWMutex
    data map[string]int
}

func (c *Counter) Incr(key string) int {
    c.Lock()
    c.data[key]++
    count := c.data[key]
    c.Unlock()
    return count
}

var (
    accessLog = &Counter{data: make(map[string]int)}
)

func init() {
    go func() {
        ticker := time.NewTicker(time.Second * 10)
        for range ticker.C {
            func() {
                accessLog.Lock()
                fmt.Println(accessLog.data)
                accessLog.data = make(map[string]int)
                accessLog.Unlock()
            }()

        }
    }()

}
func handler(c *fiber.Ctx) error {
    id := c.Params("id")
    accessLog.Incr(id)
    return c.Status(200).SendString("")
}

func main() {
    app := fiber.New(fiber.Config{Prefork: false})
    app.Get("/item/:id", handler)
    app.Listen(fmt.Sprintf(":%d", 8099))
}

复制运行后发现的确如此,key 都是重复的。
首先代码 review 后,没有发现明显问题。锁的使用中规中矩; map 并发写的话,也不应该出现这种情况,而是会直接 panic。所以初步排除了是锁的问题。

分而治之

原始代码只包含了两个部分: Counter 和 fiber handler。
首先把 Counter 拆出来,单独起多个协程对其 incr,无法复现那个 case。具体代码就不细讲了。
那问题应该出在 fiber 的使用上面了。

通过代码 review,想来想去最有鬼的应该就是 key 有问题了。
做了几个猜想:

  1. key 里面长度不一且含有不可见字符: 通过 unsfae 包拿到字符串的 Data地址和 len,可以看到 key 的 len 全部都是 3. 示例代码参考strHeader := (*reflect.StringHeader)(unsafe.Pointer(&str))。可以看到 strHeader 的 Len 都是 3。
  2. 参考 The Go Memory Model,假设框架用法有误,导致了 key 的使用比 key 从 url 中解析要早,这样可以解释为什么插入 map 的时候 hashkey 都不一致;插入后,若是使用 unsafe 包再解析出来 key,就会使 map 里面都是"id1" 的 key。不过通过对比 fiber 文档、打断点,打日志等方式,否定了这个猜想。

不过 2 的思路已经很接近了,就是“key的内容会变”的这个假设。

谜底

如果说一个 string 会变,最可能的原因是它底层的 []byte 变了;在这个 web 框架的场景中, []byte pool 来复用 []byte 又是很常见的思路。
如果插入前 key 没有变化,那么应该就是插入完之后,key 变了。
通过 review 代码,可以看到 fiber 使用了两个 getStr([]byte)string 方法,其中一个直接使用 unsafe 包,而另一个使用string([]byte)。前者不会进行一次内存分配,而是直接把 []byte 作为 string 往外丢,如果底层的 []byte 变更了,那对应 string 的内容也会跟着变更。fiber 的默认设置使用前者作为 getStr 方法。
结合多个现象:

  1. key 大概率会变更而不是一个 immutable string
  2. web 框架常见的 []byte 复用
  3. fiber 默认使用 unsafe 作为 getStr 的实现方法

猜想:我们的 key,在请求完成后,[]byte 被重复利用了
假设我们一开始插入了一个 id1, 在请求完成后,[]byte 被回收利用成了 id2
map 的实现里面没有拷贝一次 string,所以 map 里面的 key 变成了 id2,但是 hash 还是之前 id1 的 hash
然后分两种情况:

  • 新插入 id1,!t.key.equal(key, k), 所以给它分配了一个新的桶
  • 新插入 id2,原有的 id2 跟新的 id2 hash 不相等,不会覆盖,还是给它新分配一个新的桶
    这种情况下,map 里面出现重复的 key,就解释得通了。

复现

既然复现条件搞清楚了,那么这个函数就很好写了,只需要用 unsafe 生成 key,然后在插入之后去修改 key 就可以了。
在 Golang 中,string promised immutable,而这里使用 unsafe 突破了这个约束,自然就会出现问题。
用这段代码生成的 map,里面包含了 200个 "id1" 的 key

func makeMap()map[string]int {
    m := make(map[string]int)
    for i := 0; i < 200; i++{
        b := []byte("id2")
        str := *(*string)(unsafe.Pointer(&b))
        strptr := (*reflect.StringHeader)(unsafe.Pointer(&str))
        _ = strptr
        m[str]++
        b[2] = '1'
    }
    return m
}

修复

既然知道了是 key 的问题,就很简单了,以下任意一个解法都可以:

  1. 使用fiber.Config{Prefork: false, Immutable: false},这样会保证 []byte 到 string 的时候经过一次内存分配和拷贝,key 在请求完成后也不会变化。缺点是可能带来很多额外的内存分配和拷贝的性能消耗。
  2. 使用 key2 = key +"字符", 显式地重新为 key 分配另一块内存,这样也可以保证插入 map 后,key 不会发生变化。原帖有回复提到accessLog.Incr(id + "")这样也会解决问题,但是我尝试了str2 := str + ""后发现 Data 指针并没有变化,并没有分配新的内存,可能因为不同版本编译器的优化不一样。
    解法都是让插入 map 后的 key 不发生变化。

后记

在原帖中,因为这个问题一开始并不显然,所以引起了很多讨论,涉及不限于锁、管道、concurrent-map等讨论,最后发现根本不是并发引起的问题不过这些讨论里面提到的一些思路和想法还是值得思考的。其中9楼提出仨优化方案没一个对的,被众人指出,看得我乐呵得 在 v2 也算是比较少见这种讨论得氛围了。

译: Golang 如何生成固定长度的随机字符串

译者写在前面:之前在 Stack Overflow 看到了这个回答,感觉很多优化思路可以用在日常的开发之中。搜了一下中文社区没找到该回答翻译,所以打算翻译成中文,这样我的博客就可以又多一篇水文。
需要注意的是,该文的各种优化方法之后,代码可读性会非常的差,在日常工作中这样写需要注意人身安全。
不过很多优化的思想还是值得借鉴的。

原文地址点击这里

以下是原文的译文

Paul 的解决方案提供了一个简单普遍的解法。

该问题再寻求“最快和最简单的方法”。我们来着眼于最快。我们会一步一步得出我们一个最终的最快的版本。每一步的 benchmark 结果会附在本回答的最后。

所有的方案和性能测试的代码可以在这个 Go playground看到. 这些代码是一个 test 文件,而不是一个可直接执行的代码。你可以把它保存成XX_test.go然后用以下命令执行

go test -bench . -benchmem

写在前面:

如果你只是需要一个随机字符串,最快的解决方案并不是首选方案,Paul 的解决方案已经足够了。这个最快的方案仅使用于性能敏感的场景。虽然前两步的优化已经足够使用了,它在原来的基础上提升了 50%的性能。(具体数值参考 Benchmark 一章),而且不会让代码变得太复杂。

不过,即使你不需要最快的解法,看完这个回答可能会有点挑战性而又可以从中学到东西。

I. 优化

1. 起源(字符)

我们要优化的最原始的一般解法像这样

func init() {
    rand.Seed(time.Now().UnixNano())
}

var letterRunes = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

func RandStringRunes(n int) string {
    b := make([]rune, n)
    for i := range b {
        b[i] = letterRunes[rand.Intn(len(letterRunes))]
    }
    return string(b)
}

2. Bytes

如果我们的随机字符串仅由英语字母大小写组成,我们可以只使用 bytes 因为英文字母跟 byte 是一一对应映射的(Go 存储strings 的方式)
所以,对于原来的语句

var letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

我们可以替换为

var letters = []bytes("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")

或者这样甚至更好

const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

现在已经是一个很大的优化了:我们可以把它声明成 const(Go 中有 string 常量但是没有 slice 常量)。额外的收益是,len(letters)也会是一个常量(当 s 是一个string常量时,表达式len(s)也是常量)

那成本呢?没有任何成本。我们可以通过 index 拿到 string 中的 byte。

优化完后,我们的代码如下:

const letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

func RandStringBytes(n int) string {
    b := make([]byte, n)
    for i := range b {
        b[i] = letterBytes[rand.Intn(len(letterBytes))]
    }
    return string(b)
}

3. 取余

上一个解法中,我们通过 rand.Intn()获得一个随机字符,而 Rand.Intn() 是委托给 Rand.Int31n() 执行的。

所以相比于一次生成 63个随机bit 的 rand.Int63()来说,它要慢得多。

所以我们可以直接使用rand.Int63() 然后使用它除以 len(letterBytes) 的余数:

func RandStringBytesRmndr(n int) string {
    b := make([]byte, n)
    for i := range b {
        b[i] = letterBytes[rand.Int63() % int64(len(letterBytes))]
    }
    return string(b)
}

它要显著地比之前的解法快得多地完成了任务,缺点是所有字母出现的概率并不是完全一致的(假定rand.Int63()生成所有 63位数字的概率相等)。
不过这个差异足够小, 因为共计52个字符,这个数量远远小于 1<<63-1,所以在实践中使用是没有问题的。

用更简单的角度解释一下:假如你需要从 0\~5中随机挑一个数值,当使用 3个随机位,获得0\~1的概率比2\~5的概率要大一倍。使用 5个随机位,0\~1 出现的概率是 6/32, 2\~5 出现的概率是5/32,更接近期望的值了。增大随机位的数量使差异更小,当达到 63位时,差异可忽略不计。

4. 掩码

基于上一个解法,我们可以只用低几位的 bit 来获得我们想要的一个字母。如果我们有 52个字母,我们需要用 6个 bit 来表示它: 52 = 110100b。所以我们可以只用rand.Int63()返回的低 6位。若要使所有字符出现的概率相等,我们只使用那些位与区间0\~len(letterBytes)-1的数字。如果最低的几位比这个要大,那我们重新生成一个新的随机数。

需要提醒的是,最低几位大于len(letterBytes) 的概率通常低于 0.5(平均来说是 0.25),意味着我们只需要重复几次,无法获得值域内的随机数的概率就会大大降低。在 n 次随机后,我们无法获得一个合适的下标的概率远低于 pow(0.5,n),而这已经是一个较高的估计了。
当我们有 52个字符是,低 6位不能用的概率仅为 (64-52)/64 = 0.19,因此例子中循环 10次拿不到一个合适的随机数的概率是 1e-8

然后这是解法:

const letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
const (
    letterIdxBits = 6                    // 用 6位表示一个字母的下标
    letterIdxMask = 1<<letterIdxBits - 1 // 数量和 letterIdxBits 一样多的 为 1的位
)

func RandStringBytesMask(n int) string {
    b := make([]byte, n)
    for i := 0; i < n; {
        if idx := int(rand.Int63() & letterIdxMask); idx < len(letterBytes) {
            b[i] = letterBytes[idx]
            i++
        }
    }
    return string(b)
}

5. 掩码优化版

上一个解法只用了 rand.Int63() 返回的63位中的低 6位。我们算法中耗时最长的就是获取随机数,因此我们浪费了非常多的计算资源。
如果我们有 52个字母,意味着每 6位可以唯一索引一个字母。因此 63随机位可以可以指定 63/6 = 10 个不同的字母。我们可以把这 10个都用上:

const letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
const (
    letterIdxBits = 6                    // 6 bits to represent a letter index
    letterIdxMask = 1<<letterIdxBits - 1 // All 1-bits, as many as letterIdxBits
    letterIdxMax  = 63 / letterIdxBits   // # of letter indices fitting in 63 bits
)

func RandStringBytesMaskImpr(n int) string {
    b := make([]byte, n)
    // A rand.Int63() generates 63 random bits, enough for letterIdxMax letters!
    for i, cache, remain := n-1, rand.Int63(), letterIdxMax; i >= 0; {
        if remain == 0 {
            cache, remain = rand.Int63(), letterIdxMax
        }
        if idx := int(cache & letterIdxMask); idx < len(letterBytes) {
            b[i] = letterBytes[idx]
            i--
        }
        cache >>= letterIdxBits
        remain--
    }

    return string(b)
}

6. 源

上一个掩码优化版 已经非常好了,没有太多的改进空间了。我们可以加以改进,不过引入的复杂度不一定值得。
现在我们来看其它可以优化的地方。随机数生成源
crypto/rand 包提供了 Read(b []byte) 函数,所以我们可以一次调用就获得足够多 byte。不过这对于我们的问题并没有什么作用,因为crypto/rand 实现了加密安全的伪随机数生成算法而导致它的性能要慢得多。
我们看回来math/rand 包。 rand.Rand 使用了 rand.Source 作为随机位生成源。rand.Source 是一个接口,指定了一个 Int63() int64 方法:--在我们只需要这个。
所以我们其实并不需要 rand.Rand (无论隐式或全局变量,被包含在 rand 包中的),一个 rand.Source 已经完美地满足我们的需要了。

var src = rand.NewSource(time.Now().UnixNano())

func RandStringBytesMaskImprSrc(n int) string {
    b := make([]byte, n)
    // A src.Int63() generates 63 random bits, enough for letterIdxMax characters!
    for i, cache, remain := n-1, src.Int63(), letterIdxMax; i >= 0; {
        if remain == 0 {
            cache, remain = src.Int63(), letterIdxMax
        }
        if idx := int(cache & letterIdxMask); idx < len(letterBytes) {
            b[i] = letterBytes[idx]
            i--
        }
        cache >>= letterIdxBits
        remain--
    }

    return string(b)
}

这个解法并不需要你去初始化(seed) math/rand包中全局的 Rand 因为我们没有用到它,我们用到的 rand.Source 已经被初始化好了。
还有一个需要注意的, math/rand 的文档中注明了:
默认的 Source 是并发安全的,可以被用于多个 Goroutine 中
所以默认的随机数源要比从 rand.NewSource() 获得的随机数源要慢的多,因为默认的随机数源需要保证并发调用下的协程安全,而 rand.NewSource() 并没有提供这种保证(从而它返回的随机数源更可能要快一些)

7. 使用strings.Builder

之前的所有解法都返回一个 string, 而这个 string 都是先用切片拼凑起来的(最初的解法是[]rune,然后使用[]byte), 然后再转换成 string。最后的类型转换会铲屎一个切片内容的值拷贝,因为 string 的值是不可变的,如果转换不进行一次值拷贝,无法保证这个字符串的内容不因原始切片被改变而改变。更详细的信息可以参考[How to convert utf8 string to [byte?]How to convert utf8 string to []byte? 和 [[]byte(string) vs []byte(*string)]

Go 1.10 引入了 strings.Builder. 我们可以像用bytes.Buffer 一样使用 strings.Builder 构建字符串的内容。它内部的确使用了一个 []byte,当我们操作完成后,我们通过 Builder.String() 获得最终的字符串值。但是有意思的是,他不需要进行像我们刚刚谈到的值拷贝。它之所以可以不拷贝,是因为用于构建字符串的 slice 并没有暴露出去,因此并没有办法可以无意或恶意地修改生成的”不可变“的字符串。

所以我们下一步就是,不通过切片生成一个随机字符串,而是使用 strings.Builder, 当我们完成后,我们可以生成并返回,而无需再进行一次拷贝。它可能会在速度上有所帮助,而且它无疑会优化内存占用和分配。

func RandStringBytesMaskImprSrcSB(n int) string {
    sb := strings.Builder{}
    sb.Grow(n)
    // A src.Int63() generates 63 random bits, enough for letterIdxMax characters!
    for i, cache, remain := n-1, src.Int63(), letterIdxMax; i >= 0; {
        if remain == 0 {
            cache, remain = src.Int63(), letterIdxMax
        }
        if idx := int(cache & letterIdxMask); idx < len(letterBytes) {
            sb.WriteByte(letterBytes[idx])
            i--
        }
        cache >>= letterIdxBits
        remain--
    }

    return sb.String()
}

需要留意的是,当我们创建了一个新的 strings.Builder后,我们调用它的 Builder.Grow(), 让它分配足够大的内部切片,以避免我们增加随机字符后,需要进行内存的再分配)

8. 模仿 strings.Builder 使用 unsafe

string.Builder 使用内部 []byte 构建字符串,我们自己也可以这样做。我们用strings.Builder 只是是为了避免最后的切片拷贝,而它本身也会带来一些额外开销。

strings.Builder 使用 unsafe 包来避免最终的拷贝:

// String returns the accumulated string.
func (b *Builder) String() string {
    return *(*string)(unsafe.Pointer(&b.buf))
}

问题是,我们自己也可以这样做。所以这里的方法是,我们回到上一个使用[]byte构建字符串的方法,不过当我们构建完成后,不要把它转换成 string,而是做一个”不安全的转换“:获得一个指向我们的字节片但把它作为字符串数据的字符串。

我们可以看这里的代码:

func RandStringBytesMaskImprSrcUnsafe(n int) string {
    b := make([]byte, n)
    // A src.Int63() generates 63 random bits, enough for letterIdxMax characters!
    for i, cache, remain := n-1, src.Int63(), letterIdxMax; i >= 0; {
        if remain == 0 {
            cache, remain = src.Int63(), letterIdxMax
        }
        if idx := int(cache & letterIdxMask); idx < len(letterBytes) {
            b[i] = letterBytes[idx]
            i--
        }
        cache >>= letterIdxBits
        remain--
    }

    return *(*string)(unsafe.Pointer(&b))
}

(9. 使用rand.Read())

Go 1.7 新增 一个rand.Read() 函数和一个 Rand.Read() 方法。我们可能会想用这个方法一次性获得足够多 byte 以达到更高的效率。

但是这有一个小"问题":我们需要多少字节?我们可以假设:要跟输出的字母数一样。我们可以认为这是一个向上的约数,因为一个字母索引需要少于 8位(一个字节)。但是这个解法没有上面的好,因为获取随机位是计算中最重的部分,而我们获取到的比我们需要的还要多。

还需要留意的是,为了让每个字母出现的概率一致,也许会有一些被丢弃的随机数据,所以我们可能有可能因为跳过了一些随机数据而导致最后获得的字符串不够长。然后我们需要”递归地“获取更多随机字节。现在我们连”只需要调用一次rand包“的优点都没有了。

我们可以某种程度上优化我们使用math.Rand()生成的随机数据的方法。我们可以预估我们需要多少字节(位)。一个字母需要 letterIdxBits 位,我们需要 n 个字母,所以四舍五入我们需要n * letterIdxBits / 8.0 字节。我们可以计算一个随机索引不可用的概率,所以我们可以获取多一些数据以便更可能足够使用(如果不够的话,重复这个过程)。例如我们可以用github.com/icza/bitio这个第三方库把字节切片当成 bit 流来使用。

但是基准测试中它的性能仍然没有以上好,为什么呢?

因为rand.Read() 使用循环调用 Source.Int63() 直到传入的切片填满,实际上就是没有中间 buffer 和更多复杂度的RandStringBytesMaskImprSrc()这个解法,这就是RandStringBytesMaskImprSrc()表现更好的原因。
是的RandStringBytesMaskImprSrc()使用了不同步的rand.Source 而不像 rand.Read(),不过上面的理由依然成立,我们可以使用Rand.Read() 替换 rand.read()来证明(前者也是不同步的)

II. 基准测试

好了,是时候看看不同解法的基准测试结果

BenchmarkRunes-4                     2000000    723 ns/op   96 B/op   2 allocs/op
BenchmarkBytes-4                     3000000    550 ns/op   32 B/op   2 allocs/op
BenchmarkBytesRmndr-4                3000000    438 ns/op   32 B/op   2 allocs/op
BenchmarkBytesMask-4                 3000000    534 ns/op   32 B/op   2 allocs/op
BenchmarkBytesMaskImpr-4            10000000    176 ns/op   32 B/op   2 allocs/op
BenchmarkBytesMaskImprSrc-4         10000000    139 ns/op   32 B/op   2 allocs/op
BenchmarkBytesMaskImprSrcSB-4       10000000    134 ns/op   16 B/op   1 allocs/op
BenchmarkBytesMaskImprSrcUnsafe-4   10000000    115 ns/op   16 B/op   1 allocs/op

只需要从 runes 切换到 bytes,我们即可获得 24% 的性能提升,同时内存占用降至原来的 三分之一

使用 rand.Int63() 代替rand.Intn()可以再获得 20%的性能提升

使用掩码(如果索引过大就重算)比它的上一个解法更慢一些: -22%

但是当我们使用所有(或者说,大部分)的63个随机位(一次调用获取10个索引):3倍于上一个解法的效率。

如果我们使用一个非默认的全新rand.Source而不是rand.Rand,我们再获得 22%的性能提升。

如果我们使用 strings.Builder, 我们获得微小的 3.5%的效率提升,但是我们减少了 50%的内存占用和分配。

最后如果我们敢于使用 unsfae包而不是 rand.Rand,我们可以获得一个不错的 14%提升。

把最后的解法与最初的解法对比,BenchmarkBytesMaskImprSrcUnsafe() 的速度是 BenchmarkRunes() 的 6.3倍,只使用了六分之一的内存和二分之一次内存分配。

到此我们的任务已经完成了。

Java 版本增量覆盖率工具

Problem to solve

在手工测试的时候,我们的 workflow 通常是这样的:

  1. 产品同学提交需求。
  2. 开发同学编码。
  3. 开发同学 push 代码,通过流水线进行静态检查、自动化测试,并部署到测试环境。
  4. 测试同学针对需求,进行针对性手工测试。
  5. 产品、设计同学走查。
  6. 上线,并在需要时添加线上监控告警规则。

    该工具要解决的问题,就是如何较为量化、清晰地评估第 4步:手工功能测试的测试质量。通过该工具,生成增量测试率报告,可以清晰地看到,该 feature 更新的代码中,被手工测试覆盖到了哪些代码,哪些没有被覆盖到。

    workflow

    引入该工具,需要在手工测试后,生成一份覆盖率报告。大致的 workflow 变为如下:

  1. 产品同学提交需求。
  2. 开发同学编码。
  3. 开发同学 push 代码,通过流水线进行静态检查、自动化测试,并部署到测试环境。
  4. 测试同学针对需求,进行针对性手工测试。
  5. 生成此时测试环境中的覆盖率报告。
  6. 产品、设计同学走查。
  7. 上线,并在需要时添加线上监控告警规则。

    主要思路:

    • 通过 git diff ,获取两次发布之间的代码变更,并进行稍微处理,可以得到 map<文件名, 变更的行数>,其中文件名应包含类名,被覆盖的行数为 ArrayList\, 行号为新版本的代码中变更的行号,如下图集合A。
    • 通过手工测试之后生成的覆盖率报告,可以获得手工测试中,已覆盖到&未覆盖到的行号。把覆盖到的行号设为集合S'
    • A ∩ S' 即为此次发布中,更新的代码中被覆盖到的行数,未覆盖到的同理。
    • 若某行有更新,且不需要被覆盖,则在增量覆盖率报告中,体现为灰色。(如空行、注释、import)
    • 以原测试覆盖率报告为 html 模板,把第 3 步获取的行号,渲染到 html 文件中,生成新的覆盖率报告。

具体实现

git diff
  • git diff 可以简单的通过命令行获得,注意一次发布可能包含多个commit,获取代码变更的时候需要获取多个 commit 的合并变更,具体可以参考 这篇文档

  • git diff 输出的文件包含单个/多个文件,通过简单的字符串匹配分割,即可分割出每个文件的变更,其中变更类型可能是新增、更改、删除,文件类型可能是 text 或 binary,这里我们不对 binary 文件进行处理,直接忽略。

  • git diff 的每个文件变更内,包含单个/多个代码块变更,首先通过简单的字符串匹配分割,然后对每个变更块进行计数&遍历,即可获得每个代码块的变更行数,其中变更行数指修改/新增行数,被删除的行被忽略即可。把每个变更块的行号进行合并,即可获得该文件的变更行号(上图集合A)。

报告解析
  • 我们采用的是 jacoco 生成的覆盖率报告。该报告的目录结构见附录。该报告包含 index.html 为主要入口,样式被记录于jacoco-resources/report.css,并在浏览器打开时,使用 jacoco-resources/prettify.js 进行页面样式的调整与优化。
  • 代码文件与报告路径可以简单地通过字符串匹配获得,如com/foo/Bar.java 对应 html 文件com.foo/Bar.java.html
  • 拿取未经过 prettify.js 重渲染的 html观察可得,无须覆盖的行不带有 css 样式,未覆盖的行带有样式 nc,已覆盖的行带有样式fc,通过简单的字符串分割&匹配,即可得出已覆盖、未覆盖、无须覆盖的行号。
报告渲染
  • 改动1:调整原有CSS样式
    • 去掉原来 css 类pc, nc, fc的颜色;
    • 新增 nnc, nfc 类,使用 nc, fc的颜色,以标记未覆盖/已覆盖行
    • 新增ngc 类,颜色设置为灰色,以标记更新了但无须覆盖的行(如注释)。
  • 改动2:把集合 A ∩ S' 中的行号,通过修改对应 html文件,对应行的\ 标签添加css 类 nfc的方法,标记为已覆盖。未覆盖/无须覆盖同理。
  • 改动3(TODO):统计的 html(如com.foo/index.html),需要在表格内添加一列,以展示增量代码的覆盖率。

附录

jacoco 覆盖率报告目录结构

.
├── com.foo
│   ├── Bar.html
│   ├── Bar.java.html
│   ├── index.html
│   └── index.source.html
├── index.html
├── jacoco-resources
│   ├── branchfc.gif
│   ├── branchnc.gif
│   ├── branchpc.gif
│   ├── bundle.gif
│   ├── class.gif
│   ├── down.gif
│   ├── greenbar.gif
│   ├── group.gif
│   ├── method.gif
│   ├── package.gif
│   ├── prettify.css
│   ├── prettify.js
│   ├── redbar.gif
│   ├── report.css
│   ├── report.gif
│   ├── session.gif
│   ├── sort.gif
│   ├── sort.js
│   ├── source.gif
│   └── up.gif
├── jacoco-sessions.html
└── tree.output

[编程题]贪吃的小Q-算法题记录

前几天隔壁宿舍同学在刷算法题,串门的时候看到了这道有趣的题,记录一下。 原题目是这样的: 链接:https://www.nowcoder.com/questionTerminal/d732267e73ce4918b61d9e3d0ddd9182?orderByHotValue=1&page=1&onlyReference=false 来源:牛客网 小Q的父母要出差N天,走之前给小Q留下了M块巧克力。小Q决定每天吃的巧克力数量不少于前一天吃的一半,但是他又不想在父母回来之前的某一天没有巧克力吃,请问他第一天最多能吃多少块巧克力

输入描述:
每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数,表示父母出差的天数N(N<=50000)和巧克力的数量M(N<=M<=100000)。
输出描述:
输出一个数表示小Q第一天最多能吃多少块巧克力。
示例1

输入

3 7

输出

4

一开始打算找规律,使用2的n次方进行分配,最后也没有得出一个好的解法(虽然已经很接近了),于是看了一下牛客的参考答案,主要是两种解法:

二分查找法:

非常暴力的方法,意料之外情理之中。需要的结果为“第一天最多可以吃多少个”,这个值一定在0与巧克力总数M之间。于是可以在[0,M]区间内进行二分查找。复杂度为O(logM·N),代码如下:

//@小冲冲

#include
using namespace std;
int n,m;
//计算第一天吃s个巧克力一共需要多少个多少个巧克力
int sum(int s){
    int sum=0;
    for(int i=0;i<n;i++){ sum+=s; s=(s+1)>>1;//向上取整
    }
    return sum;
}
//二分查找
int fun(){
    if(n==1) return m;
    int low=1;
    int high=m;//第一天的巧克力一定是大于等于1小于等于m的
    while(low<high){ int mid=(low+high+1)>>1;//向上取整
        if(sum(mid)==m) return mid;//如果第一天吃mid个巧克力,刚刚好吃完所有巧克力,那么直接返回
        else if(sum(mid)<m){ low=mid; }else{ high=mid-1; } } return high; } int main() { cin>>n>>m;
    int res=fun();
    cout<<res<<endl;
    return 0;
}

但是我个人觉得这个想法不太elegant,复杂度仍有一些高,于是再往下翻,找到一个比较有意思的解法,跟我一开始的想法差不多。他没有标明他的方法,我给他随便起个名字:

逐次分配法:

他的思路如下:

  1. 首先,每天分配一颗巧克力
  2. 计算得到剩余的可分配巧克力
  3. 按照2的N次方的顺序给各天分配,如:可分配的有7颗,则第一天分4个,第二天分2个,第三天分1个。
  4. 计算剩余的巧克力数量,如果还有剩余,跳转到2
  5. 没有剩余可分的巧克力,则完成分配。

代码如下:

//@域外創音
#include
#define MAX_INDEX 17
int power2[] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072};
int main()
{
    int n,m;
    std::cin>>n>>m;
    //只有1天时直接输出
    if(n==1){std::cout<<m<<std::endl;return 0;} //初始分配:每天最少吃1块     
    int alignable = m-n; 
    int result = 1; //如果可以某种power2[i]-1的方式分配,便进入。具体的分配是:第一天多吃power2[i-1]块,第二天多吃power2[i-2]块,依此类推。 
    //这样一来,只要每个追加分配所对应的i不重复,每天吃的块数就依然能符合要求,因为第j天吃的块数最多等于power2[从i-j到0]+1,一定大于power2[从i-j-1到0]的二倍。 
    for(int i=MAX_INDEX-1;i>=0;i--)if(alignable>=power2[i]-1)
    {
        result+=power2[i-1];
        alignable -= (power2[i]-1);
    }
    std::cout<<result<<std::endl;
    return 0;
}

这个代码非常的有意思,它可以把复杂度减少到O(log(m)),并且它还通过了所有测试用例。但是,作为预备役测试猿,我找到了它一个bug(笑)。当输入用例为(3天,20块巧克力)时,跑出来的结果是10,但是实际上,可以得到(11,6,3)的分配策略,与其得到的结果不符。使用二分查找法得出的结果也为11.问题出在哪里呢,通过代码走读很容易定位到问题出在18行:

alignable -= (power2[i]-1);

以(3天,20块)为用例,逐步推演,即可看到问题是怎么样发生的:

 

在第一轮分配的时候,@域外創音 的方法是,默认认为分配了pow(2,n)-1颗,而不是实际分出去的颗数。在此用例中,假如有4天或以上,分配列为(8,4,2,1),alignable -= 15无疑是正确的,但是当只有3天时,则会给不存在的第四天分配了一颗,从而导致最终结果的错误。

更正的方法也很简单,就是把alignable -= (power2[i]-1);改为alignable -= actually_assigned即可,而actually_assigned值的计算可以由代码中的i与天数n联合得出。

经过修改的代码如下,通过了牛客网的OJ所有测试用例,暂未发现未通过的其它反例。

#include<iostream>
#define MAX_INDEX 17
int power2[] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072};
int main()
{
    int n,m;
    std::cin>>n>>m;
    //只有1天时直接输出
    if(n==1){std::cout<<m<<std::endl;return 0;} //初始分配:每天最少吃1块
    int alignable = m-n;
    int result = 1; //如果可以某种power2[i]-1的方式分配,便进入。具体的分配是:第一天多吃power2[i-1]块,第二天多吃power2[i-2]块,依此类推。
    //这样一来,只要每个追加分配所对应的i不重复,每天吃的块数就依然能符合要求,因为第j天吃的块数最多等于power2[从i-j到0]+1,一定大于power2[从i-j-1到0]的二倍。
    for(int i=MAX_INDEX-1;i>=0;i--)if(alignable>=power2[i]-1)
        {
            if(i>0)//防止越界
                result+=power2[i-1];
            int assigned = 0;
            if(i>n)
                assigned = (power2[i]-1) - (power2[i-n]-1);
            else
                assigned = (power2[i]-1);
            alignable -= assigned;
        }
    std::cout<<result<<std::endl;
    return 0;
}

 

Tokens in Python

本文主要归纳python的parse过程中,词法分析中,生成的Token的名字以及其含义。
此文章归纳自https://github.com/python/cpython/blob/3.6/Parser/tokenizer.c,版本为python3.6。

 

"ENDMARKER", 结束标记符
"NAME", 名字
"NUMBER", 数字
"STRING", 字符串
"NEWLINE", 换行
"INDENT", 缩进
"DEDENT", 未明,在tokenizer.c里面找不到
"LPAR", 左括号(
"RPAR", 右括号)
"LSQB", 左中括号[
"RSQB", 右中括号]
"COLON", 冒号:
"COMMA", 逗号,
"SEMI", 分号;
"PLUS", 加号+
"MINUS", 减号-
"STAR", 星号*
"SLASH", 斜杠/
"VBAR", 或号|
"AMPER", 与&
"LESS", 小于号<
"GREATER", 大于号>
"EQUAL", 等于号=
"DOT", 点.
"PERCENT", 百分号%
"LBRACE", 左花括号{
"RBRACE", 右花括号}
"EQEQUAL", 判断相等==
"NOTEQUAL", 不相等!=或者<>
"LESSEQUAL", 小于等于<=
"GREATEREQUAL", 大于等于>=
"TILDE", 波浪线~
"CIRCUMFLEX", 音调符号^
"LEFTSHIFT", 左移<<
"RIGHTSHIFT", 右移>>
"DOUBLESTAR", 双星号**
"PLUSEQUAL", 加等于+=
"MINEQUAL", 减等于
"STAREQUAL", 星等于*=
"SLASHEQUAL", 除等于/=
"PERCENTEQUAL", 百分号等于%=
"AMPEREQUAL", 与等于&=
"VBAREQUAL", 或等于|=
"CIRCUMFLEXEQUAL", 次等于^=
"LEFTSHIFTEQUAL", 左移等于<<=
"RIGHTSHIFTEQUAL", 右移等于>>=
"DOUBLESTAREQUAL", 双星号等于**=
"DOUBLESLASH", 双斜杠//
"DOUBLESLASHEQUAL", 双斜杠等于//=
"AT", AT号@
"ATEQUAL", @=
"RARROW", ->
"ELLIPSIS", 省略号...
/* This table must match the #defines in token.h! */
"OP",
"AWAIT", 关键字await
"ASYNC", 关键字async
"<ERRORTOKEN>", 错误的token
"<N_TOKENS>" 不知道是啥

使用python撸一个支持四则运算的计算器

代码地址:https://github.com/MakDon/toy_calculator
效果如下:


实现的功能为读入一个字符串格式的算式,然后输出数字格式的结果。

计算器主要包括如下几个部分:

  1. 词法分析器
  2. 语法分析器
  3. 伪指令生成器
  4. 伪VM

词法分析器

词法分析器对输入的文本进行分析,输出为一串token。如输入为

"1 + 2 + 3 + 5 + 7"

则输出为:

<class 'list'>:
 [['NUMBER', '1'], ['+', '+'], ['NUMBER', '2'], ['+', '+'], 
['NUMBER', '3'], ['+','+'], ['NUMBER', '5'], ['+', '+'], ['NUMBER', '7']]

此处实现的基本思路是,使用正则对字符串从头进行匹配,若匹配到结果,则截取为一个token,然后继续匹配;若一直匹配不到结果,则认为输入的串存在词法错误。使用的正则分别如下:

 {
    "NUMBER": r"([0-9]+\.)?[0-9]+",# 数字
    "+": r"\+",# 加号
    "-": r"-",# 减号
    "*": r"\*",# 乘号
    "/": r"/",# 除号
    "LBRA": r"\(",# 左括号
    "RBRA": r"\)",# 右括号
    "SEPARATOR": r"( |\n)"# 分隔符,此处使用空格与换行
}

 

语法分析器:

语法分析,是把词法分析器生成的token串,转换为抽象语法树(Abstract Syntax Tree,AST)。上节的token串生成的AST如下:

在此计算器中,我选择的是自顶向下的生成方式。四则运算语法如下:

Expr      ->    Term ExprTail
ExprTail  ->    + Term ExprTail
          |     - Term ExprTail
          |     null

Term      ->    Factor TermTail
TermTail  ->    * Factor TermTail
          |     / Factor TermTail
          |     null

Factor    ->    (Expr)
          |     num

reference:https://zhuanlan.zhihu.com/p/24035780

其中各个符号的含义与消除左递归的推导过程详见《编译原理》。

伪指令生成

上一节的语法分析器中,生成得到了AST。这一步的作用,则是把上一节得到的树,转化为顺序的指令序列。此处使用了递归的深度遍历的方法,此处生成的每条指令包括如下两个部分:

  1. 操作:操作可以为入栈,或者是运算(加减乘除)。
  2. 操作数:可选,当操作为入栈时,操作数是被入栈的数值。当操作为运算时为None。

上一节的AST可以生成如下指令:

[(PUSH,1), (PUSH,2), (+,None), (PUSH,3), (+,None), (PUSH,5), (+,None), (PUSH,7), (+,None)]

 

伪VM

伪VM的作用,为自行上一节生成的伪指令,最后返回结算的结果。伪VM维护一个栈,用于数值计算。获得指令序列后,开始顺序执行指令。当指令的操作为入栈时,把指令的操作数push入栈顶。当指令为运算时,pop出栈顶的两个数字,进行指令的运算,然后把运算结果push回栈顶。在指令序列执行完后,伪VM的栈内应有且只有一个数值,为计算结果。

在伪VM执行完指令后,就得到结果了,计算的全过程也就此结束了。