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

发布时间：2020-12-16 19:04:26 所属栏目：大数据来源：网络整理

导读：问题：我需要将多个正则表达式应用于大日志文件的每一行(如几GB长),收集非空匹配并将它们全部放在一个数组中(用于序列化并通过网络发送). 如果回答this question持有,切片没有多大帮助： If the slice does not have sufficient capacity,append will need

问题：

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

如果回答this question持有,切片没有多大帮助：

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.

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

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

>有一个双重链接的比赛清单(http://golang.org/pkg/container/list/)
>计算其长度(将len()工作吗？)
>预分配一部分此容量
>复制到此切片的字符串指针

在Go中是否有一种不太费力的方法来实现这个目标(附加~O(1)追加复杂性)？

(golang新手当然在这里)

append()的平均(摊销)成本已经是O(1),因为它每次增长一个百分比.随着阵列变大,增长越来越昂贵,但比例也越来越少.一个10M项目的切片比一个1M项切片要贵10倍,但由于我们分配的额外容量与大小成正比,所以它也是追加(切片,项目)调用的10倍.下一次它成长.增加的成本和降低的重新分配频率抵消了,使平均成本保持不变,即O(1).

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

在我的笔记本电脑上,我可以在77毫秒内运行一百万个切片=追加(切片,一些静态串).下面提到的快速的一个原因是,“复制”字符串以扩大数组实际上只是复制字符串标题(指针/长度对),而不是复制内容.与您正在使用的其他数据量相比,100,000个字符串标题仍然低于2MB进行复制,这并不是什么大问题.

容器/列表在微基准测试中对我来说慢了3倍;链接列表追加也是恒定时间,当然,但我想追加有一个较低的常量,因为它通常只能写入几个字的内存而不是分配列表项等.时序代码将不起作用游乐场,但你可以在本地复制并运行它来看你自己：http://play.golang.org/p/uYyMScmOjX

但是你在这里问一个关于类似grep的应用程序的更具体的问题(并且感谢你用上下文询问一个详细的问题).为此,底线建议是,如果您正在搜索日志,那么最好避免在RAM中缓冲整个输出.

您可以编写一些内容来将结果作为单个函数流式传输：logparser.Grep(在io.Reader中,out io.Writer,patterns [] regexp.Regexp);如果您不希望发送结果的代码与grep代码过于混淆,您可以选择发出chan []字节或func(匹配[]字节)(错误错误).

(在[]字节与字符串上：a []字节似乎在这里完成工作并且在执行I / O时避免[] byte< =>字符串转换,所以我更喜欢.我不知道是什么但是你所做的一切,如果你需要字符串就可以了.)

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!