bisect.bisect_right()比我的快3~4倍
我写了我的 bisect_right()。它比 bisect.bisect_right() 慢 3 倍。
def my_bisect_right(a, num):
ok = len(a)
ng = -1
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if a[mid] <= num:
ng = mid
else:
ok = mid
return ok
我创建了一个包含 10M 个整数的列表并对其运行 bisect_right()。bisect.bisect_right() 耗时 24.82 秒，而 my_bisect_right() 耗时 76.30 秒。请让我知道我在做什么错...
回答
假设您使用的是 CPython 并且_bisect可用，最大的区别在于它bisect.bisect_right()是用 C 实现的。请参阅以下几行bisect.py：
# Overwrite above definitions with a fast C implementation
try:
from _bisect import *
except ImportError:
pass
作为参考，您可以通过其 repr 轻松检查函数是在 Python 还是 C 中实现的：
>>> import bisect
>>> bisect.bisect_right # C
<built-in function bisect_right>
>>> import functools
>>> functools.wraps # Python
<function wraps at 0x000001DDAB175F70>