python - 如何减少python列表算法中k个连续数字的最大和的执行时间

Question

我的问题是找出给定列表中 k 个连续数字的最大总和。例如:l = [2,3,5,1,6] 那么对于 k =2，结果将是 8(3+5)。我知道一个好的算法是首先找到前 k 个数字的总和，然后将下一个元素添加到总和中并减去 k 个数字的第一个元素:

2+3 => 5
5-2+5 => 8
... 

我想到了这个:

def f(l, k):
    M= 0
    temp = sum(l[0:k])
    for i in range(1,k):
        temp += a[l+1]-l[i-1]
        if temp > M:
            M = temp
    return M

但不幸的是它只适用于 k = 2？所以我有两个问题:

1. 为什么我的代码不能使用更高的 k？(错误是什么，我该如何修复？)
2. 有没有更好的方法(时间方面)来解决主要问题？如果例如 len(l) = 100000 和 k = 2000，这个算法是否足够快？我如何仅通过查看代码？

Answer 1

您描述的思路是正确的，但是您的实现是错误的。

1. 您的变量 M 等同于下面的 cumax。它应该是初始化为前 k 项的总和，而不是 0。
2. 要考虑的 k 数字的起始范围应该是 N - k + 1，对于大小为 k 的窗口，序列中的最大位置。

3. 您的temp 等同于cusum。 temp += a[l+1]-l[i-1] 行是错误的。我不知道你从哪里得到a。我我想你的意思是 temp += l[i + k] - l[i - 1]。

   def f(l, k):
       assert len(l) >= k
   
       # Start of max sum of k consecutive number
       start_idx = 0
       # Current max sum of k consecutive number
       cumax = cusum = sum(l[:k])
   
       # Slide a window of size k from second element onwards
       N = len(l)
       for i in range(1, N - k + 1):
           # Subtract element before start of window and add rightmost element
           cusum = cusum + l[i + k - 1] - l[i - 1]
   
           # Update start of and latest max sum of k consecutive number if
           # necessary
           if cusum > cumax:
               cumax = cusum
               start_idx = i
   
       return start_idx, cumax
   

时间复杂度为O(N)，内存复杂度为O(1)。实际上，对于长序列，@dobkind 使用卷积的方法可能是最快的。

def f_convolve(l, k):
    start_idx = np.argmax(np.convolve(l, np.ones(k,), 'valid'))
    return start_idx, np.sum(l[start_idx : start_idx + k])

如果您有空闲内存并且 l 不是太大，这个实现比前两个更好

def f_numpy_cusum(l, k):
    cumsums = np.cumsum(l)
    cumsums[k :] -= cumsums[: len(cumsums) - k ]
    cumsums = cumsums[ k- 1:]
    start = np.argmax(cumsums)
    return start, np.sum(l[start : start + k])

len(l) = 100000 和 k = 2000 的上述 3 个函数的运行时间是

f每个循环 32.6 毫秒 +- 78.5 us(7 次运行的平均值 +- 标准偏差，每次 10 次循环)

f_convolve每个循环 26.3 毫秒 +- 183 us(7 次运行的平均值 +- std.dev，每次 10 次循环)

f_numpy_cusum每个循环 718 us +- 3.81 us(7 次运行的平均值 +- std.dev，每次 1000 次循环)