0

我正在尝试优化在竞争性编程网站上超时的解决方案。我开始使用 cProfile，它似乎显示bisect_right()需要 4 倍于insort_right(). 这是在输入列表上运行的分析，包含超过 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

谢谢你的关注。

4

1 回答 1

2

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

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

同时，假设k远远大于 的典型元素nums，您的bisect调用将在列表中间的某个位置找到一个位置factor_min，可能在大多数情况下靠近但不在末尾。这不太适合分支预测。

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

于 2019-12-19T22:47:50.857 回答