python - for/in/if 列表理解在大量匹配项下变得非常慢

Question

我的 Python 2.7 代码中有以下列表理解，它返回行号(索引)和一长串行中的行:

results = [[lines.index(line), line] for line in lines
            if search_item in line.lower()]

如果结果数量很少，这会非常快:

The search item is: [ 1330 ]
Before string pre-processing, the time is: 0.0000
The number of lines is: 1,028,952
After string pre-processing, the time is: 0.2500
The number of results is: 249

“字符串预处理”就是我上面所说的results = operation。

这是相同的操作，但使用“1330”而不是“1330”作为搜索项。这个产生 6,049 个匹配项而不是 249 个:

The search item is: [1330]
Before string pre-processing, the time is: 0.0000
The number of lines is: 1,028,952
After string pre-processing, the time is: 10.3180
The number of results is: 6,049

如您所见，10 秒与 1/4 秒...此外，“1330”和“1330”搜索使用 for 循环分别在 2.4 和 3.2 秒内运行:

for lineNum, line in enumerate(lines):
    if search_item in line.lower():
        return lineNum, line

因此，列表理解在 249 个结果的情况下性能提高了 10 倍，但在 6,049 个结果的情况下慢了 3 倍...

显然，问题不在于列表理解的 if/in 部分(两个搜索都扫描所有 1M+ 行并接受或拒绝每一行)，而在于构建第二个“long'ish”的结果列表案件。换句话说，瓶颈似乎在

results = [lines.index(line), line]

部分理解。

我想我对列表理解对于大型结果集变得如此缓慢感到非常惊讶(6K 实际上并没有那么大)。我错过了什么？我应该使用一种不同的方法来始终优于 for 循环吗？

Answer 1

list.index() 调用必须搜索所有行 以找到匹配项。对于 N 行，执行 O(N^2) 步； 1000 行变成一百万步，等等。对于 6k 行，这是 3600 万步 ^*

如果您只需要行号，请使用 enumerate() function生成一个:

results = [[index, line] for index, line in enumerate(lines)
            if search_item in line.lower()]

enumerate() 添加一个运行计数器，让您的算法只执行 O(N) 个步骤。您已经在完整的 for 循环语句中使用了它，但不在您的列表理解中。

但是，如果您有重复行，输出会有所不同； lines.index() 找到第一个 匹配项，而enumerate() 生成唯一的行号。

---

^* Big-O notation给我们算法的渐近行为。由于 list.index() 对于给定行 x 只需扫描(最多)x 行即可找到索引，如果您对你迭代的每一行都这样做，你总共只需要 1 + 2 + 3 + ... x 步，这是一个 triangle number .所以总共“只”((N *(N + 1))/2)步被采取，大约1/2 N ^ 2步。但是当 N 趋于无穷大时，乘数不再重要，最终得到 O(N^2)。