将小数组排序为大排序数组

Question

将一个大的排序数组与一个小的未排序数组合并的最佳算法是什么？

我将从我的特定用例中给出我所指的例子，但不要感到被它们所束缚:我主要是想对问题有一种感觉。

带92 kB未排序数组的8MB排序数组(缓存中排序)

2.5GB排序数组，包含3.9MB未排序数组(内存中排序)

带21 MB未排序数组的34 GB排序数组(内存不足排序)

Answer 1

您可以实现一个基于块的算法来有效地解决这个问题(只要一个比另一个小得多，不管数组的输入大小如何)。

首先，您需要对小数组进行排序(如果不需要自定义比较器，则可能使用基排序或双声速排序)。然后，想法是切割大数组块完全适合CPU缓存(例如。2 5 6 KiB)。对于每个块，使用二进制搜索将小数组<=中的最后一个项的索引查找到块的最后一个项。这是相对较快的，因为小数组可能适合缓存，如果数组很大，二进制搜索的相同项将在连续块之间获取。此索引使您能够知道在写入之前需要与块合并多少项。对于要合并到块中的每个值，请使用块中的二进制搜索找到值的索引。这是快速的，因为块适合缓存。一旦您知道了要插入到块中的值的索引，就可以在每个块中逐个地有效地移动该项(可能是从结束到开始)。这个实现比传统合并算法快得多，因为由于二进制搜索和块要插入的条目数量少，所以所需的比较数量要小得多。

对于相对较大的输入，可以使用并行实现。这个想法是同时处理一组多块(即。超级块)。超级块比经典的要大得多。( >=2 MiB)。每个线程一次工作在一个超级块上。在小数组上执行二进制搜索，以知道每个超级块中插入了多少个值。这个数字在线程之间共享，这样每个线程都知道它可以在哪里安全地写入输出，而不依赖于其他线程(可以使用并行扫描算法在大规模并行架构上这样做)。然后将每个超级块分割成经典块，并使用前面的算法独立地解决每个线程中的问题。当小输入数组不适合缓存时，这种方法即使在顺序上也应该更有效，因为整个小数组中的二进制搜索操作将大大减少。

算法的(摊销)时间复杂度是O(n (1 + log(m) / c) + m (1 + log(c)))，m是大数组的长度，n是小数组的长度，c是块的大小(为了清晰起见，这里忽略了超级块，但它们只以常数c那样的常数因子改变了复杂度)。

替代方法/优化:如果您的比较操作符很便宜，并且可以使用SIMD指令进行矢量化，那么您可以优化传统的合并算法。传统的方法由于分支(在一般情况下很难预测)很慢，也因为它不容易/有效地矢量化。然而，由于大阵列比小阵列大得多，传统的算法会在小阵列之间从大数组中选取大量的连续值。这意味着您可以选择大数组的SIMD块，并将值与一个小数组进行比较。如果所有SIMD项都小于从小数组中选择的项，那么您可以一次非常有效地编写整个SIMD块。否则，您需要编写SIMD块的一部分，然后编写小数组的项并切换到下一个。最后一次操作显然效率较低，但应该很少发生，因为小数组比大数组小得多。注意，小数组仍然需要先排序。