主页 / coding / 问题 / 79135714
Accepted
KyroAsks
Asked: 2024-10-29 10:58:04 +0800 CST

将 Python 中的二维数组划分为逆时针块的最快方法

  • 772

给定一个大小为 (W,H) 的二维数组，例如 (3,4)。您可以将该二维数组中的每个点视为矩形面片的一个角。我想将该数组分成各个面片，如下面的示例所示。这种划分的顺序是逐行进行的，对于每个面片，我们从左上角的像素开始逆时针移动。这意味着面片 1 是 [A[0,0],A[1,0],A[1,1],A[0,1]]。然后面片 2 是 [A[0,1],A[1,1],A[1,2],A[0,2]]。面片的数量为 (w-1) (h-1)，最终输出是另一个大小为 ((w-1) (h-1),4) 的二维数组（例如此处为 (6,4)），其中 6 是面片的数量，4 是面片角的数组值，如上所述，以逆时针方式排列。

现在我的问题是关于仅使用简单的 python 函数和 numpy 在 python 中生成这些补丁的最有效方法。

太感谢了。

我可以编写一个双 for 循环来完成下面的工作，但我想知道是否有更好的算法可以提供更快的性能：

import numpy as np
A=np.array([[ 0,  1,  2,  3],
       [ 4,  5,  6,  7],
       [ 8,  9, 10, 11]])
H=A.shape[0]
W=A.shape[1]
patches=[]
for y in range(H-1):
    for x in range(W-1):
       patches.append([A[0+y,0+x],A[1+y,0+x],A[1+y,1+x],A[0+y,1+x]])


patches =np.array(patches)
print(patches)
python

1 个回答

  1. Best Answer

    假设你打错了，意思是

    for y in range(H-1):
    for x in range(W-1):

    然后你可以得到相同的结果：

    # indeces offsets for a counterclockwise 2x2 block
i = np.array([0,1,1,0])
j = np.array([0,0,1,1])

# top corner indeces for the (H-1)x(W-1) 2D array of blocks
h, w = np.meshgrid(np.arange(H-1), np.arange(W-1), indexing='ij')

# turn to a flat 1D array of blocks
h = h.flatten()
w = w.flatten()

# add the ofsets for every block (create extra axis and broadcast)
h = h[:,None]+i
w = w[:,None]+j

# use advanced indexing to "sample at given indeces
A[h,w]

    比较（在那个玩具示例上我的速度慢了约 3 倍，但在更大的阵列上快了约 10 倍）：

    def yours(A):
    H=A.shape[0]
    W=A.shape[1]
    grids=[]
    for y in range(H-1):
        for x in range(W-1):
           grids.append([A[0+y,0+x],A[1+y,0+x],A[1+y,1+x],A[0+y,1+x]])
    grids=np.array(grids)
    return grids
    
def mine(A):
    i = np.array([0,1,1,0])
    j = np.array([0,0,1,1])
    H = A.shape[0]
    W = A.shape[1]
    h, w = np.meshgrid(np.arange(H-1), np.arange(W-1), indexing='ij')
    h = h.flatten()[:,None]+i
    w = w.flatten()[:,None]+j
    return A[h,w]


A = np.arange(30*20).reshape((30,20))    

assert np.all(yours(A) == mine(A))


%timeit yours(A)
# 261 µs ± 229 ns per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

%timeit mine(A)
# 27.4 µs ± 46.4 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
    • 1

相关问题