如何計算就地外部合併排序的時間？

原始問題如下：
您將排序1PB大小的整數範圍從-2^31〜2^31 - 1（int），您有1024臺機器，每臺機器具有1TB磁盤空間和16GB內存空間。假設磁盤速度爲128MB/s（r/w），內存速度爲8GB/s（r/w）。 CPU的時間可以忽略。爲簡單起見，網絡傳輸時間可以忽略。計算所需的近似時間。如何計算就地外部合併排序的時間？

我知道與外部排序，我們可以在大致10小時作爲計算這樣一臺機器上的1TB的數據進行排序：

磁盤訪問（2r2w）：1T * 4/128MB/S = 2^15秒〜 9小時
存取訪問：
排序2^48 64個部分（每個2^42）的整數大概每個需要1.3分鐘。所以總共1.4小時。
63路合併需要幾秒鐘，因此被忽略。

但是下一步怎麼樣：1024T數據的組合？我不知道這是如何計算的。請幫忙嗎？

來源

2013-02-27 NSF

1位32位整數表示您有2^48整數，而不是2^38。 – NovaDenizen 2013-02-27 01:17:37

@NovaDenizen好的。糾正。 – NSF 2013-02-27 01:22:21

2^31 = 20億（2「giga」）。所以你正在看很多重複的數字和固定的範圍。所以考慮基底排序（http://en.wikipedia.org/wiki/Radix_sort）。

每個處理器，對於od數據子集）創建'count'數組（x [0]包含0等的計數）。然後你可以將所有結果合併成一個數組。稍後，您可以「構建」已排序的數組。

來源

2013-02-27 01:20:41 ElKamina

那麼如果範圍是2^64呢？是的你是對的，但實際上我正在尋找一種使用外部合併排序的解決方案。 – NSF 2013-02-27 01:26:58

@NSF這是一個面試問題還是一個真正的實際問題？如果這是一個面試問題，數字（1peta，1 tera，範圍等）的設置方式暗示一個特定的解決方案。換言之，如果範圍是2^64而不是2^31，解決方案將會大不相同。 – ElKamina 2013-02-27 18:10:50

當我遇到網絡時發現一個面試問題 – NSF 2013-02-27 19:15:14

如何計算就地外部合併排序的時間？

回答

相關問題