在 Python 中优化集合理解

Question

我正在尝试优化 Python 程序以提高速度。在查看我的 CProfiler 转储后，我发现瓶颈在于集合理解，它显示为对 <setcomp> 的调用。相关的代码行是：

mySet = {foo['bar'] for foo in long_list if foo['baz'] == special}

更多可能有用的信息：

结果 mySet 总是很小，在 0-10 个元素之间。
long_list 几乎总是很长（数千个元素）。
special foo in long_list，我们用来构建集合的是 long_list 的一个小子集（数十或数百个元素，即 1%-10 long_list 中所有 foo 的百分比）。

我应该如何优化速度？

在使用集合理解之前将 long_list 减少到 special 个？如果可以，如何快速完成？
完全摆脱集合理解？给定场景（长列表，10% 特殊的，< 10 个需要被捞出的唯一值），正确的 algorithm/data 结构是什么？

如果我们先通过列表理解来削减 long_list，看起来会更慢：

>>> mysetup='import random\nx = range(10)\nlonglist = [random.choice(x) for p in range(100000)]'
>>> stmt1 = 'myset = {item for item in longlist if item < 3}'
>>> timeit.timeit(stmt=stmt1, setup=mysetup, number=1000) 
3.17
>>> stmt2 = 'shortlist = [x for x in longlist if x < 3]\nmyset={x for x in shortlist}'
>>> timeit.timeit(stmt=stmt2, setup=mysetup, number=1000) 
3.86

Answer 1

随着列表的变化，您可以使理解的结果保持最新。初始化一个 collections.Counter 键控 bar 值，表示列表中具有该 bar 值的特殊元素的数量。要从列表中删除一个值，请检查它是否特殊，如果是则减少计数器。如果该减量将值降为零，则从 Counter 中删除密钥。要向列表中添加一个值，请检查它是否特殊，如果是则增加计数器。如果 special 可能取多个值，则每种可能性保留一个计数器。

在 Python 中优化集合理解

Optimizing a set comprehension in Python

python

algorithm

optimization