arrays - (arg) 对沿每个维度排序的扁平 nD 数组进行排序的最快方法？

Question

问题本身与语言无关。我将使用 python 作为我的示例，主要是因为我认为它很好地证明了这一点。

---

我有一个形状为 (n1, n2, ..., nN) 的 N 维数组，它在内存中是连续的(c 顺序)并填充有数字。对于每个维度本身，数字按升序排列。这种数组的二维示例是:

>>> import numpy as np
>>> n1 = np.arange(5)[:, None]
>>> n2 = np.arange(7)[None, :]
>>> n1+n2
array([[ 0,  1,  2,  3,  4,  5,  6],
       [ 1,  2,  3,  4,  5,  6,  7],
       [ 2,  3,  4,  5,  6,  7,  8],
       [ 3,  4,  5,  6,  7,  8,  9],
       [ 4,  5,  6,  7,  8,  9, 10]])

在这种情况下，每一行中的值都是升序的，每一列中的值也是升序的。一维示例数组是

>>> n1 = np.arange(10)
>>> n1*n1
array([ 0,  1,  4,  9, 16, 25, 36, 49, 64, 81])

我想获得一个包含索引的列表/数组，这些索引将按升序对 nD 数组的扁平版本进行排序。我所说的展平数组是指我将 nD 数组解释为等效大小的一维数组。排序不必保留顺序，即索引相同数字的索引顺序无关紧要。例如

>>> n1 = np.arange(5)[:, None]
>>> n2 = np.arange(7)[None, :]
>>> arr = n1*n2
>>> arr
array([[ 0,  0,  0,  0,  0,  0,  0],
       [ 0,  1,  2,  3,  4,  5,  6],
       [ 0,  2,  4,  6,  8, 10, 12],
       [ 0,  3,  6,  9, 12, 15, 18],
       [ 0,  4,  8, 12, 16, 20, 24]])
>>> np.argsort(arr.ravel())
array([ 0, 28, 14,  7,  6, 21,  4,  3,  2,  1,  5,  8,  9, 15, 22, 10, 11,
       29, 16, 12, 23, 17, 13, 18, 30, 24, 19, 25, 31, 20, 26, 32, 27, 33,
       34], dtype=int64)

扁平化数组的标准排序可以做到这一点；但是，它没有利用数组已经部分排序的事实，所以我怀疑存在更有效的解决方案。 最有效的方法是什么？

---

评论询问我的用例是什么，以及我是否可以提供一些更真实的测试数据来进行基准测试。这是我遇到这个问题的方式:

Given an image and a binary mask for that image (which selects pixels), find the largest sub-image which contains only selected pixels.

在我的例子中，我对图像应用了透视变换，并希望裁剪它以便没有黑色背景，同时尽可能多地保留图像。

from skimage import data
from skimage import transform
from skimage import img_as_float

tform = transform.EuclideanTransform(
    rotation=np.pi / 12.,
    translation = (10, -10)
    )

img = img_as_float(data.chelsea())[50:100, 150:200]
tf_img = transform.warp(img, tform.inverse)
tf_mask = transform.warp(np.ones_like(img), tform.inverse)[..., 0]

y = np.arange(tf_mask.shape[0])
x = np.arange(tf_mask.shape[1])
y1 = y[:, None, None, None]
y2 = y[None, None, :, None]
x1 = x[None, :, None, None]
x2 = x[None, None, None, :]

y_padded, x_padded = np.where(tf_mask==0.0)
y_padded = y_padded[None, None, None, None, :]
x_padded = x_padded[None, None, None, None, :]
y_inside = np.logical_and(y1[..., None] <= y_padded, y_padded<= y2[..., None])
x_inside = np.logical_and(x1[..., None] <= x_padded, x_padded<= x2[..., None])
contains_padding = np.any(np.logical_and(y_inside, x_inside), axis=-1)

# size of the sub-image
height = np.clip(y2 - y1 + 1, 0, None)
width = np.clip(x2 - x1 + 1, 0, None)
img_size = width * height

# find all largest sub-images
img_size[contains_padding] = 0
y_low, x_low, y_high, x_high = np.where(img_size == np.max(img_size))
cropped_img = tf_img[y_low[0]:y_high[0]+1, x_low[0]:x_high[0]+1]

算法效率很低；我知道。这个问题的有趣之处在于 img_size，它是一个 (50,50,50,50) 如上所述排序的 4 维数组。目前我这样做:

img_size[contains_padding] = 0
y_low, x_low, y_high, x_high = np.where(img_size == np.max(img_size))

但使用适当的 argsort 算法(我可以提前中断)这可能会变得更好。

Answer 1

我会使用部分合并排序和分而治之的方法来做到这一点。您从前两个数组开始。

[0,  1,  2,  3,  4,  5,  6],//<- This
[ 1,  2,  3,  4,  5,  6,  7],//<- This
....

然后你可以像这样合并它们(类似 Java 的语法):

List<Integer> merged=new ArrayList<>();
List<Integer> firstRow=... //Same would work with arrays
List<Integer> secondRow=...
int firstCnter=0;
int secondCnter=0;
while(firstCnter<firstRow.size()||secondCnter<secondRow.size()){
  if(firstCnter==firstRow.size()){ //Unconditionally add all elements from the second, if we added all the elements from the first
     merged.add(secondRow.get(secondCnter++)); 
  }else if(secondCnter==secondRow.size()){
     merged.add(firstRow.get(firstCnter++));
  }else{ //Add the smaller value from both lists at the current index.
    int firstValue=firstRow.get(firstCnter);
    int secondValue=secondRow.get(secondCnter);
    merged.add(Math.min(firstValue,secondValue));
    if(firstValue<=secondValue)
       firstCnter++;
    else
       secondCnter++;
  }
}

之后你可以合并接下来的两行，直到你有:

[0,1,1,2,2,3,3,4,4,5,5,6,7]
[2,3,3,4,4,5,5,6,6,7,7,8,8,9]
[4,5,6,7,8,9,10] //Not merged.

继续合并。

[0,1,1,2,2,2,3,3,3,4,4,4,4,5,5,5,6,6,6,7,7,7,8,8,9]
[4,5,6,7,8,9,10]

之后，最后的合并:

[0,1,1,2,2,2,3,3,3,4,4,4,4,4,5,5,5,5,6,6,6,6,7,7,7,7,8,8,8,9,9,10]

我不知道时间复杂度，但应该是一个可行的解决方案