时间戳

首页 > 解决方案 > 如何对子矩阵求和

python - 如何对子矩阵求和

问题描述

我需要为每个子矩阵制作值的总和。例如，如果我有 [[1,1,2],[2,3,4]]，则结果矩阵将是：

 M[0][0] = 1 M[0][1] = 1+1 = 2 M[0][2] = 1+1+2 = 4
 M[1][0] = 1+2 = 3 M[1][1] = 1+1+2+3 = 7 M[1][2] = 1+1+2+2+3+4 = 13

或者

M = [[1,2,4],[3,7,13]]

我做了这个代码

`N = []
 M = []
 summ = 0
 n= list(map(int, input().split()))
 while n != []:
     N.append(n)
     n = list(map(int, input().split()))
 for i in range(len(N)):
     M.append([0 for i in range(len(N[0]))])
     summ = 0
     for j in range(len(N[0])):
         summ += N[i][j]
         M[i][j] = M[i-1][j] + summ `

问题是当矩阵很大时会变得非常慢。我需要在 0.5 秒内最大求解 100x100 矩阵

有谁能够帮我？无需导入包！！`

标签： pythonmatrixtimesumsubmatrix

解决方案

为了速度，您真的希望使用NumPy，它除了为矩阵提供更简洁的代码外，还比基础 Python 快得多。从您的小示例中，您可以numpy.cumsum()在不同的轴上使用两次：

import numpy as np

arr = np.array([[1,1,2],[2,3,4]])
out = arr.cumsum(axis=1).cumsum(axis=0)

print(out)

给出：

array([[ 1,  2,  4],
       [ 3,  7, 13]], dtype=int32)

旁注：在 Windows 上，默认int类型是 32 位，并且可能会在大矩阵/大数字上静默溢出，因此如果在 Windows 上cumsum()，您可能会想要。arr = np.array([[1,1,2],[2,3,4]]).astype(np.int64)

时间：

arr = np.arange(10000).reshape(100, 100)
%timeit out = arr.cumsum(axis=1).cumsum(axis=0)
56.3 µs ± 4.96 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

因此，比您的要求快数千倍。

推荐阅读