我预计 ThreeSum 的 Python 实现会很慢:
def count(a):
"""ThreeSum: Given N distinct integers, how many triples sum to exactly zero?"""
N = len(a)
cnt = 0
for i in range(N):
for j in range(i+1, N):
for k in range(j+1, N):
if sum([a[i], a[j], a[k]]) == 0:
cnt += 1
return cnt
但令我震惊的是这个版本看起来也很慢:
def count_python(a):
"""ThreeSum using itertools"""
return sum(map(lambda X: sum(X)==0, itertools.combinations(a, r=3)))
谁能推荐一个更快的 Python 实现？这两种实现看起来都很慢...... 谢谢
...
答案摘要: 以下是 O(N^3)(用于教育目的，未在现实生活中使用)版本的此线程中提供的所有不同版本在我的机器上运行的方式:
56 秒 RUNNING count_slow...
28 秒运行 count_itertools，由 Ashwini Chaudhary 编写...
14 秒 RUNNING count_fixed，由 roippi 编写...
11 秒运行 count_itertools(更快)，由 Veedrak 编写...
08 秒 RUNNING count_enumerate，由 roippi 编写...
*注意:需要修改 Veedrak 的解决方案以获得正确的计数输出:
sum(1 for x, y, z in itertools.combinations(a, r=3) if x+y==-z)
最佳答案
提供第二个答案。从各种评论来看，您似乎主要关心的是为什么这个特定的 O(n**3) 算法在从 Java 移植过来时速度很慢。让我们开始吧。
def count(a):
"""ThreeSum: Given N distinct integers, how many triples sum to exactly zero?"""
N = len(a)
cnt = 0
for i in range(N):
for j in range(i+1, N):
for k in range(j+1, N):
if sum([a[i], a[j], a[k]]) == 0:
cnt += 1
return cnt
立即出现的一个主要问题是您正在做您的 Java 代码几乎肯定不会做的事情:具体化一个 3 元素列表只是为了将三个数字加在一起!
if sum([a[i], a[j], a[k]]) == 0:
呸!就这样写吧
if a[i] + a[j] + a[k] == 0:
一些基准测试表明，您这样做会增加 50% 以上的开销只是。哎呀。
此处的另一个问题是您在本应使用迭代的地方使用了索引。在 python 中尽量避免编写这样的代码:
for i in range(len(some_list)):
do_something(some_list[i])
而只是写:
for x in some_list:
do_something(x)
如果您明确需要您所在的索引(正如您在代码中实际做的那样)，请使用enumerate:
for i,x in enumerate(some_list):
#etc
一般来说，这是一种风格的东西(尽管它比那更深入，使用鸭子类型和迭代器协议(protocol))——但它也是一种性能的东西。为了查找 a[i] 的值，该调用被转换为 a.__getitem__(i)，然后 python 必须动态解析一个 __getitem__ 方法查找，调用它，并返回值。每次。这不是一个疯狂的开销 - 至少在内置类型上 - 但如果你在循环中做很多事情，它就会加起来。另一方面，将 a 视为可迭代对象可以避免很多开销。
考虑到这一变化，您可以再次重写您的函数:
def count_enumerate(a):
cnt = 0
for i, x in enumerate(a):
for j, y in enumerate(a[i+1:], i+1):
for z in a[j+1:]:
if x + y + z == 0:
cnt += 1
return cnt
让我们看一些时间:
%timeit count(range(-100,100))
1 loops, best of 3: 394 ms per loop
%timeit count_fixed(range(-100,100)) #just fixing your sum() line
10 loops, best of 3: 158 ms per loop
%timeit count_enumerate(range(-100,100))
10 loops, best of 3: 88.9 ms per loop
这将是最快的速度。您可以通过将所有内容包装在理解中而不是执行 cnt += 1 来削减大约一个百分比，但这非常小。
我玩过一些 itertools 实现，但实际上我无法让它们运行得比这个显式循环版本更快。如果您考虑一下，这是有道理的 - 对于每次迭代，itertools.combinations 版本必须重新绑定(bind)所有三个变量所引用的内容，而显式循环会“作弊” "并且在外循环中重新绑定(bind)变量的频率要低得多。
但是现实检查时间:在一切都说完之后，您仍然可以期望 cPython 运行此算法比现代 JVM 慢一个数量级。 python 内置了太多的抽象，妨碍了快速循环。如果您关心速度(并且您无法修复您的算法 - 请参阅我的其他答案)，要么使用类似 numpy 的东西来花费所有时间在 C 中循环，要么使用不同的 python 实现.
后记:pypy
为了好玩，我在 cPython 和 pypy 上对 1000 个元素的列表运行了 count_fixed。
cPython:
In [81]: timeit.timeit('count_fixed(range(-500,500))', setup='from __main__ import count_fixed', number = 1)
Out[81]: 19.230753898620605
pypy:
>>>> timeit.timeit('count_fixed(range(-500,500))', setup='from __main__ import count_fixed', number = 1)
0.6961538791656494
快点!
我可能会在稍后添加一些 java 测试来进行比较:-)
关于python - 为什么 "map"版本的ThreeSum这么慢？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25712596/