如何在不预先读取整个文件的情况下对文件中的行进行无序排列?

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

我不熟悉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);
?>

我能想到的另一个选择是,如果扫描文件中的新行是绝对不可接受的,那就是(我不会将这一行编码出来):

1. 确定文件大小
2. 创建已写入stdout的偏移量和长度列表
3. 循环直到字节写入==文件大小
4. 寻找一个不在已写入值列表中的随机偏移量
5. 从该查找备份到上一行或文件开头
6. 显示该行,并将其添加到写入的偏移和长度列表中
7. 转到3。

下面的算法是 线性的 输入文件中的行数。

Preprocessing:

1. 发现 n (行的总数),通过扫描换行符(或其他)而存储表示每行开始和结束的字符数。所以你有两个向量,比如, s 和 e 尺寸的 n 其中字符编号来自 s[i] 到 e[i] 在输入文件中, i 第四行。在C++中我会使用 vector .

2. 将整数向量从1随机排列到 n (C++中的 random_shuffle )把它存储在一个向量中,比如, p (例如) 1 2 3 4 变成 p = [3 1 4 2] )这意味着这条线 我 的 新文件 现在是线 p[i] 在原始文件中(即在上面的示例中,新文件的第一行是原始文件的第三行)。

主要的

1. 创建新文件

2. 通过读取原始文件中的文本,在 s[p[0]] 和 e[p[0]] 并将其附加到新文件中。

3. 继续执行步骤2中的所有其他行。

所以总的复杂性是线性的(因为 随机洗牌 是线性的)如果假定在文件中进行读/写和查找(增加文件指针)都是常量时间操作。

您可以为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,