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

Question

问题：我需要将多个正则表达式应用于大日志文件的每一行（如几 GB 长），收集非空匹配项并将它们全部放入一个数组中（用于序列化并通过网络发送）。如果这个问题的答案成立，切片没有多大帮助：如果切片没有足够的容量，则 append 将需要分配新内存并复制旧内存。对于 <1024 个元素的切片，它将使容量加倍，对于具有 >1024 个元素的切片，它将增加 1.25 倍。由于实际上可能有数十万个正则表达式匹配，因此我无法真正预测切片的长度/容量。我不能让它太大或者“以防万一” bc 这会浪费内存（或者会吗？如果内存分配器足够聪明，不会分配太多未写入的内存，也许我可以使用巨大的切片容量没有太大的伤害？）。所以我正在考虑以下替代方案：有一个双向链接的匹配列表（http://golang.org/pkg/container/list/）计算它的长度（会len()起作用吗？）预分配此容量的一部分将字符串指针复制到此切片在 Go 中是否有一种不那么费力的方法来实现这个目标（追加 ~ O(1) 追加复杂度）？（当然这里是 golang 新手）

Answer 1

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

由于可能有“数十万个正则表达式匹配”，我为matches切片容量做了大量的初始分配 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) 复制到其中。

总之，您可以append通过最初过度分配切片容量来避免 many s 的大部分开销。更大的内存问题是为每个匹配保存和引用的所有数据。更大的 CPU 时间问题是执行regexp.FindAll's所花费的时间。

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

        }

    }

}