将一个小数组排序后合并到一个已排序的大数组中。

Question

将一个小数组排序后合并到一个已排序的大数组中。

algorithmperformancesortingoptimizationlanguage-agnostic

4

最佳算法是什么，用于合并一个大的排序数组和一个小的未排序数组？

我将从我的特定用例中给出示例，但不要受限于它们：我主要是试图让您了解这个问题。

8 MB排序数组与92 kB未排序数组（缓存内排序）
2.5 GB排序数组与3.9 MB未排序数组（内存排序）
34 GB排序数组与21 MB未排序数组（out-of-memory排序）

- Charles

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jérôme Richard · Accepted Answer

你可以实现一个基于块的算法来高效解决这个问题（无论数组的输入大小如何，只要其中一个比另一个小得多）。

首先，您需要对小数组进行排序（如果不需要自定义比较器，则可以使用基数排序或双调排序）。然后，将大数组划分为完全适合CPU缓存的块（例如256 KiB）。对于每个块，使用二进制搜索找到小数组中最后一个项目的索引<=块的最后一个项目。这相对较快，因为小数组可能适合缓存，并且如果数组很大，则在连续块之间提取二进制搜索的相同项。此索引使您能够知道有多少项需要与块合并才能写入。对于要合并到块中的每个值，请在块中使用二进制搜索找到该值的索引。这很快，因为块适合缓存。一旦您知道要插入块中的值的索引，就可以有效地按块移动每个块中的项目（可能从末尾到开头原地）。这种实现比传统合并算法要快得多，因为由于二进制搜索和每个块要插入的数量较少，所需的比较次数要小得多。

对于相对较大的输入，您可以使用并行实现。其思想是同时处理一组多个块（即超级块）。超级块比传统块大得多（例如>= 2 MiB）。每个线程一次处理一个超级块。在小数组上执行二分搜索以知道每个超级块中插入了多少个值。该数字在线程之间共享，因此每个线程都知道它可以独立地写入输出的位置，而不受其他线程的影响（可以在高度并行的架构上使用并行扫描算法来执行此操作）。然后将每个超级块分成经典块，并在每个线程中独立地使用先前的算法来解决问题。当小输入数组不适合缓存时，该方法甚至在顺序上应该更有效率，因为整个小数组中的二分搜索操作数量将显着减少。

该算法的（摊销）时间复杂度为O(n (1 + log(m) / c) + m (1 + log(c)))，其中m是大数组的长度，n是小数组的长度，c是块大小（为了清晰起见，超级块在此被忽略，但它们只像常数因子c一样改变复杂度）。 替代方法/优化：如果您的比较运算符简单且可以使用SIMD指令进行向量化，则可以优化传统的合并算法。传统方法由于分支（在一般情况下很难预测）以及不能轻松/高效地进行向量化而相当缓慢。然而，由于大数组比小数组大得多，传统算法将从大数组中挑选许多连续值，这些连续值在小数组的值之间。这意味着您可以选择大数组的SIMD块，并将其与小数组中的一个值进行比较。如果所有SIMD项都小于从小数组中选择的项，则可以非常高效地一次写入整个SIMD块。否则，您需要写入SIMD块的一部分，然后写入小数组的项并切换到下一个项。这最后一个操作显然不太有效，但应该很少发生，因为小数组比大数组小得多。请注意，小数组仍然需要先进行排序。