如何从大文件中随机删除多行？

Question

我有一个很大的文本文件，大小是13GB，里面有158,609,739行。我想随机选择155,000,000行。

我试过把文件打乱顺序，然后截取前155,000,000行，但我的内存（16GB）似乎不够用，无法完成这个操作。我尝试过的处理方式有：

shuf file | head -n 155000000
sort -R file | head -n 155000000

现在，我觉得与其选择行，不如从文件中删除3,609,739行随机的内容，这样最终文件就能剩下155,000,000行，这样更节省内存。

Answer 1

马可·兰萨姆回答的证明

我们用一些更简单的数字来思考（至少对我来说是这样！）：

• 10个项目
• 删除其中3个

第一次循环时，我们假设前面三个项目被删除了——看看概率是怎样的：

• 第一个项目： 3 / 10 = 30%
• 第二个项目： 2 / 9 = 22%
• 第三个项目： 1 / 8 = 12%
• 第四个项目： 0 / 7 = 0 %
• 第五个项目： 0 / 6 = 0 %
• 第六个项目： 0 / 5 = 0 %
• 第七个项目： 0 / 4 = 0 %
• 第八个项目： 0 / 3 = 0 %
• 第九个项目： 0 / 2 = 0 %
• 第十个项目： 0 / 1 = 0 %

如你所见，一旦概率变为零，就一直是零。但如果什么都没有被删除呢？

• 第一个项目： 3 / 10 = 30%
• 第二个项目： 3 / 9 = 33%
• 第三个项目： 3 / 8 = 38%
• 第四个项目： 3 / 7 = 43%
• 第五个项目： 3 / 6 = 50%
• 第六个项目： 3 / 5 = 60%
• 第七个项目： 3 / 4 = 75%
• 第八个项目： 3 / 3 = 100%
• 第九个项目： 2 / 2 = 100%
• 第十个项目： 1 / 1 = 100%

所以，尽管每一行的概率不同，但总体上你得到了想要的结果。我进一步做了一步，写了一个Python测试，运行了一百万次，作为我自己的最终证明——从100个项目中删除7个：

# python 3.2
from __future__ import division
from stats import mean  # http://pypi.python.org/pypi/stats
import random

counts = dict()
for i in range(100):
    counts[i] = 0

removed_failed = 0

for _ in range(1000000):
    to_remove = 7
    from_list = list(range(100))
    removed = 0
    while from_list:
        current = from_list.pop()
        probability = to_remove / (len(from_list) + 1)
        if random.random() < probability:
            removed += 1
            to_remove -= 1
            counts[current] += 1
    if removed != 7:
        removed_failed += 1

print(counts[0], counts[1], counts[2], '...',
      counts[49], counts[50], counts[51], '...',
      counts[97], counts[98], counts[99])
print("remove failed: ", removed_failed)
print("min: ", min(counts.values()))
print("max: ", max(counts.values()))
print("mean: ", mean(counts.values()))

这是我运行几次中的一次结果（它们都很相似）：

70125 69667 70081 ... 70038 70085 70121 ... 70047 70040 70170
remove failed:  0
min:  69332
max:  70599
mean:  70000.0

最后一点：Python的 random.random() 生成的是 [0.0, 1.0)（不包括1.0作为可能值）。

Answer 2

你可以提前生成一个要删除的行号列表，这个列表包含3,609,739个随机数字，这些数字是从文件中选出来的，且不会重复。然后，你只需要遍历这个文件，把内容复制到另一个文件中，必要时跳过那些要删除的行。只要你有足够的空间来存放新文件，这个方法就可以使用。

你可以用 random.sample 来选择这些随机数字。例如：

random.sample(xrange(158609739), 3609739)

Answer 3

在你把文件中的每一行复制到输出时，要判断一下这行是否应该被删除。第一行被删除的概率是3,609,739/158,609,739。如果你生成一个0到1之间的随机数，如果这个数小于这个比例，就不要把这一行复制到输出里。第二行的删除概率变成了3,609,738/158,609,738；如果这一行没有被删除，那么第三行的概率就是3,609,738/158,609,737。这样一直重复下去，直到处理完所有行。

因为每处理一行，删除的概率都会变化，这个算法能确保最终的行数是准确的。一旦你删除了3,609,739行，删除的概率就变成零；如果在任何时候你需要删除文件中剩下的所有行，删除的概率就变成一。