python - 加速必须遍历整个列表的 Python 代码

Question

我有一个问题，我需要(至少非常确定)遍历整个列表来解决。问题是找出列表中最大数量的连续数字，这些数字加起来等于该列表中的另一个(更大的)元素。如果没有那么我们就取列表中的最大值作为候选求和，1作为最大的连续元素数。

我的通用代码可以工作，但对于大型列表(>500,000 个元素)来说不太好。我只是在寻找有关如何以不同方式解决问题的技巧。我目前的做法:

L = [1,2,3,4,5,6,7,8,9,10]
candidate_sum = L[-1]
largest_count = 1
N = len(L)
i = 0

while i < N - 1:
    s = L[i]
    j = 0
    while s <= (N - L[i + j + 1]):
        j += 1
        s += L[i+j]
        if s in L and (j+1) > largest_count:
             largest_count = j+1
             candidate_sum = s
    i+=1

在这种情况下，答案将是 [1,2,3,4]，因为它们相加为 10，长度为 4(显然，此示例 L 是一个非常简单的示例)。

然后我通过将初始 while 循环条件更改为:

while i < (N-1)/largest_count

这不是一个很好的假设，但基本认为数字的分布有点均匀，因此列表后半部分的两个数字平均大于列表中的最后一个数字，因此不合格。

我正在寻找:

• 可能的瓶颈
• 关于不同尝试方法的建议

Answer 1

• 严格升序:没有重复的元素或子序列，单一可能的解决方案

• Arbitrary-spaced:没有算术捷径，必须用暴力运算

使用指针运算的高效 C 实现，数字类型上的准多态:

#define TYPE int

int max_subsum(TYPE arr [], int size) {
   int max_length = 1;

   TYPE arr_fst = * arr;
   TYPE* num_ptr = arr;

   while (size --) {
      TYPE num = * num_ptr++;

      TYPE* lower = arr;
      TYPE* upper = arr;

      TYPE sum = arr_fst;
      int length = 1;

      for (;;) {
         if (sum > num) {
            sum -= * lower++;
            -- length;
         }
         else if (sum < num) {
            sum += * ++upper;
            ++ length;
         }
         else {
            if (length > max_length) {
               max_length = length;
            }

            break;
         }
      }
   }

   return max_length;
}

num 上的主循环是可并行的。使用 arr 的动态数组列表类型和 for each 循环相对直接地转换为 Python 3:

def max_subsum(arr):
   max_len = 1
   arr_fst = arr[0]

   for n in arr:
      lower = 0
      upper = 0

      sum = arr_fst

      while True:
         if sum > n:
            sum -= arr[lower]
            lower += 1
         elif sum < n:
            upper += 1
            sum += arr[upper]
         else:
            sum_len = upper - lower + 1

            if sum_len > max_len:
               max_len = sum_len

            break

   return max_len

这个max_subsum 是偏函数； Python 列表可以为空。该算法适用于提供快速索引和静态类型运算的类 C 编译命令式语言。两者在 Python 中都比较昂贵。一个(完全定义的)算法与你的算法非常相似，使用 set 数据类型进行更高效的通用量化，并避免 Python 的动态类型算法，可以更有效地解释:

def max_subsum(arr):
   size = len(arr)
   max_len = 0

   arr_set = set(arr)

   for i in range(size):
      sum = 0
      sum_len = 0

      for j in range(i, size):
         sum_mem = sum + arr[j]

         if num_mem not in arr_set:
            break

         sum = sum_mem
         sum_len += 1

      if sum_len > max_len:
         max_len = sum_len

   return max_len