高效附加到可变长度的字符串容器（Golang）

Question

问题：

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

如果这个问题的答案成立，切片没有多大帮助：

如果切片没有足够的容量，则 append 将需要分配新内存并复制旧内存。对于 <1024 个元素的切片，它将使容量加倍，对于具有 >1024 个元素的切片，它将增加 1.25 倍。

由于实际上可能有数十万个正则表达式匹配，因此我无法真正预测切片的长度/容量。我不能让它太大或者“以防万一” bc 这会浪费内存（或者会吗？如果内存分配器足够聪明，不会分配太多未写入的内存，也许我可以使用巨大的切片容量没有太大的伤害？）。

所以我正在考虑以下替代方案：

1. 有一个双向链接的匹配列表（http://golang.org/pkg/container/list/）

2. 计算它的长度（会len()起作用吗？）

3. 预分配此容量的一部分

4. 将字符串指针复制到此切片

在 Go 中是否有一种不那么费力的方法来实现这个目标（追加 ~ O(1) 追加复杂度）？

（当然这里是 golang 新手）

Answer 1

我试图将您的问题提炼成一个非常简单的例子。由于可能有“数十万个正则表达式匹配”，我为matches切片容量做了大量的初始分配 1 M (1024 * 1024) 个条目。切片是一种引用类型。在 64 位操作系统上，切片标头“结构”具有长度、容量和总共 24 (3 * 8) 个字节的指针。因此，对 1 M 个条目的切片的初始分配仅为 24 (24 * 1) MB。如果条目超过 1 M，则将分配容量为 1.25 (1 + 1 / 4) M 个条目的新切片，并将现有的 1 M 切片标头条目 (24 MB) 复制到其中。总之，您可以append通过最初过度分配切片容量来避免 many s 的大部分开销。更大的内存问题是为每个匹配保存和引用的所有数据。更大的 CPU 时间问题是执行regexp.FindAll's所花费的时间。package mainimport (&nbsp; &nbsp; "bufio"&nbsp; &nbsp; "fmt"&nbsp; &nbsp; "os"&nbsp; &nbsp; "regexp")var searches = []*regexp.Regexp{&nbsp; &nbsp; regexp.MustCompile("configure"),&nbsp; &nbsp; regexp.MustCompile("unknown"),&nbsp; &nbsp; regexp.MustCompile("PATH"),}var matches = make([][]byte, 0, 1024*1024)func main() {&nbsp; &nbsp; logName := "config.log"&nbsp; &nbsp; log, err := os.Open(logName)&nbsp; &nbsp; if err != nil {&nbsp; &nbsp; &nbsp; &nbsp; fmt.Fprintln(os.Stderr, err)&nbsp; &nbsp; &nbsp; &nbsp; os.Exit(1)&nbsp; &nbsp; }&nbsp; &nbsp; defer log.Close()&nbsp; &nbsp; scanner := bufio.NewScanner(log)&nbsp; &nbsp; for scanner.Scan() {&nbsp; &nbsp; &nbsp; &nbsp; line := scanner.Bytes()&nbsp; &nbsp; &nbsp; &nbsp; for _, s := range searches {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for _, m := range s.FindAll(line, -1) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; matches = append(matches, append([]byte(nil), m...))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; if err := scanner.Err(); err != nil {&nbsp; &nbsp; &nbsp; &nbsp; fmt.Fprintln(os.Stderr, err)&nbsp; &nbsp; }&nbsp; &nbsp; // Output matches&nbsp; &nbsp; fmt.Println(len(matches))&nbsp; &nbsp; for i, m := range matches {&nbsp; &nbsp; &nbsp; &nbsp; fmt.Println(string(m))&nbsp; &nbsp; &nbsp; &nbsp; if i >= 16 {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}