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。

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

第一个非常简单的优化是简单地将列表中的 final 字典行更改为 set - 使用 set 匹配in 运算符从线性变为恒定时间(从 O(m) 到 O(1) ) - 因此，如果在运行之前，您基本上将搜索时间缩短了 50 倍您在示例中执行的代码:

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

但是您仍然在 final 的每个 2010 键中执行线性搜索。将其更改为常量搜索的方法是创建一个反向字典 - 其中一行 final 中的 50 个值中的每一个都指向键 esp。然后您只需使用 a[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]
       ...