python - Python 中通过随机化减少文本文件

Question

我在 bash 中解决了以下问题，但考虑到我需要减少的文件大小，我觉得它效率很低且非常慢。希望有人知道如何在 Python 中做同样的事情并希望加快速度。

最初的问题是减少非常大的文本文件(50-6000 万行，制表符分隔的列)。 其中一列被视为键，即我们确定文件中有多少行具有唯一键，然后随机选择其中的百分比(例如，如果减少 75%，则为总数的四分之一)以附加到一个将保留我们的结果的新文件。我们继续检查其余的键，随机化，然后以相同的百分比减少包含每个唯一键的所有行。如果无法减少，我们只需将所有行转移到结果文件中即可。

正如我所说，我的 bash 脚本运行得很好，但速度很慢，并且将各种 awk 和 grep 结构串在一起。从各方面来看，Python 应该以一种更优雅的方式处理这个问题，并且不会过多地影响内存(同样，在这种情况下，我们正在处理 50 多百万行的文件)。 任何建议/技巧都会有帮助!谢谢!

Answer 1

简单的解决方案是按键列对文件进行排序，例如 sort第二列制表符分隔的输入:

#!/bin/bash
printf "a\tz\nb\ty\nc\tx" | sort -k 2 -t $'\t'

然后解决一个更简单的问题，即为每个唯一键检索 25% 的随机行，其中具有相同键的所有行都相邻，并具有每个唯一键至少应保留一行的约束:

#!/usr/bin/env python
import random
import sys
from itertools import chain, groupby

def choose_random(iterator, fraction, random=random.random):
    """Lazy analog of:

        L = list(iterator)
        k = int(len(L) * fraction + .5) or 1 # get at least one
        result = random.sample(L, k)

    Note: this function doesn't randomize the order of elements
          that would require to keep selected elements in memory
          and number of output elements is not exactly k
    """
    # always yield at least one item if input is not empty
    item = next(iterator)
    it = (x for x in chain([item], iterator) if random() < fraction)
    for x in chain([next(it, item)], it):
        yield x

def getkey(line):
    return line.split("\t")[1] # 2nd column

for key, group in groupby(sys.stdin, key=getkey):
    sys.stdout.writelines(choose_random(group, fraction=0.25))

注意:输入文件中的最后一行应包含换行符，否则如果选择最后一行，输出将损坏。

该脚本接受 stdin 上排序(按键列)的输入，并将减少的输出打印到 stdout。它一次只需要在内存中存储一​​行。它是单遍算法 (O(n))。