как сделать сумму подматриц - PullRequest
Новая
       33

как сделать сумму подматриц

0 голосов
/ 30 октября 2018

мне нужно сделать для каждой подматрицы сумму значений. например, если у меня есть [[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 `

проблема в том, что когда матрица большая, она становится очень медленной. мне нужно решить матрицу 100x100 при максимуме в 0,5 сек

Кто-нибудь может мне помочь? БЕЗ ИМПОРТНЫХ ПАКЕТОВ !! `

1 Ответ

0 голосов
/ 30 октября 2018

Для скорости вы действительно хотите использовать 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-битный, а cumsum() может молча переполняться при больших матрицах / больших числах, поэтому вам, вероятно, потребуется arr = np.array([[1,1,2],[2,3,4]]).astype(np.int64), если в Windows.

Тайминги: 

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)

Итак, в тысячи раз быстрее, чем требуется.

...