go - 高效附加到可变长度的字符串容器 (Golang)

Question

问题:

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

如果回答 this question， slice 并没有多大帮助持有:

If the slice does not have sufficient capacity, append will need to allocate new memory and copy the old one over. For slices with <1024 elements, it will double the capacity, for slices with >1024 elements it will increase it by factor 1.25.

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

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

1. 有一个匹配的双向链表(http://golang.org/pkg/container/list/)
2. 计算它的长度(len() 会起作用吗？)
3. 预先分配一部分容量
4. 复制字符串指针到这个 slice

在 Go 中有没有更省力的方法来实现这个目标(追加 ~ O(1) 追加复杂度)？

(这里当然是 golang 新手)

Answer 1

append() 的平均(摊销)成本已经是 O(1)，因为它每次都会按百分比增长数组。随着阵列越来越大，增加它的成本会越来越高，但相应地也会越来越少。一个 10M 项目的 slice 的增长成本是 1M 项目 slice 的 10 倍，但由于我们分配的额外容量与大小成正比，它也将是 10 倍的 append(slice, item ) 调用直到下一次增长。增加的成本和减少的重新分配频率相互抵消，使平均成本保持不变，即 O(1)。

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

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

container/list 在微基准测试中对我来说慢了 3 倍；当然，链表追加也是常数时间，但我认为 append 具有较低的常数，因为它通常只能写入几个内存字而不分配列表项等。时间安排代码在 Playground 中不起作用，但您可以将其复制到本地并运行它以查看您自己:http://play.golang.org/p/uYyMScmOjX

有时，您可以预先分配空间以避免重新分配/复制(在此示例中，使用 make([]string, 0, 1000000) 将运行时间从 ~77ms 缩短到 ~10ms) ，但是，当然，通常只是你没有足够的关于预期数据大小的信息等等来获得有值(value)的 yield ，你最好把它留给内置算法。

---

但是您在这里问的是关于类似 grep 的应用程序的更具体的问题(感谢您提出具有上下文的详细问题)。为此，底线建议是，如果您要搜索大量日志，最好完全避免在 RAM 中缓冲整个输出。

您可以编写一些东西将结果流式传输为单个函数:logparser.Grep(in io.Reader, out io.Writer, patterns []regexp.Regexp);如果你不想要发送结果的代码与 grep 代码过于纠缠。

(关于 []byte 与 string:[]byte 似乎在这里完成了工作并避免了 [] byte<=>string 转换，当你做 I/O 时，所以我更喜欢那样。不过，我不知道你在做什么，如果你需要 string 没问题。)

如果您确实将整个匹配列表保存在 RAM 中，请注意保持对大字符串或字节 slice 的一部分的引用可以防止整个源字符串/slice 被垃圾收集。因此，如果您走那条路，那么与直觉相反，您实际上可能想要复制匹配项以避免将所有源日志数据保留在 RAM 中。