python - 在 python 中测试矩阵元素的最快方法

Question

我想创建一个矩阵，其中第 (i,j) 个条目是某个有序列表 L 的元素 i:j 的总和。我实际上想在总和超过 L 的最大成员的元素处停止.

例如，如果 L = [2,3,5,7]，则矩阵如下所示:

[ 2, 5, 0, 0 ]
[ 0, 3, 0, 0 ]
[ 0, 0, 5, 0 ]
[ 0, 0, 0, 7 ]

然后我想扫描矩阵并找到列表中最大数量的连续成员，这些成员加起来到列表中的另一个元素，如果这些子列表中有多个子列表，那么我选择具有最高数量的子列表和。所以在我之前的例子中，最大的数字是 2，因为 2+5=7 并且 7 在列表中。

对于非常大的列表，最快的方法是什么？ (数百万个元素)。我可以做类似的事情:

m = np.zeros(shape = (nmb, nmb))
for i in range(0, nmb):
    m[i, i:] = np.cumsum(L[i:])

print(m)

但我不确定如何在超过 L 中的最大值时停止 cumsum。事实上，我真的只需要矩阵的上三角，或者实际上只需要主对角线和一些上三角对角线，因为累加和超过 L 中的最高值比耗尽矩阵中的列数要早得多。

更新:

快一点:

m = np.zeros(shape = (nmb, nmb))
np.fill_diagonal(m, L)

for i in range(0, nmb):
    j = i + 1
    while  2*m[i,j-1]<L[-1]:
        m[i, j] = m[i, j-1] + m[j, j]
        j+=1
print(m) 

似乎过滤并挑选出最大的条纹仍然很慢，也许我不应该使用有这么多零的矩阵

Answer 1

好的，所以我一直走到 10,000 个元素(更多的元素开始接近内存限制，这对速度本身来说是一个问题)我发现这相当快(在我的机器上不到 1 秒)

import numpy as np
import time

Cl1 = time.time()
L = np.random.randint(1,100,10000)
nmb = np.size(L)
m = np.zeros(shape = (nmb, nmb))
np.fill_diagonal(m, L)


for i in range(nmb-1):
    j = i+1  
    if np.sum(L[i:j+1])<=np.max(L):
        m[i,j] = np.sum(L[i:j+1])  


Cl2 = time.time()
print(m)
print(Cl2-Cl1)