时间戳

首页 > 解决方案 > 在 Go 中处理大量数据时使用切片而不是列表

go - 在 Go 中处理大量数据时使用切片而不是列表

问题描述

我对 Go 中切片的实用性有疑问。我刚刚看到了为什么在 Go 中很少使用列表？为什么使用数组而不是切片？但有一些我没有看到在那里回答的问题。

在我的应用程序中：

我更喜欢列表而不是切片的原因是由于数组/切片需要大量的连续内存。另外，由于我不知道文件中确切记录数的大小，因此我无法预先指定数组大小（我知道 Go 可以根据需要动态地重新调整切片/数组的大小，但这似乎非常糟糕对于如此庞大的数据集效率低下）。

我阅读的每一篇 Go 教程或文章似乎都建议我应该使用切片而不是列表（因为切片可以完成列表可以做的所有事情，但以某种方式做得更好）。但是，我不明白切片如何或为什么对我的需要更有帮助？任何人的任何想法？

标签： golinked-listslice

解决方案

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

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

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

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

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

如果您使用切片，并且每次都分配一个额外的切片条目，则从 none 开始，将其增长到大小 1，然后将 1 复制到大小为 2 的新数组并填充项目 #2，将其增长到大小 3并填写第 3 项，依此类推。n 个实体中的第一个被复制n次，第二个被复制n -1 次，依此类推，对于n ( n +1)/2 = O(n 2 ) 个副本。但是如果你使用乘法扩展技术——Go 的append实现就是这样做的——这将减少到 O(log n ) 个副本。虽然每个都复制更多字节。它最终是 O( n )，摊销（见为什么动态数组必须以几何方式增加它们的容量才能获得 O(1) 摊销的 push_back 时间复杂度？）。

切片使用的空间显然是 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 MB。（Go 的container/list实现使用双向链表，在 64 位机器上，这是所需的每个元素线程的大小。）

不过，我们一开始会得到一些不太明显的东西，而且它是巨大的。因为 Go 是一种垃圾收集语言，所以每个指针都是 GC 必须在不同时间检查的东西。 切片方法每条记录有零个额外指针；链表方法有两个. 这意味着 GC 系统可以避免检查不存在的 2000 万个指针（在 1000 万条记录中）。

结论

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

推荐阅读