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

Question

问题：

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

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

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

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

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

1. 有一个双向链接的匹配列表（http://golang.org/pkg/container/list/）
2. 计算其长度（len()行得通吗？）
3. 预分配此容量的一部分
4. 将字符串指针复制到此切片

Go中是否有较省力的方法来实现此目标（附加〜O（1）附加复杂性）？

（当然是golang新手）

Answer 1

append()的 平均（摊销）成本已经是O（1），因为它每次都会使数组增加一个百分比。随着阵列变大，增长变得越来越昂贵，但比例却越来越少。10M项切片的增长成本比1M项切片的成本高10倍，但是由于我们分配的额外容量与大小成正比，因此append(slice,item)在下一次增长之前，其调用数也将是其10倍。重新分配的增加的成本和减少的频率会抵消，从而使平均成本保持不变，即O（1）。

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

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

container/list在微基准测试中，我的速度降低了约3倍；当然，链表附加也是固定时间，但是我想 append它的常数较低，因为它通常只能写到几个内存中，而不分配列表项，等等。计时码在Playground中不起作用但您可以在本地复制并运行它以查看自己的身份： http

//play.golang.org/p/uYyMScmOjX

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

你可以写的东西流的结果作为一个单一的功能：logparser.Grep(in io.Reader, out io.Writer, patterns []regexp.Regexp); 你可以或者让out一个chan []byte或者func(match []byte) (err error)，如果你不希望将结果发送到与grep的代码过于沉浸代码。

（在[]bytevs上string：在您执行I / O时，a[]byte似乎可以完成此工作，并且避免了[]byte<=>
string转换，所以我更愿意这样做。但是，我不知道您在做什么，以及是否需要string没关系。）

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