在 Go 中处理大型数据卷时使用切片而不是列表

Question

我有一个关于切片在Go中的效用的问题。我刚刚看到为什么列表在Go中很少使用？和为什么使用数组而不是切片？但是有一些问题我没有看到答案。在我的应用程序中：我读取了一个包含大约1000万条记录的CSV文件，每条记录有23列。对于每条记录，我创建一个结构并将其放入链表中。读取完所有记录后，应用程序逻辑的其余部分将使用此链接列表（处理逻辑本身与此问题无关）。我更喜欢列表而不是切片的原因是数组/切片需要大量的连续内存。另外，由于我不知道文件中确切的记录数的大小，因此我无法预先指定数组大小（我知道Go可以根据需要动态地重新调整切片/数组的尺寸，但对于如此庞大的数据集，这似乎非常低效）。我读过的每篇Go教程或文章似乎都建议我应该使用切片而不是列表（因为切片可以完成列表可以做的所有事情，但以某种方式做得更好）。但是，我不明白切片如何或为什么对我的需求更有帮助？任何人有什么想法吗？

Answer 1

...大约1000万条记录，每条记录23列...我更喜欢列表而不是切片的原因是数组/切片需要大量的连续内存。

这种连续的记忆是它自己的优点，也是它自己的缺点。让我们考虑这两个部分。

（请注意，也可以使用混合方法：块列表。不过，这似乎不太可能非常值得。

另外，由于我不知道文件中确切的记录数的大小，因此我无法预先指定数组大小（我知道Go可以根据需要动态地重新调整切片/数组的尺寸，但对于如此庞大的数据集，这似乎非常低效）。

显然，如果有 n 条记录，并且您分配并填写每条记录一次（使用列表），则为 O（n）。

如果使用切片，并且每次都分配一个额外的切片条目，则从 none 开始，将其增大到大小 1，然后将 1 复制到大小为 2 的新数组并填充项目 #2，将其增大到大小 3 并填充项目 #3，依此类推。对于 n（n+1）/2 = O（n ^{2） 个}副本，n 个实体中的第一个被复制 n 次，第二个实体被复制 n-1 次，依此类推。但是，如果您使用乘法扩展技术（Go的实现确实如此），则会下降到O（log n）副本。不过，每个都会复制更多的字节。它最终是O（n），摊销（请参阅为什么动态数组必须几何地增加其容量以获得O（1）摊销push_back时间复杂度？）。append

与切片一起使用的空间显然是O（n）。用于链表方法的空间也是 O（n）（尽管记录现在至少需要一个正向指针，因此每条记录需要一些额外的空间）。

因此，就构造数据所需的时间以及保存数据所需的空间而言，无论哪种方式都是O（n）。您最终会得到相同的总内存要求。无论如何，乍一看，主要区别在于链表方法不需要连续内存。

那么：使用连续记忆时，我们会失去什么，我们会得到什么？

我们失去什么

我们失去的东西是显而易见的。如果我们已经有碎片化的内存区域，我们可能无法获得正确大小的连续块。也就是说，给定：

used: 1 MB (starting at base, ending at base+1M)
free: 1 MB (starting at +1M, ending at +2M)
used: 1 MB (etc)
free: 1 MB
used: 1 MB
free: 1 MB

我们总共有6 MB，3个已使用，3个免费。我们可以分配 3 个 1 MB 块，但我们不能分配一个 3 MB 块，除非我们能以某种方式压缩三个“已使用”区域。

由于Go程序倾向于在大内存空间计算机（虚拟大小为64 GB或更大）的虚拟内存中运行，因此这往往不是一个大问题。当然，每个人的情况都不同，所以如果你真的受到VM的限制，这是一个真正的问题。（其他语言有压缩GC来处理这个问题，未来的Go实现至少在理论上可以使用压缩GC。

我们收获什么

第一个增益也很明显：我们不需要每条记录中的指针。这样可以节省一些空间 - 确切的数量取决于指针的大小，我们是否使用单链表等。我们假设 2 个 8 字节指针，或每条记录 16 个字节。乘以1000万条记录，我们在这里看起来相当不错：我们节省了160兆字节。（Go 的实现使用双链表，在 64 位机器上，这是所需的每个元素线程的大小。container/list

然而，我们一开始得到了一些不太明显的东西，而且是巨大的。由于 Go 是一种垃圾回收语言，因此每个指针都是 GC 必须在不同时间检查的内容。切片方法每条记录没有额外的指针;链表方法有两种。这意味着GC系统可以避免检查不存在的2000万个指针（在1000万条记录中）。

结论

有时使用 。如果你的算法真的需要一个列表，并且以这种方式更清晰，那就这样做，除非它在实践中被证明是一个问题。或者，如果您有一些项目可以位于某个列表集合中（实际上已共享的项目，但其中一些在 X 列表中，一些在 Y 列表中，一些在两者上），这需要一个列表样式的容器。但是，如果有一种简单的方法可以将某些内容表示为列表或切片，请先选择切片版本。由于切片内置于 Go 中，因此您还可以获得第一个链接中提到的类型安全性/清晰度（为什么列表在 Go 中很少使用？）。container/list