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

Question

问题是：

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

如果这个问题的答案是正确的，那么切片并没有多大帮助：

如果片没有足够的容量，append将需要分配新内存并复制旧内存。用于切片

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

所以我在考虑以下选择：

1. 有一个双链表匹配（http://golang.org/pkg/container/list/）
2. 计算它的长度（将len（）工作？）
3. 预先分配此容量的一个片段
4. 复制指向此切片的字符串指针

在Go中是否有一种不那么费力的方法来实现这个目标（使用~O（1）append complexity进行append）？

（当然是这里的golang新手）

Answer 1

我试图把你的问题提炼成一个非常简单的例子。

因为可能有数十万个正则表达式匹配，所以我为匹配切片容量分配了大量的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）复制到该片。

总之，通过最初过度分配片容量，您可以避免许多appends的开销。更大的内存问题是为每个匹配保存和引用的所有数据。更大的CPU时间问题是执行regexp所需的时间。FindAll。

package main

import (
    "bufio"
    "fmt"
    "os"
    "regexp"
)

var searches = []*regexp.Regexp{
    regexp.MustCompile("configure"),
    regexp.MustCompile("unknown"),
    regexp.MustCompile("PATH"),
}

var matches = make([][]byte, 0, 1024*1024)

func main() {
    logName := "config.log"
    log, err := os.Open(logName)
    if err != nil {
        fmt.Fprintln(os.Stderr, err)
        os.Exit(1)
    }
    defer log.Close()
    scanner := bufio.NewScanner(log)
    for scanner.Scan() {
        line := scanner.Bytes()
        for _, s := range searches {
            for _, m := range s.FindAll(line, -1) {
                matches = append(matches, append([]byte(nil), m...))
            }
        }
    }
    if err := scanner.Err(); err != nil {
        fmt.Fprintln(os.Stderr, err)
    }
    // Output matches
    fmt.Println(len(matches))
    for i, m := range matches {
        fmt.Println(string(m))
        if i >= 16 {
            break
        }
    }
}

Answer 2

append（）的平均（摊销）成本已经是O（1），因为它每次都会增加数组的百分比。随着数组变得越来越大，它变得越来越昂贵，但比例越来越稀少。10M的切片比1M的切片要贵10倍，但是由于我们分配的额外容量与大小成正比，它也将是下一次增长之前的10倍。成本的增加和重新分配频率的减少抵消了，使平均成本保持不变，即O（1）。

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

在我的笔记本电脑上，我可以在77毫秒内运行一百万个slice=append（slice，someStaticString）s。siritinga在下面指出，它之所以快速的一个原因是“复制”字符串以放大数组实际上只是复制字符串头（指针/长度对），而不是复制内容。100000个字符串头的复制容量仍然不足2MB，与您正在处理的其他数据量相比，这不是什么大问题。

容器/list在微基准测试中对我来说慢了3倍；当然，链表append也是常量时间，但我认为append具有较低的常量，因为它通常只能写入内存中的几个单词不分配列表项等。计时代码在操场上不起作用，但你可以在本地复制并运行它来查看自己：http://play.golang.org/p/uYyMScmOjX

有时，您可以有效地预分配空间以避免重新分配/复制（在本例中，使用make（[]字符串，0, 1000000)将运行时间从~77ms缩短到~10ms），但是，当然，通常情况下您没有足够的信息关于预期的数据大小等等来维持有价值的收益，你最好把它留给内置的算法。

但是您在这里提出了一个关于类grep的应用程序的更具体的问题（感谢您在上下文中提出了一个详细的问题）。对于这一点，最基本的建议是，如果您正在搜索GIG的日志，那么最好避免在RAM中缓冲整个输出。

您可以编写一些东西将结果作为单个函数进行流式处理：logparser。Grep（in-io.Reader，out-io.Writer，patterns[]regexp.regexp）；如果您不希望发送结果的代码与grep代码过于纠缠，您也可以将outachan[]byte或func（match[]byte）（err error）。

（在[]bytevs.string上：一个[]byte似乎在这里完成了这项工作，并避免了[]byte

如果您将整个匹配列表保留在RAM中，请注意，保留对大字符串或字节片的部分引用可以防止整个源字符串/片被垃圾收集。所以，如果您这样做，那么您可能会违反直觉地希望复制匹配项，以避免将所有源日志数据保留在RAM中。