我有一个简单的代码来分组和计算列表的内容。我担心完成这项工作需要多长时间。少于 100 个项目足够快，但数百个项目让我的 Mac 尖叫。我的列表中有多达 10000 个来自真实世界数据的项目。所以我需要知道如何优化这段代码:
v = [1,2,3,4,5,6,7,8,9,10]
v1 = v[:5]
l = len(v1)
a = [sum(v1[x:y]) for y in range(l+1) for x in range(y)]
d = {x:a.count(x) for x in a}
所以在 v 上有一个整数列表。数字可以从 1 到 4000。示例中的列表长度为 10，但如上所述，它将达到 10000。v1 只是一个拆分列表，用于处理较小的测试数据。
a 将每个项目作为单个实例并将所有前面的项目作为实例:
[1, 3, 2, 6, 5, 3, 10, 9, 7, 4, 15, 14, 12, 9, 5]
d 将所有项目分组并将它们计为键值对字典:
{1: 1, 2: 1, 3: 2, 4: 1, 5: 2, 6: 1, 7: 1, 9: 2, 10: 1, 12: 1, 14: 1, 15: 1}
似乎在 100 多个项目之后计算 a 已经变得非常繁重。 a 上有 500 个项目，我得到 276813 个 d 实例。因此，当列表中有 10000 个项目时，我预计 d 上会有多达 5559333 个项目，a 上可能有 100 倍以上。
更新
根据下面的评论和答案，通过下面的实现完成了一些改进:
def t5(v1):
l = len(v1)
d = {}
for x in range(0, l):
s = sum(v1[x:])
if s in d:
d[s] += 1
else:
d[s] = 1
for y in range(1, l-x):
s -= v1[-y]
if s in d:
d[s] += 1
else:
d[s] = 1
return d
我不知道如何使用 numpy 和/或 numba 进行更多优化。也许适合不同的单独问题......
请您参考如下方法:
您不断地为之前已经计算过的切片重新计算总和(每个 sum() 调用一个冗余循环)，而且您一直在通过切片创建大量新列表对象。
您可以使用动态规划来计算总和，从输入列表的末尾开始；您只需将“当前”值添加到列表中下一个值的总和中:
# v1 is the input list, l is len(v1)
sums = [0] * (l * (l + 1) // 2)
for x in range(l - 1, -1, -1):
for y in range(x, l):
i = (y * (y + 1) // 2) + x
sums[i] += v1[x] + (sums[i + 1] if x < y else 0)
这会将部分子序列的已计算总和加到下一个较长的子序列，避免了整个内部循环。这需要 O(N^2) 时间，而不是您的 O(N^3) 方法(其中 sum() 在每个子切片上循环最多 N 个元素)。
它将 x 和 y 坐标转换为最终的“三角形”，以避免必须创建更大的矩阵(或字典，这会产生额外的内存和散列开销).
那是因为你计算了列表中任意两点之间的切片；如果你采用一个矩阵，其中轴是每个切片中包含的开始和结束索引，你可以像这样对最终列表进行编号:
0 1 2 3 4
0 0 1 3 6 10
1 2 4 7 11
2 5 8 12
3 9 13
4 14
(空格是反向切片，重复，不在输出中使用)。对于每一行和每一列，您可以通过计算该列之前的三角形中有多少值加上行号来计算输出索引，或者 ((col * col + 1)//2) + row).
动态规划方法将已生成的后续值(索引下方的行)切片的总和添加到当前行的 v1 值:
v1 0 1 2 3 4
1 > 0 1 3 6 10 15
^ ^ ^ ^
2 > 1 2 5 9 14
^ ^ ^
3 > 2 3 7 12
^ ^
4 > 3 4 9
^
5 > 4 5
因此第 2 行第 4 列的值是 v1[2] 加上第 3 行第 4 列的已计算总和，或者在本例中为 2 + 12。对于那些行索引小于列索引的元素，只有一个已经计算好的总和；在位置 (3, 3) 在 (4, 3) 没有计算总和。
下一个问题是您的 list.count() 遍历您的整个 总和列表以计算一个数字出现的频率。因此，您的 {x:a.count(x) for x in a} 表达式创建了一个 O(N^2) 双循环；处理所有计数需要二次方时间。
使用 Counter() object改为生成该字典(Counter 是 dict 的子类):
from collections import Counter
d = Counter(sums)
Counter() 仅一次遍历所有元素以计算值；它只是为它在迭代过程中看到的每个值保留计数器。
