python - 为什么 "map"版本的ThreeSum这么慢？

Question

我预计 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)

Answer 1

提供第二个答案。从各种评论来看，您似乎主要关心的是为什么这个特定的 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 测试来进行比较:-)