Python循环优化

Question

我目前正在处理一个超过200万行的文件.我已经将这些行分成了元素列表(例如:[a,b,c,d]= 1行,单词分隔).

我正在尝试使用以下代码遍历所有行:

for a in aud:
    for esps in final:
        if a[0] in final[esps]:
            a[0] = esps

在第一个for循环中,我指的是200万+行.在第二个for循环中,它通过一个包含2010键的字典,每个键可能至少有50个相应的值.我想在行中找到a[0]与字典中的值相等的元素.如果它们匹配,我a[0]将所选行中的元素更改为字典键的值.

问题是这段代码需要很长时间才能运行,而且我对于优化以及如何更快地运行这一点并不了解太多(没有).如果有人能告诉我如何更快地完成这样的事情,我会非常感谢.

Answer 1

当你有"大"的东西要经历时,像这样,快速推进的关键是"降低算法的复杂性" - 也就是说,如果可能的话,避免任何依赖于任一数据集大小的操作.

在您给出的示例中,您为数百万行中的每一行执行50 x 2000线性搜索 - 这是很多!问题在于,如果你的每个人final[esps]都是一个列表,那么Python会使用运算符在这50个值中执行线性搜索in.

既然你提到你正在从文件中读取你的值,我必须假设[0]和行中的元素final都是字符串 - 但这也适用于数字.

第一个非常简单的优化是简单地将final字典行从列表更改为sets - 操作符set的匹配从in线性变为恒定时间(从O(m)到O(1)) - 所以,如果在运行示例中的代码之前,您基本上将搜索时间减少了50倍:

for key in final:
   final[key] = set(final[key])

但是你仍然在每个2010年的密钥中执行线性搜索final.将其更改为常量搜索的方法是创建反向字典 - 其中一行中的50个值中的每一个都final指向键esp.然后你只需使用[0]作为这个反向字典中的键 - 你将在100000项(2000 x 50)中替换线性搜索,以便在字典中以恒定时间进行搜索;

这很容易实现 - 只需将代码更改为:

rfinal = {}
for esp, values in final.items():
   for value in values:
       rfinal[value] = esp


for a in aud:
    if a[0] in rfinal:
       a[0] = rfinal[a[0]]
    else:
       # code for when there is no match for a[0]
       ...