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

Question

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

---

我有一个 N 维的形状数组，(n1, n2, ..., nN)它在内存中是连续的（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)

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

---

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

给定图像和该图像的二进制掩码（选择像素），找到仅包含选定像素的最大子图像。

就我而言，我对图像应用了透视变换，并希望对其进行裁剪，以便在保留尽可能多的图像的同时没有黑色背景。

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)如上所述排序的 4D 数组。目前我做：

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

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

标签： arrayssortinglanguage-agnostic

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]

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