代码之家  ›  专栏  ›  技术社区  ›  Frank

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

  •  3
  • Frank  · 技术社区  · 14 年前

    在不预先读取整个文件的情况下,对文件中的行进行无序排列有什么好的算法?

    我想应该是这样的:从一开始一行一行地读取文件,在每一点存储该行,然后决定是否要打印到目前为止存储的其中一行(然后从存储中删除),或者什么都不做,然后继续下一行。

    有人能验证/证明这一点和/或可能是工作后(perl、python等)代码吗?

    相关问题,但不考虑记忆效率算法:

    3 回复  |  直到 14 年前
        1
  •  4
  •   Brandon Horsley    14 年前

    我想不出一种方法来随机地完成整个文件,而不必以某种方式维护已经写入的内容的列表。我想如果我必须做一个内存高效的洗牌,我会扫描文件,为新的行建立一个偏移列表。一旦我有了这个新行偏移列表,我将随机选择其中一个,将其写入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。
        2
  •  3
  •   Jacob    14 年前

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

    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中的所有其他行。

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

        3
  •  0
  •   Rudi    14 年前

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