在不加载内存的情况下随机播放大量项目

Question

我有一个大约20亿行文本的文件(~200gig).我想生成一个包含相同文本行的新文件,但是按行随机洗牌.我无法将所有数据保存在内存中.有没有一个很好的方法在python /命令行中执行此操作需要一段合理的时间(几天)？

我以为我可以触摸50个空文件.流过20亿行文件,并将每行随机分配到50个空文件中的一个.然后cat 50个文件.对这种方法有任何重大的系统偏见吗？

Answer 1

如果你可以为这个程序保留16 GB的内存,我编写了一个程序sample,它通过读取它们的字节偏移量来调整文件的行,调整偏移量,然后通过搜索文件到打乱的偏移来打印输出.它为每个64位偏移使用8个字节,因此对于20亿行输入使用16个字节.

它不会很快,但在具有足够内存的系统上,sample将随机播放足以导致GNU shuf失败的文件.此外,它使用mmap例程来尝试最小化第二次通过文件的I/O开销.它还有一些其他选择; 了解--help更多详情.

默认情况下,此程序将在没有替换的情况下进行采样并通过单行进行随机播放 如果您想要替换,或者您的输入是FASTA,FASTQ或其他多行格式,您可以添加一些选项来调整采样的方式.(或者你可以应用另一种方法,我在下面的Perl要点中链接,但sample解决了这些情况.)

如果你的FASTA序列在每两行上,也就是说,它们在一行上的序列标题和下一行的序列数据之间交替,你仍然可以随机播放sample,并且只有一半的内存,因为你只是改变一半的偏移量.看--lines-per-offset选项; 2例如,你可以指定改变线对.

对于FASTQ文件,它们的记录每四行分割一次.您可以指定使用--lines-per-offset=4调整单行文件所需的四分之一内存来随机播放FASTQ文件.

可替换地,我有一个要旨这里用Perl写成的,其将采样而无需来自FASTA文件替换序列而无需在一个序列的行数方面.请注意,这与对整个文件进行混洗并不完全相同,但您可以将此作为起点,因为它会收集偏移量.您不必对某些偏移进行采样,而是删除对排序后的索引进行排序的第47行,然后使用文件搜索操作直接使用混洗索引列表来读取文件.

同样,它不会很快,因为你正在乱序地跳过一个非常大的文件,但是存储偏移比存储整行要便宜得多,并且添加mmap例程可以帮助一点点本质上是一系列随机的访问操作.如果您正在使用FASTA,那么存储的偏移量会更少,因此您的内存使用量(除了任何相对无关紧要的容器和程序开销)应该最多为8 GB - 并且可能更少,具体取决于其结构.

Answer 2

怎么样:

import mmap
from random import shuffle

def find_lines(data):
    for i, char in enumerate(data):
        if char == '\n':
            yield i 

def shuffle_file(in_file, out_file):
    with open(in_file) as f:
        data = mmap.mmap(f.fileno(), 0, access=mmap.ACCESS_READ)
        start = 0
        lines = []
        for end in find_lines(data):
            lines.append((start, end))
            start = end + 1
        shuffle(lines)

        with open(out_file, 'w') as out:
            for start, end in lines:
                out.write(data[start:end+1])

if __name__ == "__main__":
    shuffle_file('data', 'result')

此解决方案应该只存储文件中行的所有文件偏移量,即每行2个字,加上容器开销.

Answer 3

您可以查看我的HugeFileProcessor工具。它类似于@Alex-Reynolds 的sample，但应该快得多，因为没有搜索。

以下是有关改组实施的详细信息。它需要指定batchSize - 写入输出时保留在 RAM 中的行数。越多越好（除非您的 RAM 不足），因为总混洗时间将为(sourceFile 中的行数) / batchSize * (time to full read sourceFile)。请注意，该程序会打乱整个文件，而不是按批次打乱。

算法如下。

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

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

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

   • 我们要经过的资源文件读取所有的线条和存储在存储器中只有那些会在第一线BATCHSIZE的的orderArray。当我们得到所有这些行时，我们可以按照需要的顺序将它们写入outFile，它是完成工作的batchSize / linesCount。
   • 接下来，我们将一次又一次地重复整个过程，取出orderArray 的下一部分，并从头到尾读取每个部分的sourceFile。最终整个orderArray被处理，我们就完成了。

为什么有效？

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

一些数字

在我的机器（酷睿i5，16GB RAM，Win8.1，HDD东芝DT01ACA200 2TB，NTFS），我能够重新洗牌使用5个小时左右132 GB（84条000 000线）的文件BATCHSIZE的3 500 000随着BATCHSIZE 2 000 000 花了大约 8 小时。阅读速度约为每秒 118000 行。