如何在 Python 中添加二维数组的相邻元素而不必使用嵌套循环？

Question

我想添加数组的相邻元素“3x3”并创建新数组。使用嵌套循环时，这段代码将被调用数千次，因此需要时间。

import tensorflow as tf
import numpy as np

rows=6
cols=8

array1 = np.random.randint(10, size=(rows, cols))
print(array1)

array2=np.zeros((rows-2,cols-2))

for i in range(rows-2):
    for j in range(cols-2):
        array2[i,j]=np.sum(array1[i:i+3,j:j+3])# print()
        
print("output\n",array2)


##My output
    [[9 4 9 6 1 4 9 0]
     [2 3 4 2 0 0 9 0]
     [2 8 9 7 6 9 4 8]
     [6 3 6 7 7 0 7 5]
     [2 1 4 1 7 6 9 9]
     [1 1 2 6 3 8 1 4]]
    output
     [[50. 52. 44. 35. 42. 43.]
     [43. 49. 48. 38. 42. 42.]
     [41. 46. 54. 50. 55. 57.]
     [26. 31. 43. 45. 48. 49.]]

矢量化可以解决这个问题。然而，我尝试了不同的技术，但从未有过任何运气，例如重塑然后添加数组，只使用一个带有大小行或列的循环。 注意：在我的项目中，行和列的大小可能非常大。 它类似于带有内核的 2D 卷积。问题是，是否可以在不使用循环的情况下实现它？ 或至少将其降低以具有更小的时间复杂度“仅采用行或列作为循环的大小”。

Answer 1

这里应该使用部分求和。并且您可以在 1 个操作中找到任何点。

如果您将它用于小号码。没有太多的性能差异。但是如果你用大数字检查它。您会看到性能差异。

行 = 行数

列数 = 列数

innerrow = 你的目标行。 *//in your example(3)*

innercol = 你的目标上校。 *//in your example(3)*

使用您的代码：

O(rows x cols x innerrow x innercol)

O(2000 x 2000 x 200 x 2000)

但你可以用以下方法计算：

O(rows x cols)

示例：O(2000 x 2000)

import numpy as np

rows = 1000
cols = 2000

array1 = np.random.randint(10, size=(rows, cols))
array0 = array1
print(array1)

array2 = np.zeros((rows-100, cols-100))

for i in range(0, rows):
    for j in range(1, cols):
        array1[i][j] += array1[i][j-1]

for i in range(0, cols):
    for j in range(1, rows):
        array1[j][i] += array1[j-1][i]

for i in range(rows-100):
    for j in range(cols-100):
        sm = array1[i+100][j+100]
        if i-1 >= 0:
            sm -= array1[i-1][j+100]
        if j-1 >= 0:
            sm -= array1[i+100][j-1]
        if i-1 >= 0 and j-1 >= 0:
            sm += array0[i-1][j-1]
        array2[i, j] = sm

print("output\n", array2)

这是输出

[[1 9 1 9 2 0 3 8]
 [7 1 8 7 1 2 8 4]
 [7 1 5 4 8 3 9 0]
 [4 4 8 9 3 1 7 6]
 [2 5 9 9 3 6 7 2]
 [9 0 9 5 0 3 2 8]]
output
 [[40. 45. 45. 36. 36. 37.]
 [45. 47. 53. 38. 42. 40.]
 [45. 54. 58. 46. 47. 41.]
 [50. 58. 55. 39. 32. 42.]]

Answer 2

我找到了更适合这种情况的解决方案。使用 scipy.signal 模块中的函数 convolve2d 我使用函数 np.ones 和 np.array 将您的输入声明为一个 numpy 数组，并使用 convolve2d 将内核应用于图像的每个部分。这称为 Convolutional Filters and Kernels，它在 python.

的图像处理中被大量使用

In [50]: import numpy as np

In [55]: np.ones((3,3))
Out[55]: 
array([[1., 1., 1.],
       [1., 1., 1.],
       [1., 1., 1.]])

In [59]: input_matrix
Out[59]: 
array([[9, 4, 9, 6, 1, 4, 9, 0],
       [2, 3, 4, 2, 0, 0, 9, 0],
       [2, 8, 9, 7, 6, 9, 4, 8],
       [6, 3, 6, 7, 7, 0, 7, 5],
       [2, 1, 4, 1, 7, 6, 9, 9],
       [1, 1, 2, 6, 3, 8, 1, 4]])

In [60]: kernel
Out[60]: 
array([[1., 1., 1.],
       [1., 1., 1.],
       [1., 1., 1.]])

In [61]: from scipy.signal import convolve2d

In [63]: convolve2d(input_matrix, kernel, 'valid')
Out[63]: 
array([[50., 52., 44., 35., 42., 43.],
       [43., 49., 48., 38., 42., 42.],
       [41., 46., 54., 50., 55., 57.],
       [26., 31., 43., 45., 48., 49.]])

另外，其实这个速度还是挺快的。如您所见，即使在 1000x1000 矩阵中它也足够快。

In [68]: %timeit convolve2d(input_matrix, kernel, 'valid')
5.24 µs ± 21.2 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

In [69]: input = np.random.randint(10, size=(1000, 1000))

In [70]: %timeit convolve2d(input_matrix, kernel, 'valid')
41.6 ms ± 555 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Answer 3

@trenixjetix 的 solution against a numpy implementation of @n-ata's 的 micro-benchmark。即使对于相对较小的内核，第二种方法也更快。

import numpy as np
from scipy.signal import convolve2d

def partial_sum(array1, n):
    array1 = array1.cumsum(1).cumsum(0)
    res = array1.copy()
    res[:,n:] -= array1[:,:-n]
    res[n:] -= array1[:-n]
    res[n:,n:] += array1[:-n,:-n]
    return res[n-1:,n-1:]

rows = 500
cols = 500
n = 50   # relatively small n, since convolve2d becomes slow
np.random.seed(42)
array1 = np.random.randint(10, size=(rows, cols))

%timeit convolve2d(array1, np.ones((n,n), int), 'valid')
#1 loop, best of 5: 1.3 s per loop

%timeit partial_sum(array1, n)
#100 loops, best of 5: 3.36 ms per loop

partial_sum 的正确性通过与 convolve2d 结果的比较得到验证。

np.testing.assert_equal(partial_sum(array1, n), convolve2d(array1, np.ones((n,n), int), 'valid'))

增长的运行时复杂度 n

用于此基准测试的代码

import perfplot

perfplot.show(
    setup=lambda n: (np.random.randint(10, size=(500, 500)), n),
    kernels=[
        lambda a, n: partial_sum(a, n),
        lambda a, n: convolve2d(a, np.ones((n,n), int), 'valid')
    ],
    labels=['partial_sum','convolve2d'],
    n_range=[k for k in range(10,80,5)]
)

如何在 Python 中添加二维数组的相邻元素而不必使用嵌套循环？

How to add neighboring elements of 2D array in Python without having to use nested loops?

python

arrays

numpy

matrix

tensorflow