bisect.bisect_right() 比我的快 3~4 倍

Question

我写了我的 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 秒。请让我知道我在做什么错...

Answer 1

假设您使用的是 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>