高效追加可变长度的字符串容器(Golang)

Question

问题:

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

如果对这个问题的答案成立,切片并没有多大帮助:

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

由于可能有数十万个正则表达式匹配,我无法真正预测切片的长度/容量.我不能把它变得太大"以防万一"bc这会浪费内存(或者它会吗？如果内存分配器足够聪明不分配太多未写入的内存,也许我可以使用巨大的切片容量没有太大的伤害？).

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

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).

同样的想法也适用于其他语言的动态大小的数组:例如,微软的std::vector实现显然每次增加50%的数组.摊销O(1)并不意味着您不需要为分配支付任何费用,只是您继续按照与阵列变大相同的平均费率付款.

在我的笔记本电脑上,我可以slice = append(slice, someStaticString)在77毫秒内运行一百万秒.下面提到的快速的一个原因是,"复制"字符串以扩大数组实际上只是复制字符串标题(指针/长度对),而不是复制内容.与您正在使用的其他数据量相比,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代码过于混淆.

(在[]byte主场迎战string:一[]byte,似乎在这里做的工作,避免[]byte<=> string转换,当你的I/O,所以我宁愿我不知道你在做什么都,不过,如果你需要.string没关系.)

如果确实将整个匹配列表保留在RAM中,请注意保持对大字符串或字节切片的一部分的引用会使整个源字符串/切片不被垃圾回收.因此,如果你走这条路,那么违反直觉,你可能实际上想要复制匹配,以避免将所有源日志数据保存在RAM中.