gpt4 book ai didi

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

转载 作者:太空宇宙 更新时间:2023-11-03 13:00:01 25 4
gpt4 key购买 nike

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

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com