☰

在 Windows 上對極大 (800GB) 文字檔的內容進行排序

tag-icon • tag-icon windows sorting
在 Windows 上對極大 (800GB) 文字檔的內容進行排序

我有一個文字檔案每行一個字，檔案大小為800GB。我需要按字母順序對單字進行排序。

我嘗試過使用視窗 種類程式使用：

sort.exe input.txt /o output.txt

這給了錯誤：主記憶體不足，無法完成排序。

我有32GB記憶體因此，當我嘗試使用以下命令指定 10GB 記憶體進行排序時：

sort.exe input.txt /o output.txt /M 10000000

我得到：

警告：指定的記憶體大小正在減少到可用的分頁記憶體。

輸入記錄超過最大長度。指定更大的最大值。

我有什麼選擇？

答案1

我有什麼選擇？

嘗試免費軟體命令列排序實用程式 CMSort。

它使用多個臨時文件，然後在最後合併它們。

CMsort 正在讀取輸入檔的記錄，直到達到調整後的記憶體。然後記錄被排序並寫入臨時檔案。這將重複進行，直到處理完所有記錄。最後，所有臨時檔案都合併到輸出檔案中。如果可用記憶體足夠，則不會寫入臨時文件，也不需要合併。

一位用戶報告說它對 130,000,000 位元組的檔案進行了排序。

如果您想自己調整一些程式碼，也可以對巨大的文字檔案進行排序 - CodeProject- “對大小超過可用記憶體的文字檔案中的行進行排序的演算法”

答案2

另一種選擇是將文件載入到資料庫中。例如 MySQL 和 MySQL Workbench。
資料庫是處理大檔案的完美選擇。

如果您的輸入檔案僅包含由換行符號分隔的單詞，那麼這應該不會太難。

安裝資料庫和 MySQL Workbench 後，您需要執行下列操作。

首先，建立架構（這假設單字長度不會超過 255 個字符，儘管您可以透過增加參數值來更改此設定）。

第一列“idwords”是主鍵。

CREATE SCHEMA `tmp` ;

CREATE TABLE `tmp`.`words` (
  `idwords` INT NOT NULL AUTO_INCREMENT,
  `mywords` VARCHAR(255) NULL,
  PRIMARY KEY (`idwords`));

其次，導入資料。
例如，這會將所有單字匯入表中；此步驟可能需要一段時間才能完成。我的建議是首先使用較小的文件運行測試，一旦確定格式與較大的文件相同（截斷表......即清除它並加載完整的數據集）。

LOAD DATA LOCAL INFILE "C:\\words.txt" INTO TABLE tmp.words
LINES TERMINATED BY '\r\n'
(mywords);

此連結可能有助於取得適合負載的格式。 https://dev.mysql.com/doc/refman/5.7/en/load-data.html

例如，如果您需要跳過第一行，您可以執行以下操作。

LOAD DATA LOCAL INFILE "H:\\words.txt" INTO TABLE tmp.words
-- FIELDS TERMINATED BY ','
LINES TERMINATED BY '\r\n'
IGNORE 1 LINES
(mywords);

最後，儲存排序後的文件。這可能需要一段時間，具體取決於您的電腦。

SELECT tmp.words.mywords
FROM tmp.words
order by tmp.words.mywords asc
INTO OUTFILE 'C:\\sorted_words.csv';

您也可以隨意搜尋資料。
例如，這將為您提供按升序排列的前 50 個單字（從零位置或第一個單字開始）。

SELECT tmp.words.mywords
FROM tmp.words
order by tmp.words.mywords asc
LIMIT 0, 50 ;

答案3

sort

有許多演算法用於對有序和非有序文件進行排序[1]。
由於所有這些演算法都已經實現，因此選擇一個已經測試過的程式。

在核心工具 （來自 Linux，但也適用於 Windows [2]），存在sort能夠在多核心處理器下並行運行的命令：通常就足夠了。

如果你的文件是這麼大您可以協助處理分割（split -l），將檔案分成一些區塊，可能使用並行選項（--parallel），並對結果進行排序有序列與-m選項（歸併排序）。
解釋了多種方法之一這裡（分割檔案、排序單一區塊、合併排序區塊、刪除暫存檔案）。

筆記：

  • 在Windows 10中存在所謂的Linux 的 Windows 子系統其中所有的Linux 範例都會顯得更加自然。
  • 使用不同演算法進行排序具有不同的執行時間，其執行時間根據要排序的資料條目的數量而變化（O(n m )、O(nlogn)...）。
  • 演算法的效率取決於原始文件中已存在的順序。
    （例如冒泡排序是對於已排序的檔案來說最快的演算法（恰好是 N），但在其他情況下效率不高）。

答案4

如果每行上的單字來自有限的詞彙（例如英語），那麼您可以使用 TreeMap 並記錄計數（其中 m 是唯一值的數量）在 O(n + m log m) 時間內對清單進行排序。

否則你可以使用java庫大分類機。它將輸入拆分為排序的中間文件並有效地合併它們（總體 O(nlogn)）。要對文件進行排序，如下所示：

Sorter.serializerTextUtf8()
      .input(inputFile)
      .output(outputFile)
      .loggerStdOut() // display some progress
      .sort();

我創建了一個1.7GB 檔案（100m 行），隨機生成16 個字元單詞，並在142 秒內按照上述方式對其進行排序，並且基於我正在使用的方法的O(n log n) 計算複雜度，我估計800GB 的16 個字元單字將在我配備 SSD 的 i5 2.3GHz 筆記型電腦上進行單線程排序大約需要 24 小時。

相關內容