C++排序巨大的二進制文件

我需要排序大量的二進制文件，將不適合內存。使用排序算法並不斷地從I/O設備讀取/寫入是不行的。有沒有可能使用類似內存映射文件的東西？C++排序巨大的二進制文件

2011-06-18 0xbadf00d

爲什麼讀/寫連續不是一個選項？你需要隨機訪問嗎？ – Macke

正如一個粗略的想法，你可能想看看被稱爲「在線算法」。基本上，這個想法是你可以對數據進行排序，因爲你一個接一個地接收數據。例如，請參閱：http://en.wikipedia.org/wiki/Merge_sort#Utility_in_online_sorting –

回答這個問題，因爲它目前被問到：是的，有這樣的可能性。你應該問一個更好的問題。 – Dialecticus

這是一個解決的問題，因爲這wiki頁面上解釋說：http://en.wikipedia.org/wiki/External_sorting

基本上，在某些設定金額看，排序，保存到一個文件中，並重復。然後，從每個文件中讀取較小的數量，對這些數據進行排序，然後繼續執行。

UPDATE：

你可能想看看他使用的Java代碼，這聽起來像他解決了你所需要的。

2011-06-18 18:59:14

如果他們不適合內存，他們將不適合到內存中，而這幾乎是。您無法將內存映射超出內存限制 - 排序算法一次需要所有數據。

但是，您可以編寫專門的排序算法。例如，如果按字節排序，則應該能夠以塊爲單位遍歷文件，計算每個字節的出現次數，然後按順序排列它們。這也可以適用於只要有大量重複數據被發現的情況下對每個較大類型進行排序的情況。

2011-06-18 18:55:59 Puppy

一種策略是用快速排序或其他一些快速的內存排序算法的大塊它排序，然後做一個合併排序這些塊。

2011-06-18 18:56:14

其實你只需要合併這些塊，完整的合併將會是浪費。 –

@Thomas Jungblut：如果你有很多塊，你真的不想合併它們。相反，您希望以與mergesort相同的模式遞歸合併塊。 – btilly

使用內存映射文件應該可以工作。它需要適合您的地址空間（32位爲〜2Gb）或LOTS（如果是64位）。映射文件的

頁面將以/進行替換爲你訪問它們，就像虛擬交換文件，所以它應該工作。

2011-06-18 18:57:04 Macke

這可能會起作用，但您仍然需要適當選擇排序算法，以確保您不會進行大量的磁盤I/O操作。具體而言，您需要避免在文件中跳轉，而是對整個頁面進行排序，然後合併它們，這是正常的外部排序算法無論如何都會執行的操作。 –

回答