高效追加到字符串（Golang）

问题的一个可变长度的容器：高效追加到字符串（Golang）

我需要多个正则表达式应用到大的日志文件中的每一行（如几个GB长），收集非空的比赛和把它们全部放在一个数组中（用于序列化并通过网络发送）。

片都没有太大的帮助，如果回答this question认为：

如果切片不具备足够的能力，追加需要分配新的内存，并复制旧的了。对于具有< 1024个元素的切片，其将使容量加倍，对于具有> 1024个元素的切片，它会将其增加1.25倍。

由于可以从字面上成千上万的正则表达式匹配，我不能真正预测切片的长度/容量。如果内存分配器足够聪明，不会分配太多没有写入的内存，也许我可以使用巨大的分片容量没有太大的伤害？）。

所以我在考虑以下选择：

有匹配的双向链表（http://golang.org/pkg/container/list/）
计算它的长度（？会len()工作）
预分配的这片容量
复制串指向这片

是否有更少的劳动力在Go中实现这个目标的方法（追加〜O（1）追加复杂度）？

（这里当然golang新手）

来源

2013-11-27 LetMeSOThat4U

append()的平均（摊销）成本已经是O（1），因为它的增长由每个时间的百分比的阵列。随着阵列变大，增长越来越昂贵，但比例更少。 10M物品切片比1M物品切片成本高出10倍，但由于我们分配的额外容量与大小成正比，因此它将成为许多append(slice, item)调用的10倍，直到下一次增长。重新分配的成本增加和频率下降被抵消，使平均成本保持不变，即O（1）。例如，微软的std::vector实现显然每次都会将数组增长50％。此外，微软的std::vector实现也可以使数组增长50％。已摊销的O（1）并不意味着您不会为分配支付任何费用，只是您继续以与阵列变大的平均费率相同的价格付款。

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

container/list对于我来说，在微基准测试中慢了3倍;链接列表追加也是恒定的时间，当然，但我想append有一个较低的常量，因为它通常可以写入一对单词的内存，而不是分配一个列表项等。时间码将无法在游乐场但你可以在本地复制此并运行它看到自己：http://play.golang.org/p/uYyMScmOjX

但是你在这里问一个更具体的问题有关grep样的应用程序（和感谢要求具有上下文的详细问题）。为此，底线建议是，如果您搜索日志的演出，最好避免在RAM中缓冲整个输出。

你可以写一些东西来将结果作为单个函数进行流式传输：logparser.Grep(in io.Reader, out io.Writer, patterns []regexp.Regexp);如果您不希望发送结果的代码与grep代码过于紧密结合，您可以选择使out为chan []byte或func(match []byte) (err error)。

（在[]byte对比string：一个[]byte似乎在这里做的工作，避免[]byte < =>string转换，当你做I/O，所以我宁愿我不知道你”。再这样做，不过，如果你需要string它的罚款。）

如果做保持在RAM中的整体匹配列表，要知道，围绕基准保持一个大的字符串或字节片的一部分保持整个源字符串/切片被垃圾收集。所以如果你走这条路线，那么违反直觉，你实际上可能会想要复制匹配，以避免将所有的源日志数据保存在RAM中。

来源

2013-11-27 21:02:44 twotwotwo

鉴于数据TB的容量来处理我有限制的行数在一个运行扫描（原因应该是显而易见的：平均保持在I/O负载，CPU负载和驻留集大小，即防止大负荷峰），所以我不必真的流。但是更重要的是，我不明白你的意思，如果我溢出1M行，下一个操作将不会是1.25M行分配+复制1M行？请参阅下一个计算评论。 – LetMeSOThat4U

在Python中：a = 1; cumul = 0。然后'因为我在范围内（10）：print'rows％.2f cumul％.2f'％（a，cumul），; cumul + = a; A = A * 1.25'。结果：行1.00累积0.00行1.25累积1.00行1.56累积2.25行1.95累积3.81行2.44累积5.77行3.05累积8.21行3.81累积11.26行4.77累积15.07行5.96累积19.84行7.45累积25.80。因此，如果我从1M行切片开始，并且有800万个匹配需要复制切片10次，并复制总计25M行。与链接列表相比，这不是一个非常好的成本.. – LetMeSOThat4U

我认为一段字符串在内部是一个指向字符串的指针切片，从某种意义上说，扩展切片不会真正复制字符串，只是指向字符串，因此每个条目都是4或8个字节（取决于系统架构），所以它应该很快。 – siritinga

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

由于可以进行“数十万次正则表达式匹配”，因此我为matches切片容量做了1 M（1024 * 1024）条目的大规模初始分配。切片是一种参考类型。片头“struct”具有长度，容量和指针，在64位操作系统上共有24（3 * 8）个字节。因此，1M条目片的初始分配仅为24（24 * 1）MB。如果有超过1M个条目，则将分配一个容量为1.25（1 + 1/4）M个条目的新条带，并将现有1M条带头条目（24 MB）复制到它。

总之，通过最初分配切片容量，可以避免很多append的开销。更大的内存问题是每次比赛保存和引用的所有数据。 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 
     } 
    } 
}

来源

2013-11-28 20:01:32 peterSO

高效追加到字符串（Golang）

回答

相关问题