为何Python中bisect_left比我实现的二分查找更快？

问题背景 #

我在解决一道算法题时，自己实现的二分查找超出时间限制，但使用Python标准库中的bisect_left却能快速通过测试。用10^5个随机整数做性能测试时，手动实现的二分查找耗时约0.33秒，而bisect_left仅需0.13秒，两者差距明显。

手动实现的二分查找及业务代码 #

def bs(self, new, k, n):
    st = 0
    end = n
    while st < end:
        mid = (st + end) // 2
        if new[mid] < k:
            st = mid + 1
        else:
            end = mid
    return st

def smallerSum(self, n : int, arr : List[int], val) -> List[int]:
    new = sorted(arr)
    cum = [0 for _ in range(n+1)]
    for i in range(0, n):
        cum[i+1] = cum[i] + new[i]

    ans = [0 for _ in range(n)]
    for i in range(n):
        if val == 0:
            ans[i] = cum[bisect_left(new, arr[i])]
        else:
            ans[i] = cum[self.bs(new, arr[i], n)]
    return ans

完整性能测试代码 #

from typing import List
from bisect import bisect_left, bisect_right
import random
import time

class Solution:
    def bs(self, new, k, n):
        st = 0
        end = n
        while st < end:
            mid = (st + end) // 2
            if new[mid] < k:
                st = mid + 1
            else:
                end = mid
        return st

    def smallerSum(self, n : int, arr : List[int], val) -> List[int]:
        new = sorted(arr)
        cum = [0 for _ in range(n+1)]
        for i in range(0, n):
            cum[i+1] = cum[i] + new[i]

        ans = [0 for _ in range(n)]
        for i in range(n):
            if val == 0:
                ans[i] = cum[bisect_left(new, arr[i])]
            else:
                ans[i] = cum[self.bs(new, arr[i], n)]
        return ans

if __name__ == "__main__":
    n = 10**5
    arr = []
    for i in range(n):
        arr.append(random.randint(0, 10**9))
    obj = Solution()
    st = time.time()
    res = obj.smallerSum(n, arr, 0)
    end = time.time()
    print(end - st)
    st = time.time()
    res = obj.smallerSum(n, arr, 1)
    end = time.time()
    print(end - st)

疑问 #

为什么手动实现的二分查找与bisect_left的耗时差异如此显著？bisect_left的性能优势来自哪里？

内容的提问来源于stack exchange，提问作者Anshul