在 Go 中处理大量数据时使用切片而不是列表
Using a slice instead of list when working with large data volumes in Go
我对 Go 中切片的实用性有疑问。我刚刚看到 Why are lists used infrequently in Go? and ，但有一些问题在那里我没有看到答案。
在我的申请中：
- 我读取了一个包含大约 1000 万条记录的 CSV 文件，每条记录有 23 列。
- 对于每条记录，我创建一个结构并将其放入链表中。
- 读取完所有记录后，其余的应用程序逻辑将使用此链表（处理逻辑本身与此问题无关）。
我更喜欢列表而不是切片的原因是 array/slice 需要大量的连续内存。另外，由于我事先不知道文件中记录的确切数量的大小，所以我无法预先指定数组大小（我知道 Go 可以根据需要动态地重新确定 slice/array 的尺寸，但这对于如此大的数据集来说，效率似乎非常低）。
我阅读的每篇 Go 教程或文章似乎都建议我应该使用切片而不是列表（因为切片可以做列表可以做的所有事情，但不知何故做得更好）。但是，我不明白切片如何或为什么对我的需要更有帮助？任何人有什么想法吗？
... approx 10 million records, with 23 columns per record ... The reason I prefer a list and not a slice is due to the large amount of contiguous memory an array/slice would need.
这种连续内存既有优点也有缺点。让我们考虑这两个部分。
（请注意，也可以使用混合方法：块列表。不过，这似乎不太值得。）
Also, since I don't know the size of the exact number of records in the file upfront, I can't specify the array size upfront (I know Go can dynamically re-dimension the slice/array as needed, but this seems terribly inefficient for such a large set of data).
显然，如果有 n 条记录，并且您分配并填写每条记录一次（使用列表），这是 O(n).
如果您使用切片，并且每次分配一个额外的切片条目，您从 none 开始，将其增长到大小 1，然后将 1 复制到大小为 2 的新数组并填充第 2 项，将其增大到 3 号并填充第 3 项，依此类推。 n 个实体中的第一个被复制 n 次，第二个被复制 n-1 次，依此类推，对于 n(n+1)/2 = O(n2) 份.但是如果你使用乘法扩展技术——Go 的 append 实现就是这样做的——这会下降到 O(log n) 个副本。虽然每个人都复制了更多的字节。它最终是 O(n)，摊销（见 ）。
与切片一起使用的space显然是O(n)。用于 linked 列表方法的 space 也是 O(n) （尽管记录现在至少需要一个前向指针，所以你需要一些额外的space 每条记录）。
因此，就构建数据所需的时间以及保存数据所需的space而言，无论哪种方式都是 O(n) 。您最终会得到相同的总内存需求。无论如何，乍一看，主要区别在于 linked-list 方法不需要 连续 内存。
那么：使用连续内存时，我们失去什么，获得什么？
我们失去了什么
我们失去的东西是显而易见的。如果我们已经有碎片内存区域，我们可能无法 能够 获得正确大小的连续块。即，给定：
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 程序倾向于 运行 在大内存 space 机器上的虚拟内存中（虚拟大小为 64 GB 或更多），这往往不是一个大问题。当然，每个人的情况都不同，所以如果您真的 是 VM 约束，那才是真正的问题。 （其他语言有压缩 GC 来处理这个问题，未来的 Go 实现至少在理论上可以使用压缩 GC。）
我们的收获
第一个收获也很明显：我们不需要每条记录中的指针。这节省了一些 space——确切的数量取决于指针的大小，我们是否使用单独的 linked 列表，等等。让我们假设 2 个 8 字节指针，或每条记录 16 个字节。乘以 1000 万条记录，我们在这里看起来相当不错：我们已经节省了 160 MB。 （Go 的 container/list 实现使用双重 linked 列表，在 64 位机器上，这是每个元素线程所需的大小。）
虽然一开始我们得到了一些不太明显的东西，但它巨大。因为 Go 是一种垃圾收集语言，每个指针都是 GC 必须在不同时间检查的东西。切片方法每个记录 零额外指针 ; linked-list 方法有两个。这意味着 GC 系统可以避免检查 none 现有的 2000 万个指针（在 1000 万条记录中）。
结论
有 次使用 container/list。如果你的算法真的需要一个列表，并且这样更清晰，那么就这样做，除非并直到它在实践中被证明是一个问题。或者，如果您有可以在某些列表集合上的项目——实际上共享的项目，但其中一些在 X 列表上，一些在 Y 列表上，还有一些在两个列表上——这需要列表样式容器。但是，如果有一种简单的方法可以将某些内容表示为列表 或 切片，请先使用切片版本。因为切片内置于 Go 中，所以您还可以获得第一个 link (Why are lists used infrequently in Go?).
中提到的类型安全/清晰度
我对 Go 中切片的实用性有疑问。我刚刚看到 Why are lists used infrequently in Go? and
在我的申请中：
- 我读取了一个包含大约 1000 万条记录的 CSV 文件，每条记录有 23 列。
- 对于每条记录，我创建一个结构并将其放入链表中。
- 读取完所有记录后，其余的应用程序逻辑将使用此链表（处理逻辑本身与此问题无关）。
我更喜欢列表而不是切片的原因是 array/slice 需要大量的连续内存。另外，由于我事先不知道文件中记录的确切数量的大小，所以我无法预先指定数组大小（我知道 Go 可以根据需要动态地重新确定 slice/array 的尺寸，但这对于如此大的数据集来说，效率似乎非常低）。
我阅读的每篇 Go 教程或文章似乎都建议我应该使用切片而不是列表（因为切片可以做列表可以做的所有事情，但不知何故做得更好）。但是，我不明白切片如何或为什么对我的需要更有帮助？任何人有什么想法吗？
... approx 10 million records, with 23 columns per record ... The reason I prefer a list and not a slice is due to the large amount of contiguous memory an array/slice would need.
这种连续内存既有优点也有缺点。让我们考虑这两个部分。
（请注意，也可以使用混合方法：块列表。不过，这似乎不太值得。）
Also, since I don't know the size of the exact number of records in the file upfront, I can't specify the array size upfront (I know Go can dynamically re-dimension the slice/array as needed, but this seems terribly inefficient for such a large set of data).
显然，如果有 n 条记录，并且您分配并填写每条记录一次（使用列表），这是 O(n).
如果您使用切片，并且每次分配一个额外的切片条目，您从 none 开始，将其增长到大小 1，然后将 1 复制到大小为 2 的新数组并填充第 2 项，将其增大到 3 号并填充第 3 项，依此类推。 n 个实体中的第一个被复制 n 次，第二个被复制 n-1 次，依此类推，对于 n(n+1)/2 = O(n2) 份.但是如果你使用乘法扩展技术——Go 的 append 实现就是这样做的——这会下降到 O(log n) 个副本。虽然每个人都复制了更多的字节。它最终是 O(n)，摊销（见
与切片一起使用的space显然是O(n)。用于 linked 列表方法的 space 也是 O(n) （尽管记录现在至少需要一个前向指针，所以你需要一些额外的space 每条记录）。
因此，就构建数据所需的时间以及保存数据所需的space而言，无论哪种方式都是 O(n) 。您最终会得到相同的总内存需求。无论如何，乍一看，主要区别在于 linked-list 方法不需要 连续 内存。
那么：使用连续内存时，我们失去什么，获得什么？
我们失去了什么
我们失去的东西是显而易见的。如果我们已经有碎片内存区域，我们可能无法 能够 获得正确大小的连续块。即，给定：
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 程序倾向于 运行 在大内存 space 机器上的虚拟内存中（虚拟大小为 64 GB 或更多），这往往不是一个大问题。当然，每个人的情况都不同，所以如果您真的 是 VM 约束，那才是真正的问题。 （其他语言有压缩 GC 来处理这个问题，未来的 Go 实现至少在理论上可以使用压缩 GC。）
我们的收获
第一个收获也很明显：我们不需要每条记录中的指针。这节省了一些 space——确切的数量取决于指针的大小，我们是否使用单独的 linked 列表，等等。让我们假设 2 个 8 字节指针，或每条记录 16 个字节。乘以 1000 万条记录，我们在这里看起来相当不错：我们已经节省了 160 MB。 （Go 的 container/list 实现使用双重 linked 列表，在 64 位机器上，这是每个元素线程所需的大小。）
虽然一开始我们得到了一些不太明显的东西，但它巨大。因为 Go 是一种垃圾收集语言，每个指针都是 GC 必须在不同时间检查的东西。切片方法每个记录 零额外指针 ; linked-list 方法有两个。这意味着 GC 系统可以避免检查 none 现有的 2000 万个指针（在 1000 万条记录中）。
结论
有 次使用 container/list。如果你的算法真的需要一个列表，并且这样更清晰，那么就这样做，除非并直到它在实践中被证明是一个问题。或者，如果您有可以在某些列表集合上的项目——实际上共享的项目，但其中一些在 X 列表上，一些在 Y 列表上，还有一些在两个列表上——这需要列表样式容器。但是，如果有一种简单的方法可以将某些内容表示为列表 或 切片，请先使用切片版本。因为切片内置于 Go 中，所以您还可以获得第一个 link (Why are lists used infrequently in Go?).