不加载到内存中打乱大型项目列表

Question

我有一个大约有20亿行文本的文件（大约200GB）。我想生成一个新文件，里面的文本行顺序是随机打乱的。但是我无法把所有数据都放在内存里。有没有什么好的方法可以用Python或者命令行来实现，时间上能接受（几天内完成）？

我在想，我可以先创建50个空文件。然后逐行读取这20亿行的文件，把每一行随机分配到这50个空文件中。最后再把这50个文件合并起来。这样做会不会有什么大的系统性偏差呢？

Answer 1

你可以创建一个迭代器，用来生成排列。每次读取文件时，你可以根据它提供的排列来调整读取的位置。因为这个迭代器会给出不同的排列，所以你永远不会重复读取相同的数据。

对于N个元素的集合，所有的排列都可以通过交换来生成。交换就是把第0个元素和第i个元素的位置互换，而其他元素的位置保持不变。因此，你可以通过组合一些随机选择的交换来生成一个随机的排列。下面是一个用Python写的例子：

import random

class Transposer:
    def __init__(self,i):
        """
        (Indexes start at 0)
        Swap 0th index and ith index, otherwise identity mapping.
        """
        self.i = i
    def map(self,x):
        if x == 0:
            return self.i
        if x == self.i:
            return 0
        return x

class RandomPermuter:
    def __init__(self,n_gens,n):
        """
        Picks n_gens integers in [0,n) to make transposers that, when composed,
        form a permutation of a set of n elements. Of course if there are an even number of drawn
        integers that are equal, they cancel each other out. We could keep
        drawing numbers until we have n_gens unique numbers... but we don't for
        this demo.
        """
        gen_is = [random.randint(0,n-1) for _ in range(n_gens)]
        self.trans = [Transposer(g) for g in gen_is]
    def map(self,x):
        for t in self.trans:
            x = t.map(x)
        return x

rp = RandomPermuter(10,10)

# Use these numbers to seek into a file
print(*[rp.map(x) for x in range(10)])

Answer 2

在你的情况下，最简单的方法就是进行递归的洗牌和分割 - 洗牌 - 合并。你需要定义两个数字：一个是你想把一个文件分成多少个小文件，这个数字叫做 N（通常在32到256之间），另一个是你可以在内存中直接洗牌的文件大小，这个大小叫做 M（通常大约是128MB）。然后你可以用伪代码表示：

def big_shuffle(file):
    if size_of(file) < M :
        memory_shuffle(file)
    else:
        create N files
        for line in file:
            write_randomly_to_one_of_the_N_files
        for sub_file in (N_files):
            big_shuffle(file)
        merge_the_N_files_one_line_each

由于每个子文件都经过洗牌，所以不会有偏差。

这个方法的速度会比Alex Reynolds的方案慢很多（因为涉及到大量的磁盘读写），但你唯一的限制就是磁盘空间。

Answer 3

你可以看看我的 HugeFileProcessor 工具。这个工具和 @Alex-Reynolds 的 sample 类似，但应该会快很多，因为它不需要跳来跳去。

下面是关于打乱实现的细节。它需要你指定 batchSize，也就是在写入输出时保留在内存中的行数。这个数字越大越好（除非你的内存不够），因为总的打乱时间可以用 (源文件中的行数) / batchSize * (读取源文件所需的时间) 来计算。请注意，这个程序是 对整个文件进行打乱，而不是按批次来处理。

算法大致如下。

1. 先计算 sourceFile 中的行数。这可以通过逐行读取整个文件来完成。（你可以在 这里 查看一些比较。）这也能让我们知道读取整个文件一次需要多长时间。因此，我们可以估算出完成一次完整打乱需要多少次读取，因为这需要 Ceil(行数 / batchSize) 次完整的文件读取。

2. 现在我们知道了总的 linesCount，我们可以创建一个大小为 linesCount 的索引数组，并使用 Fisher–Yates 算法对它进行打乱（在代码中称为 orderArray）。这将给我们一个想要在打乱后的文件中行的顺序。注意，这个顺序是针对整个文件的，而不是按批次或块来处理。

3. 接下来是实际的代码。我们需要按照刚刚计算的顺序从 sourceFile 中获取所有行，但我们不能把整个文件都读到内存中。所以我们将任务分成几部分来处理。

   • 我们会遍历 sourceFile，读取所有行，并只在内存中存储 orderArray 中前 batchSize 的行。当我们获取到这些行后，就可以按照需要的顺序将它们写入 outFile，这就完成了 batchSize/linesCount 的工作。
   • 接下来，我们会重复这个过程，继续处理 orderArray 中的下一部分，每次都从头到尾读取 sourceFile。最终，整个 orderArray 都会被处理完，我们就完成了。

为什么这样有效？

因为我们做的就是从头到尾读取源文件。没有前后跳转，这正是硬盘喜欢的方式。文件会根据内部硬盘缓冲区、文件系统块、CPU缓存等被分块读取，所有内容都是顺序读取的。

一些数字

在我的机器上（Core i5，16GB内存，Win8.1，Toshiba DT01ACA200 2TB硬盘，NTFS），我能在大约5小时内用 batchSize 为 3,500,000 的设置打乱一个132GB（84,000,000行）的文件。使用 batchSize 为 2,000,000 时，花了大约8小时。读取速度大约是每秒118,000行。

Answer 4

这样怎么样：

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 5

如果你能为这个程序预留16GB的内存，我写了一个叫sample的程序，它可以通过读取文件中每一行的字节偏移量来打乱文件的行顺序。具体做法是先打乱这些偏移量，然后根据打乱后的偏移量在文件中查找并输出内容。每个64位的偏移量占用8个字节，所以对于一个有20亿行的输入文件，就需要16GB的内存。

这个程序的速度可能不快，但在内存足够的系统上，sample可以处理那些大到GNU shuf无法处理的文件。此外，它还使用了mmap的方式，尽量减少第二次读取文件时的输入输出开销。它还有一些其他选项，具体可以查看--help获取更多信息。

默认情况下，这个程序会进行不重复的抽样，并逐行打乱。如果你想要重复抽样，或者你的输入是FASTA、FASTQ或其他多行格式，可以添加一些选项来调整抽样方式。（或者你可以参考我下面链接的Perl代码，虽然sample已经处理了这些情况。）

如果你的FASTA序列每两行一组，也就是说一行是序列头，下一行是序列数据，你仍然可以使用sample进行打乱，而且只需要一半的内存，因为你只需打乱一半的偏移量。可以使用--lines-per-offset选项；例如，你可以指定2来打乱成对的行。

对于FASTQ文件，它们的记录每四行分开一次。你可以指定--lines-per-offset=4来用四分之一的内存打乱一个FASTQ文件，而不是打乱单行文件所需的全部内存。

另外，我在这里有一个用Perl写的代码片段这里，它可以从FASTA文件中进行不重复的抽样，而不考虑序列的行数。需要注意的是，这和打乱整个文件并不完全相同，但你可以把它作为一个起点，因为它会收集偏移量。你可以去掉第47行的代码，这行代码是用来排序打乱后的索引的，然后使用文件查找操作直接读取文件，使用打乱后的索引列表。

再次强调，这个过程不会很快，因为你是在一个非常大的文件中无序跳转，但存储偏移量比存储整行数据便宜得多，添加mmap的方式可能会对这些随机访问操作有所帮助。而且如果你处理的是FASTA文件，你需要存储的偏移量会更少，所以你的内存使用量（不算一些相对不重要的容器和程序开销）最多应该是8GB，实际上可能更少，具体取决于文件的结构。