高效地向变长字符串容器追加元素（Golang）

Question

高效地向变长字符串容器追加元素（Golang）

gocontainersslice

7

问题：

我需要对一个大型日志文件（几个GB长）的每一行应用多个正则表达式，收集非空匹配项，并将它们全部放入一个数组中（以进行序列化并通过网络发送）。

如果回答 this question 是肯定的，那么切片就没有太大的帮助：

如果切片没有足够的容量，追加操作将需要分配新的内存并复制旧的内容。对于长度小于1024的切片，它会将容量翻倍；对于长度大于1024的切片，它会将容量增加1.25倍。

由于可能会有成千上万的正则表达式匹配项，我无法预测切片的长度/容量。我也不能让它太大，“以防万一”，因为这样会浪费内存（或者不会吗？如果内存分配器足够聪明，不会分配太多未写入的内存，那么我可以使用巨大的切片容量而不会造成太大的伤害吗？）。

因此，我考虑以下替代方案：

拥有一个双向链表的匹配列表 (http://golang.org/pkg/container/list/)
计算它的长度 (会用 len() 吗?)
预分配一个具有该容量的切片
将字符串指针复制到此切片中

在 Go 中是否有更少费力的方法来实现这个目标（使用 ~ O(1) 的追加复杂度）？

（当然，我是 Go 语言的新手）

- LetMeSOThat4U

2个回答

3

我试图用一个非常简单的例子来概括您的问题。

由于可能存在“成千上万个正则表达式匹配项”，因此我对matches切片容量进行了大量的初始分配，即1 M（1024 * 1024）条目。切片是一种引用类型。切片头部“struct”具有长度、容量和指针，总共在64位操作系统上为24（3 * 8）字节。因此，1 M条目的切片的初始分配仅为24（24 * 1）MB。如果有超过1 M条目，则会分配一个新的容量为1.25（1 + 1 / 4）M条目的切片，并将现有的1 M切片头部条目（24 MB）复制到其中。

总之，您可以通过最初过度分配切片容量来避免许多append的开销。更大的内存问题是保存和引用每个匹配项的所有数据。更大的CPU时间问题是执行regexp.FindAll所需的时间。

package main

import (
    "bufio"
    "fmt"
    "os"
    "regexp"
)

var searches = []*regexp.Regexp{
    regexp.MustCompile("configure"),
    regexp.MustCompile("unknown"),
    regexp.MustCompile("PATH"),
}

var matches = make([][]byte, 0, 1024*1024)

func main() {
    logName := "config.log"
    log, err := os.Open(logName)
    if err != nil {
        fmt.Fprintln(os.Stderr, err)
        os.Exit(1)
    }
    defer log.Close()
    scanner := bufio.NewScanner(log)
    for scanner.Scan() {
        line := scanner.Bytes()
        for _, s := range searches {
            for _, m := range s.FindAll(line, -1) {
                matches = append(matches, append([]byte(nil), m...))
            }
        }
    }
    if err := scanner.Err(); err != nil {
        fmt.Fprintln(os.Stderr, err)
    }
    // Output matches
    fmt.Println(len(matches))
    for i, m := range matches {
        fmt.Println(string(m))
        if i >= 16 {
            break
        }
    }
}

- peterSO

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- twotwotwo · Accepted Answer

append()的平均（分摊）成本已经是O(1)，因为它每次都会按比例增加数组大小。随着数组变得越来越大，增加它的成本会变得更高，但比例上更少。一个10M项的切片将比一个1M项的切片增长费用昂贵10倍，但由于我们分配的额外容量与大小成比例，下一次增长也会有10倍数量的append(slice, item)调用。逐渐增加的成本和减少的重新分配频率相互抵消，使平均成本保持不变，即O(1)。

同样的想法也适用于其他语言的动态大小数组：例如，Microsoft的std::vector实现每次增加50%的数组大小。分摊O(1)并不意味着您不需要支付任何分配费用，只是随着数组变得越来越大，您继续以相同的平均速率支付。

在我的笔记本电脑上，我可以在77毫秒内运行一百万次“slice = append(slice, someStaticString)”操作。其中一个原因是它很快，正如siritinga在下面指出的那样，“复制”字符串以扩大数组实际上只是复制字符串头（指针/长度对），而不是复制内容。复制100,000个字符串头仍然不到2MB，与您正在处理的其他数据量相比并不重要。

在微基准测试中，container/list对我来说慢了约3倍；链表追加当然也是常数时间，但我想append具有更低的常数，因为它通常只能写入几个字的内存而不是分配列表项等。计时代码在Playground中无法工作，但您可以将其复制到本地并运行它以查看自己：http://play.golang.org/p/uYyMScmOjX 有时，你可以预先分配空间以避免重新分配/复制（在这个示例中，使用make([]string, 0, 1000000)可以将运行时间从大约77毫秒缩短到约10毫秒），但是，当然，通常情况下你没有足够的信息了解预期数据大小等，因此更好地将其留给内置算法。

但是你在这里问的是关于类似于grep的应用程序的更具体问题（感谢您提供了有背景的详细问题）。对此，最重要的建议是，如果您正在搜索大量日志，则最好避免在RAM中缓冲整个输出。

您可以编写一些代码以将结果作为单个函数流式传输：logparser.Grep(in io.Reader, out io.Writer, patterns []regexp.Regexp)；或者，如果您不想让发送结果的代码与grep代码太过纠缠，可以将out设置为chan []byte或func(match []byte) (err error)。

（关于[]byte vs. string：在这里，[]byte似乎能够胜任工作，并且避免了在进行I/O时进行[]byte<=>string转换，因此我更喜欢它。但我不知道您在做什么，如果需要string，那也可以。）

如果你将整个匹配列表保存在RAM中，请注意保留大字符串或字节切片的一部分的引用会阻止整个源字符串/切片被垃圾回收。因此，如果你选择这种方法，那么出乎意料地，你实际上可能想要复制匹配项以避免将所有源日志数据保存在RAM中。