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

Question

我有一个13GB的大文本文件，有158609739行，我想随机选择155000000行。在

我尝试过对文件进行置乱，然后剪切155000000行，但是看起来我的ram内存（16GB）不够大。我尝试过的管道是：

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

现在不再选择行，我认为更节省内存从文件中删除3609739行随机行，得到155000000行的最终文件。在

Answer 1

当您将文件的每一行复制到输出时，评估它应该被删除的概率。第一行应该有3609739/158609739被删除的可能性。如果生成一个介于0和1之间的随机数，并且该数小于该比率，请不要将其复制到输出。现在第二行的赔率是3609738/158609738；如果不删除那一行，第三行的赔率是3609738/158609737。重复直到完成。在

因为每行处理的几率都会变化，所以该算法保证了精确的行数。一旦你删除了3609739，几率就变为零；如果在任何时候你需要删除文件中剩下的每一行，那么几率就变成了1。在

Answer 2

马克·兰森回答的证据

让我们用更容易思考的数字（至少对我来说！）公司名称：

• 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%

所以，即使每行的概率不同，总的来说你会得到你想要的结果。我从一个有100万个项目的最终测试中删除了我自己的一个100万个测试项目：

# 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()))

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

^{pr2}$

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

Answer 3

您总是可以预先生成计划删除的行号（3609739个随机数的列表，没有替换），然后遍历文件并复制到另一个，必要时跳过行。只要你有空间放一个新文件，这就行了。在

您可以用^{}选择随机数 E、 g

random.sample(xrange(158609739), 3609739)