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实现的。请参阅these lines in 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>