在Python中，将列表项与大文件中的行进行匹配的最有效方法是什么？

Question

我有一个名为my_file的大文件（5Gb）。我有一个名为my_list的列表。读取文件中的每一行，并找出与my_list中的项目匹配的行中的项，如果找到，则创建一个名为matches的新列表。此列表将包含从my_file和my_list中匹配的项所在的行中提取出的项。这里是我的尝试：

def calc(my_file, my_list)
    matches = []
    my_file.seek(0,0)
    for i in my_file:
        i = list(i.rstrip('\n').split('\t'))
        for v in my_list:
            if v[1] == i[2]:
                item = v[0], i[1], i[3]
                matches.append(item)
    return matches

这是my_file文件中的一些行：

lion    4    blue    ch3
sheep   1    red     pq2
frog    9    green   xd7
donkey  2    aqua    zr8

以下是 my_list 中的一些项目：

intel    yellow
amd      green
msi      aqua    

在上述示例中，期望的输出为一个列表，其中每个元素也是一个列表：

[['amd', 9, 'xd7'], ['msi', 2, 'zr8']]

我的代码目前能够工作，尽管速度非常缓慢。使用生成器或序列化会有所帮助吗？谢谢。

- drbunsen

---

“really slow”是什么意思？请提供两个内容：运行所需的实际时间和执行open("my_file","r").read()所需的时间。 - S.Lott

@S.Lott：你说得对，在这种情况下I/O可能会占主导地位；不过由于文件大小为5G，所以在这里使用for _ in open('my_file'): pass可能更合适。 - jfs

@J.F. Sebastian：说得好。然而，如果没有数字，这可能只是一种标准的过早优化情况。 - S.Lott

通过我的当前代码，程序需要大约2天的时间才能完成。我在一个大小大约为原文件的1/100的my_file版本上运行了数字，时间约为1小时运行程序，打开文件少于一分钟。 - drbunsen

Answer 1

你可以建立一个查找v的字典。我还添加了更多小的优化：

def calc(my_file, my_list)

    vd = dict( (v[1],v[0]) for v in my_list)

    my_file.seek(0,0)
    for line in my_file:
        f0, f1, f2, f3 = line[:-1].split('\t')
        v0 = vd.get(f2)
        if v0 is not None:
           yield (v0, f1, f3)

对于大型的my_list，这将会更快。

使用get比检查i[2]是否在vd中加上访问vd[i[2]]要快。

为了获得更多的加速优化，我建议使用http://www.cython.org

- rocksportrocker

---

关于使用.get()的好处很好。我注意到了并相应地更新了我的答案，但是因为你明确提到了它，所以加1分。 - Shawn Chin

顺便提一下，.split() 返回一个列表，所以不需要在其上调用 list()。 - Shawn Chin

如果要解压的元素数量不匹配，f1,f2,f3 = line[:-1].split() 将会引发 ValueError 异常。 - Shawn Chin

感谢rocksportrocker的建议。我的列表不是很大，但我会尝试你的建议，看看是否能提高我的速度。 - drbunsen

正如其他人所提到的，您应该测量读取文件的速度。只需在for语句下面插入一个"continue"，您就可以看到读取5GB大文件花费了多少时间。 - rocksportrocker

Answer 2

将项目保存在字典中而不是列表中（我们称之为items）。现在像你正在做的那样迭代你的文件并挑选要查找的键（i[2]），然后检查它是否存在于items中。

items将会是：

dict (yellow = "intel", green = "amd", aqua = "msi")

因此，检查部分将是：

if i[2] in items:
  yield [[items[i[2]], i[1], i[3]]

由于您只是创建列表并返回它，使用生成器可能有助于程序的内存特性，而不是将整个内容放入列表中并返回。

- Noufal Ibrahim

Answer 3

读取文件的开销并不多，但根据你的示例代码，你可以通过将列表存储为字典（以目标字段作为键）来加速匹配。

这里有一个示例，在一些优化调整后：

mylist = {
    "yellow" : "intel",
    "green" : "amd",
    # ....
}

matches = []
for line in my_file:
    i = line[:-1].split("\t")
    try:  # faster to ask for forgiveness than permission
        matches.append([mylist[i[2]], i[1], i[3]])
    except NameError:
        pass

然而，再次注意的是，大多数性能瓶颈将出现在读取文件和在此级别进行优化可能对运行时间的影响不够大。

- Shawn Chin

Answer 4

这是对@rocksportrocker的答案的一种变化，使用了csv模块：

import csv

def calc_csv(lines, lst):
    d = dict((v[1], v[0]) for v in lst) # use dict to speed up membership test
    return ((d[f2], f1, f3)
            for _, f1, f2, f3 in csv.reader(lines, dialect='excel-tab')
            if f2 in d) # assume that intersection is much less than the file

例子：

def test():
    my_file = """\
lion    4   blue    ch3
sheep   1   red pq2
frog    9   green   xd7
donkey  2   aqua    zr8
""".splitlines()

    my_list = [
    ("intel",    "yellow"),
    ("amd",      "green"),
    ("msi",      "aqua"),
    ]    

    res = list(calc_csv(my_file, my_list))
    assert [('amd', '9', 'xd7'), ('msi', '2', 'zr8')] == res


if __name__=="__main__":
   test()    

- jfs