algorithm - 如何在不提前读取整个文件的情况下打乱文件中的行？

Question

在不提前读取整个文件的情况下打乱文件中的行的好算法是什么？

我猜它看起来像这样：从头开始逐行读取文件，在每个点存储该行并决定是否要打印到目前为止存储的行之一（然后从存储中删除）或什么都不做并继续下一行。

有人可以验证/证明这一点和/或发布工作（perl、python 等）代码吗？

相关问题，但不考虑内存效率算法：

score 4 · Accepted Answer

如果不以某种方式维护已写入内容的列表，我想不出一种方法来随机执行整个文件。我想如果我必须进行内存高效的洗牌，我会扫描文件，为新行建立一个偏移列表。一旦我有了这个新的行偏移列表，我会随机选择其中一个，将其写入标准输出，然后将其从偏移列表中删除。

我不熟悉perl或python，但可以用php演示。

<?php
$offsets = array();

$f = fopen("file.txt", "r");
$offsets[] = ftell($f);
while (! feof($f))
{
  if (fgetc($f) == "\n") $offsets[] = ftell($f);
}

shuffle($offsets);
foreach ($offsets as $offset)
{
  fseek($f, $offset);
  echo fgets($f);
}
fclose($f);
?>

我能想到的唯一另一个选择是，如果扫描文件中的新行是绝对不可接受的，那么（我不会编写这个代码）：

确定文件大小
创建已写入标准输出的偏移量和长度列表
循环直到 bytes_written == 文件大小
寻找一个尚未在已写入值列表中的随机偏移量
从该搜索备份到上一个换行符或文件开头
显示该行，并将其添加到写入的偏移和长度列表中
转到 3。

score 3 · Accepted Answer

以下算法与输入文件中的行数成线性关系。

预处理：

通过扫描换行符（或其他）来查找n（总行数），但存储表示每行开头和结尾的字符号。因此，您将有 2 个向量，例如，s输入文件中从到编号的字符是e第thn行。在 C++ 中，我会使用.s[i]e[i]ivector
将整数向量从 1 随机置换到n（在 C++ 中为random_shuffle）并将其存储在一个向量中，例如p（例如1 2 3 4变为p = [3 1 4 2]）。这意味着新文件i的行现在是原始文件中的行（即在上面的示例中，新文件的第 1 行是原始文件的第 3 行）。p[i]

主要的

创建一个新文件
通过读取原始文件中的文本并将其附加到新文件中，将第一行写入s[p[0]]新e[p[0]]文件中。
对于所有其他行，按照步骤 2 继续。

random_shuffle因此，如果您假设文件中的读/写和查找（增加文件指针）都是恒定时间操作，那么总体复杂性与行数呈线性关系（因为是线性的）。

score 0 · Accepted Answer

您可以为 N 个字符串创建一个数组，并将文件的前 N 行读入该数组。剩下的你读一行，从数组中随机选择一行，然后用新读取的字符串替换这个字符串。您还可以将数组中的字符串写出到输出文件中。这样做的好处是您不需要对文件进行两次迭代。缺点是它不会创建一个非常随机的输出文件，尤其是当 N 较低时（例如，此算法不能在输出中将最后一行移动超过 N 行。）

编辑

只是python中的一个例子：

import sys
import random

CACHE_SIZE = 23

lines = {}

for l in sys.stdin: # you can replace sys.stdin with xrange(200) to get a test output
    i = random.randint(0, CACHE_SIZE-1)
    old = lines.get(i)
    if old:
        print old,
    lines[i] = l

for ignored, p in lines.iteritems():
    print p,

algorithm - 如何在不提前读取整个文件的情况下打乱文件中的行？

3 回答 3

预处理：

主要的

Related

Reference