20

我想在 Linux 中随机播放一个包含数百万行字符串的大文件。我试过'sort -R'但它很慢（一个16M的大文件需要50分钟）。有没有更快的实用程序可以代替它？

4

3 回答 3

34

使用shuf代替sort -R（手册页）。

的缓慢可能sort -R是由于它散列每一行。shuf只是做一个随机排列，所以它没有那个问题。

（这是在评论中提出的，但由于某种原因没有被任何人写成答案）

于 2015-04-02T20:23:02.387 回答
3

根据您的描述，50 分钟不是由实际的排序机制引起的。时间很可能花在等待/dev/random产生足够的熵上。

一种方法是使用外部随机数据源（例如http://random.org）以及Schwartzian Transform的变体。Schwartzian 变换将要排序的数据转换为嵌入了排序键的“丰富”数据。使用 key 对数据进行排序，然后丢弃 key。

将此应用于您的问题：

  • 生成一个带有随机数的文本文件，每行 1 个，行数与要排序的文件相同。这可以在任何时候完成，在后台运行，在不同的服务器上运行，从 random.org 下载等等。关键是当你尝试排序时不会产生这种随机性。

  • 使用以下命令创建文件的丰富版本paste：

    paste random_number_file.txt string_data.txt > tmp_string_data.txt

  • 排序这个文件：

    sort tmp_string_data.txt > sorted_tmp_string_data.txt

  • 删除随机数据：

    cut -f2- sorted_tmp_string_data.txt > random_string_data.txt

这是基本思想。我试过了，它确实有效，但我没有 1600 万行文本或 1600 万行随机数。您可能希望将其中一些步骤流水线化，而不是将其全部保存到磁盘。

于 2013-02-07T06:06:16.820 回答
0

你可以试试我的工具：HugeFileProcessor。它能够在合理的时间内洗牌数百 GB 的文件。

以下是改组实施的详细信息。它需要指定batchSize - 写入输出时保留在 RAM 中的行数。越多越好（除非你的内存用完了），因为总洗牌时间是(sourceFile 中的行数) / batchSize * (time to fully read sourceFile)。请注意，该程序会随机播放整个文件，而不是每批。

算法如下。

  1. 计算sourceFile中的行数。这只需逐行读取整个文件即可完成。（请参阅此处的一些比较。）这​​也可以衡量读取整个文件一次需要多少时间。因此，我们可以估计进行一次完整的 shuffle 需要多少次，因为它需要Ceil(linesCount / batchSize)完整的文件读取。

  2. 由于我们现在知道总linesCount，我们可以创建linesCount大小的索引数组并使用Fisher-Yates （在代码中称为orderArray ）对其进行洗牌。这会给我们一个顺序，我们希望在一个打乱的文件中有行。请注意，这是整个文件的全局顺序，而不是每个批次或块或其​​他东西。

  3. 现在是实际代码。我们需要按照刚刚计算的顺序从sourceFile中获取所有行，但是我们无法读取内存中的整个文件。所以我们只是拆分任务。

    • 我们将通过sourceFile读取所有行并仅将那些将在 orderArray 的第一个 batchSize 中的行存储在内存中。当我们得到所有这些行时，我们可以按要求的顺序将它们写入outFile，这是一个batchSize / linesCount完成的工作。
    • 接下来，我们将一次又一次地重复整个过程，获取orderArray的下一部分，并为每个部分从头到尾读取sourceFile。最终整个orderArray都被处理了，我们就完成了。

为什么它有效？

因为我们所做的只是从头到尾读取源文件。没有向前/向后搜索，这就是 HDD 喜欢的。文件根据内部 HDD 缓冲区、FS 块、CPU cahce 等以块的形式读取，并且所有内容都是按顺序读取的。

一些数字

在我的机器（Core i5、16GB RAM、Win8.1、HDD Toshiba DT01ACA200 2TB、NTFS）上，我能够使用3 500 000 的batchSize在大约 5 小时内随机播放 132 GB（84 000 000 行）的文件。使用batchSize 2 000 000 大约需要 8 个小时。读取速度约为每秒 118000 行。

于 2016-08-07T10:28:13.477 回答