关于处理大文件的建议 - python 还是命令行？

Question

给定两个文件，一个包含以下形式的条目：

label1 label2 name1
label1 label3 name2

另一个包含以下形式的条目：

label1 label2 name1 0.1 1000
label9 label6 name7 0.8 0.5

假设您要从文件二中提取前三个元素出现在文件一的一行中（顺序很重要）的行 - 有关如何进行的任何建议这可能很快就会成为圆顶吗？

给定上述示例数据的任何此类脚本的输出文件将是：

label1 label2 name1 0.1 1000

I toyed with python:

inp = open(file1.txt, 'r')
look_up = [i.split() for i in inp.readlines()]
inp.close()

inp = open('file2', 'wt')

holder = []

line = inp.readline()
while line:
    line = line.split()
    if [line[0], line[1], line[2]] in look_up:
        holder.append(line)
    line = inp.readline()

但这似乎需要一段时间。这些文件相当大。

谢谢！

Answer 1

您的 python 版本效率相当低，因为您正在测试列表中的成员资格，而不是集合或字典（即 O(n) 查找时间而不是 O(1)）。

尝试使用元组集合或字符串集合。元组将是更好的选择，因为两个文件可以在不同的分隔符上分割，但我认为您不会看到特别大的性能差异。与测试很长列表的成员资格相比，tuple('something'.split()) 相对较快。

此外，无需调用 inp.readlines()。换句话说，您可以这样做，

look_up = set(tuple(line.split()) for line in inp)

并且您应该看到显着的加速，而无需更改代码的任何其他部分，除了 tuple(line[:3]) 而不是 [line[ 0]，行[1]，行[2]]。

实际上，grep 和 bash 对此非常完美...（未经测试，但应该可以工作。）

while read line
do
    grep "$line" "file2.txt"
done < "file1.txt"

要查看哪一个更快，我们可以 生成一些测试数据（file1.txt 中约 4500 个键，file2.txt 中 1000000 行），并对简单的 Python 版本进行基准测试相同的东西（粗略地......这些行将以与 grep 版本不同的顺序打印。）。

with open('file1.txt', 'r') as keyfile:
    lookup = set(tuple(line.split()) for line in keyfile)

with open('file2.txt', 'r') as datafile:
    for line in datafile:
        if tuple(line.split()[:3]) in lookup:
            print line,

快约 70 倍。

jofer@cornbread:~/so> time sh so_temp149.sh > a

real    1m47.617s
user    0m51.199s
sys     0m54.391s

事实证明，Python 版本比vs.

jofer@cornbread:~/so> time python so_temp149.py > b

real    0m1.631s
user    0m1.558s
sys     0m0.071s

当然，这两个示例以完全不同的方式解决问题。我们实际上是在比较两种算法，而不是两种实现。例如，如果 file1 中只有几行关键行，则 bash/grep 解决方案很容易胜出。

（bash 是否有某种内置容器，可以 O(1) 查找成员资格？（我认为 bash 4 可能有一个哈希表，但我对此一无所知......）尝试实现会很有趣与上面 bash 中的 python 示例类似的算法，以及......）

Answer 2

Hacky bash/sort/Perl 解决方案：

$ cat > 1
label1 label2 name1
label1 label3 name2

$ cat > 2
label1 label2 name1 0.1 1000
label9 label6 name7 0.8 0.5

$ (cat 1; cat 2; ) | sort | perl -ne 'INIT{$pattern_re="(?:\\S+) (?:\\S+) (?:\\S+)"; $current_pattern="";} if(/^($pattern_re)$/o){$current_pattern=$1} else {if(/^($pattern_re)/o) { print if $1 eq $current_pattern} }'
label1 label2 name1 0.1 1000

它将两个文件合并到一个列表中，对其进行排序（因此我们获得具有相同键的数据块，从文件 1 开始按行引导），然后使用特殊的 Perl oneliner 只留下格式良好的行具有文件 1 中的前置“标头”。

Answer 3

您可以尝试使用字符串“label1 label2 name1”作为键，而不是值的三元组。

Answer 4

我将使用哈希来存储第一个文件中的值。虽然不是那么容错（每个项目之间只有 1 个空格），但您会得到总体思路......

#!/usr/bin/env python

labels={}
with open('log') as fd:
    for line in fd:
        line=line.strip()
        labels[line]=True

with open('log2') as fd:
    for line in fd:
        if " ".join(line.split()[0:3]) in labels:
            print line