排序數據大於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大小

回答

相關問題