bisect_right() 怎么会比 insort_right() 慢 4 倍？

Question

我正在尝试优化在竞争性编程网站上超时的解决方案。我开始使用 cProfile，它似乎显示 bisect_right() 需要的时间是 insort_right() 的 4 倍。这是对包含超过 40k 个条目的输入列表的分析运行：

         89936 function calls in 3.596 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    3.596    3.596 <string>:1(<module>)
        1    0.180    0.180    3.596    3.596 leetcode.py:38(go)
        1    3.357    3.357    3.415    3.415 leetcode.py:6(numSubarrayProductLessThanK)
    44965    0.045    0.000    0.045    0.000 {built-in method _bisect.bisect_right}
    44965    0.014    0.000    0.014    0.000 {built-in method _bisect.insort_right}
        1    0.000    0.000    3.596    3.596 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.print}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

我认为所有列表插入都是 O(n)，因为平均而言 n/2 元素必须被移动。只需确定插入排序列表的位置就是 O(log n)。但在配置文件报告中它看起来翻转了：插入器 insort_right() 比位置确定器 bisect_right() 慢。我哪里错了？这是代码：

from bisect import insort, bisect

class Solution:
    def numSubarrayProductLessThanK(self, nums, k):
        if k == 0:
            return 0

        result = 0
        product = 1 
        products = [1]
        products_n = 1

        for num in nums:
            product *= num

            factor_min = product // k
            n_factors_less = products_n - bisect(products, factor_min)

            result += n_factors_less

            insort(products, product)
            products_n += 1

        return result

感谢您的观看。

Answer 1

您的 bisect 和 insort 调用传递了完全不同的参数。

假设 nums 是一个正整数列表，您的 insort 调用将始终在 products 列表的末尾插入新的 product，这需要 O (1) 而不是 O(n) 的插入时间，它非常适合二分搜索的分支预测。（Python 对象比较比简单的硬件比较指令更复杂，但分支预测仍然适用于比较挂钩内的逻辑，特别是因为 int 比较是在 C 中实现的。）

同时，假设 k 明显大于 nums 的典型元素，您的 bisect 调用将在列表中间的某个位置找到 factor_min 的位置，大多数时候可能接近但不在最后。这不太适合分支预测。

如果没有更复杂的测试，我不能确定分支预测是主导因素，但它似乎是可能的。

bisect_right() 怎么会比 insort_right() 慢 4 倍？

How can bisect_right() be 4x slower than insort_right()?

python

list

bisect