☰

在 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 小时。

相关内容