小编mad*_*rog的帖子

我目前正在尝试计算10.000 x 10.000数组值中所有子方格总和的总和.例如,如果我的数组是:

1 1 1 
2 2 2
3 3 3 

我希望结果如下:

1+1+1+2+2+2+3+3+3                        [sum of squares of size 1]
+(1+1+2+2)+(1+1+2+2)+(2+2+3+3)+(2+2+3+3) [sum of squares of size 2]
+(1+1+1+2+2+2+3+3+3)                     [sum of squares of size 3]
________________________________________
68

所以,作为第一次尝试,我写了一个非常简单的python代码来做到这一点.因为它在O(k ^ 2.n ^ 2)中(n是大数组的大小,k是我们得到的子方形的大小),处理非常长.我在O(n ^ 2)中写了另一个算法来加速它:

def getSum(tab,size):
    n = len(tab)
    tmp = numpy.zeros((n,n))

    for i in xrange(0,n):
        sum = 0
        for j in xrange(0,size):
            sum += tab[j][i]
        tmp[0][i] = sum

        for j in xrange(1,n-size+1):
            sum += (tab[j+size-1][i] - tab[j-1][i])
            tmp[j][i] …