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

问：

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

我有一个 N 维形状数组，该数组在内存中是连续的（c 顺序）并填充了数字。对于每个维度本身，数字按升序排序。此类数组的 2D 示例如下：(n1, n2, ..., nN)

>>> 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]

该算法效率非常低;我知道。这个问题有趣的是，这是一个按上述顺序排列的 4D 数组。目前我做：img_size(50,50,50,50)

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

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

数组排序与语言无关

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]

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

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

Fastest way to (arg)sort a flattened nD-array that is sorted along each dimension?

评论

评论