1

好的，假设我们有100 billion需要排序的项目。

我们的内存足以容纳这些项目。

我们还可以使用 List.sort（合并排序）对它们进行排序吗？

我的担忧有两个部分：

  1. 在这种情况下，需要的额外空间是否会mergesort成为问题？
  2. 由于我们使用不可变的数据结构，在排序过程中我们必须重复为100 billion项目创建新的列表，这会成为一个缺点吗？在性能方面？

对于排序100 billion项目，我应该array在这种情况下使用吗？

4

1 回答 1

2

标准的合并排序实现很聪明，不会重新分配太多内存（一开始的分成两半不会分配新内存）。给定一个输入的nconses 列表，它将在最坏的情况下分配n * log(n)列表 conses（具有基本相同的最佳情况）。鉴于元素本身的值将在输入、中间和输出列表之间共享，因此您将仅通过列表 cons 分配 3 个单词，这意味着该排序将3 * n * log(n)总共分配内存中的单词（对于n = 100 billion, 3 * log(n)is 110，这是相当一个巨大的常数因子）。

另一方面，垃圾收集可以收集一些内存：最坏情况下的内存使用是总的活动内存，而不是总分配的内存。事实上，在log(n)递归子调用层中构建的中间列表可以在返回任何结果之前收集（它们以与最终merge分配新单元格相同的速率死亡），因此该算法n在最坏的情况下保留额外的活动 cons 单元格，这仅表示3*n字或24*n字节。对于n = 100 billion，这意味着 2.4 TB 的额外内存，与您最初存储输入列表的脊椎所需的内存一样多。

最后，如果您不保留对输入列表本身的引用，则可以在排序后立即收集它的前半部分，从而为您提供n/2最坏情况的界限而不是n. 并且您可以在对前半部分进行排序时收集前半部分的前半部分，从而为您提供n/4最坏情况的界限，而不是n/2. 以这种推理达到极限，我相信通过足够的 GC 工作，您实际上可以完全对列表进行排序 - 为 stop© 第一代 GC 模一些恒定大小的内存池，其大小将影响时间性能算法。

于 2013-03-11T13:51:18.487 回答