如何使用numpy和strides来提高循环的性能

Question

我是新来的纽比，刚刚听说了跨步，但我很难弄清楚如何使用它们。我有一个很慢的小循环，它似乎是一个很好的例子，可能会有很大的进步。在

def semivariogram( ds, band, lag ):
    width = ds.RasterXSize
    height = ds.RasterYSize
    data = band.ReadAsArray( 0, 0, width, height ).astype(np.float)
    #print 'w: {}, h: {}'.format(width, height)

    sumw = 0.0
    sumh = 0.0
    for i in range(width-lag):
        for j in range(height-lag):
            sumw += data[i+lag,j]-data[i,j]
            sumh += data[i,j+lag]-data[i,j]

    Nh2 = 2.0*(width-lag)*(height-lag)

    return [sumw/Nh2, sumh/Nh2, (sumw/Nh2+sumh/Nh2)/2.0]

行：

^{pr2}$

将图像的一个波段读入浮点数组。并且ds是一个像这样的图像的句柄：

ds = gdal.Open('test.tif')

Answer 1

好吧，让我们一步一步来。在

你有：

sumw = 0.0
sumh = 0.0
for i in range(width-lag):
    for j in range(height-lag):
        sumw += data[i+lag,j]-data[i,j]
        sumh += data[i,j+lag]-data[i,j]

为了清楚起见，我们把它分成两个循环

^{pr2}$

我们可以把data[i,j+lag]写成data[:-lag,lag:][i,j]，data[i,j]是{}（对于我们的范围i和{}，并假设滞后！=0）。所以我们的循环变成：

sumw = 0.0
for i in range(width-lag):
    for j in range(height-lag):
        sumw += data[lag:,:-lag][i,j]-data[:-lag,:-lag][i,j]
sumh = 0.0
for j in range(height-lag):
    for i in range(width-lag):
        sumh += data[:-lag,lag:][i,j]-data[:-lag,:-lag][i,j]

但现在我们注意到，我们所有的循环都只是在一个简单的索引[i,j]上迭代，因此我们可以完全将它们展平：

sumw = (data[lag:,:-lag] - data[:-lag,:-lag]).sum()
sumh = (data[:-lag,lag:] - data[:-lag,:-lag]).sum()

通过发现差的和就是和的差，可以更快地实现这一点：

sumw = data[lag:,:-lag].sum() - data[:-lag,:-lag].sum()
sumh = data[:-lag,lag:].sum() - data[:-lag,:-lag].sum()

此时，您可以直观地考虑整个任务：

您需要sumw作为绿色轮廓上的和减去红色轮廓上的和，而{}是蓝色轮廓上的和减去红色轮廓上的和。在

在这里，我们可以进行两种简化：

1. 我们注意到第一个和中的大多数元素都从第二个和中移除。事实上，唯一不是这样的元素是 [:lag]和{}。所以这就变成了：

   sumw = data[-lag:,:-lag].sum() - data[:lag,:-lag].sum()
   sumh = data[:-lag,-lag:].sum() - data[:-lag,:lag].sum()
   

   如果lag < len(data) / 2，这将更快。在这里，我们设置sumw = green - (red + magenta)，和sumh = blue - (red + yellow)

2. 我们注意到第二个和是重复的

   sum_shared = data[:-lag,:-lag].sum()
   sumw = data[lag:,:-lag].sum() - sum_shared 
   sumh = data[:-lag,lag:].sum() - sum_shared