sum() 是否在 python3 中占用循环的执行时间

Question

我在循环中使用了sum()，执行时间超过4s，这里的sum()等于嵌套循环吗？

def arrayMaxConsecutiveSum(inputArray, k):
    cop=k
    lis=[]
    i=0
    while i < len(inputArray):
        inpu=sum(inputArray[i:cop])
        lis.append(inpu)
        cop+=1
        i+=1
    return max(lis)

Answer 1

sum 是作为 C++ 库实现的，因此它仍然比 Python for 循环更快，尽管您仍然是运行嵌套循环.为了说明，我在这里为您的代码计时，以及使用 Python 循环代替的修改代码：

def arrayMaxConsecutiveSumLoop(inputArray, k):
    cop=k
    lis=[]
    i=0
    while i < len(inputArray) - k:
        inpu = 0
        for j in range(i, cop):  # for-loop in place of sum
            inpu += inputArray[j]
        lis.append(inpu)
        cop += 1
        i += 1
    return max(lis)

时间是：

arrayMaxConsecutiveSum(np.random.rand(10000), 100)
111 ms ± 1.42 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

arrayMaxConsecutiveSumLoop(np.random.rand(10000), 100)
198 ms ± 4.16 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

因此 sum（您的版本）的实施速度大约快两倍！

更好的实施

我使用 numpy 重写了您的函数，使其更快！此实现没有嵌套循环并且是 O(n)，并且使用非常快的 numpy 库实现。

import numpy as np
def array_max_consecutive_sum(input_array, k):
    result = np.cumsum(input_array)
    return max(result[k:] - result[:-k])

array_max_consecutive_sum(np.random.rand(10000), 100)
688 µs ± 10.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

快了 150 多倍！

其他选项

顺便说一句，接受的答案（截至撰写本文时）给出了时间：

6.46 ms ± 147 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

快，但仍然只有上述 numpy 实现的十分之一。还有，结果是错误的。

Answer 2

是的，为了将所有元素加在一起，sum 代码必须遍历 inputArray（从 i 到 cop）。

此外，len(inputArray)还必须遍历整个数组才能得到它的长度。因此，您的解决方案是 O(n*k)

您可以使用以下方法将代码优化为复杂度为 O(n) 的解决方案：

def arrayMaxConsecutiveSum(inputArray, k):
    max = sum(inputArray[0:k])
    bucket = max
    count = len(inputArray)
    for i in range(1, 1 + count - k):
        prev = inputArray[i - 1]
        cur = inputArray[i + k - 1]
        bucket += cur - prev
        if bucket > max:
            max = bucket
    return max

这个算法只在数组上循环一次。想象一下，有一个固定的桶沿着一条线滑动。当您增加 i 时，桶需要取出最新的项目，但最旧的项目会从后面掉下来。使用此逻辑，您最多只需要查看每个项目两次 - 当您将其添加到存储桶中时，以及当您将其从另一端移除时。

** 请注意，为清楚起见，省略了特殊情况处理**

sum() 是否在 python3 中占用循环的执行时间

does sum() take the execution time of a loop in python3

execution-time

python-3.x

更好的实施

其他选项