排序数据大于RAM大小

这是一个Google面试问题：给定2台机器，每台机器有64 GB RAM，包含所有整数（8字节），对整个128 GB数据进行排序。您可能会承担少量额外的RAM。将其扩展为对存储在1000台机器中的数据进行排序。排序数据大于RAM大小

我想出了外部排序。在这里，我们将整个数据分成块，并使用合并排序。这是第一次将这些块分类并将它们放回原处，并将它们重新合并并合并它们。有没有更好的办法？什么是复杂性？

2011-12-21 princess of persia

拆分它，remerge。是否可以避免单台机器进行最终合并？是：基数排序。 – wildplasser 2016-12-25 23:23:47

@wildplasser - 没关系。合并比外部I/O更快，因此合并过程仅限于将128GB数据写入目标驱动器所需的时间。对于n + 1设备，可以使用n路合并写入剩余的驱动器。这将允许n台机器并行地在n个工作驱动器上创建n个数据块，但最终的合并受限于目标驱动器的I/O速度。 – rcgldr 2016-12-25 23:28:00

你*可以*认为共享文件系统是一台（单个）机器。这仍然是一个漏斗锁。 – wildplasser 2016-12-26 00:32:48

64 GB中的每一个都可以分别使用快速排序进行排序，然后在两个64GB阵列的头部使用外部存储器保持指针，让我们考虑我们希望RAM1和RAM2按顺序具有整个数据，保持递增如果RAM1的指针小于RAM2的指针值，则将其与RAM2交换直到指针到达RAM1的末尾。

采用相同的概念对所有N个RAM进行排序。采取对他们和使用上述方法排序。你剩下的N/2排序RAM。递归地使用上述相同的概念。

来源

2011-12-21 06:15:42 FUD

在每次递归中采用一对机器的算法是什么？ – Dialecticus 2011-12-21 13:39:57

ChingPing为每个子集提出一个O（n log n）排序，然后进行线性合并（通过交换元素）。 Quicksort的问题（以及大多数n log n的问题是，它们需要n个内存，我建议改为使用使用常量内存的SmoothSort，仍然运行在O（n log n）

最差的的情况是，你有这样的事情：

setA = [maxInt .. 1] 
setB = [0..minInt]

，其中两套是反向排列，但随后的合并是按照相反的顺序

的 - ChingPing的解决方案（IMO更清晰）的解释是：

Have a pointers 'pointerA', 'pointerB' initialized at the beginning of each array 
While setA's pointer is not at the end 
    if (setA[pointerA] < setB[pointerB]) 
    then { pointerA++; } 
    else { swap(setA[pointerA], setB[pointerB]); pointerB++; }

这两套应该现在被排序。

来源

2011-12-21 14:54:32 Noxville

'快速排序的问题[是]需要n个内存 - [甚至不需要_情况_，参见Sedgewick变体]（https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms）（排序非更大的分区第一）。 – greybeard 2016-12-25 19:09:41

通过交换元素的线性合并似乎不起作用。考虑这种情况，setA = {0,1,6,7}，setB = {2,3,4,5}。线性合并后，结果为setA = {0,1,2,3}，setB = {6,7,4,5}。问题是，如果setA中的元素> setB中的元素，则需要类似于setB上的插入排序的东西，其中O（n^2）。 – rcgldr 2016-12-26 02:33:53

已经有2机箱的答案。

我假设将要排序的128GB数据作为单个文件存储在单个硬盘驱动器（或任何外部设备）上。无论使用多少台机器或硬盘，读取原始128GB文件和写入排序的128GB文件所需的时间都保持不变。在基于内部ram的排序中，唯一的节省是创建大量的排序数据。将n + 1个硬盘合并为一个单独排序的128GB文件到另一个硬盘上所需的时间再次保持不变，这受限于将128GB排序文件写入剩余硬盘所花费的时间硬盘。

对于n台机器，数据将被拆分为128GB/n块。每台机器可以交替读取子块（一次可能为64MB），以减少随机访问开销，以便“最后”机器不会等待所有先前的机器在其启动之前读取其所有块。

对于n台机器（每个64GB ram）和n + 1个硬盘，n> = 4，每个机器可以使用一个时间复杂度为O（n）的基数排序在n个工作中创建32GB或更小的块硬盘驱动器，然后通过n路合并到目标硬盘上。

有一个收益递减的限制大n的好处。在n> 16以上的某处，内部合并吞吐量可能会大于磁盘I/O带宽。如果合并进程是cpu绑定而不是I/O绑定，那么在并行创建块的时间与大于I/O时间的合并开销之间存在cpu开销的折衷。

来源

2016-12-25 22:25:30 rcgldr

据我了解问题，我们不应该使用硬盘驱动器，并且要排序的数据总量是* n * \ * 64 GB，其中* n *是机器数量。 – ruakh 2016-12-25 23:34:08

@ruakh - 如果每台机器都有64GB，那么在排序存储之前和之后的128GB数据在哪里？ – rcgldr 2016-12-25 23:35:56

排序前：在主机间任意分配。排序后：在主机中分配。 – ruakh 2016-12-25 23:43:48

排序数据大于RAM大小

回答

相关问题