Сам вопрос по языковой агности c. Я буду использовать 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]])
В этом случае значения в каждой строке идут по возрастанию, а значения в каждом столбце тоже по возрастанию. Примерный массив 1D:
>>> 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)
Стандартная сортировка уплощенного массива может выполнить sh это; однако он не использует тот факт, что массив уже частично отсортирован, поэтому я подозреваю, что существует более эффективное решение. Как это сделать наиболее эффективно?
В комментарии спрашивается, каков мой вариант использования, и могу ли я предоставить более реалистичные c тестовые данные для сравнительного анализа. Вот как я столкнулся с этой проблемой:
Учитывая изображение и двоичную маску для этого изображения (которая выбирает пиксели), найдите самое большое вспомогательное изображение, которое содержит только выбранные пиксели.
В моем случае я применил перспективное преобразование к изображению и хочу обрезать его так, чтобы не было черного фона, сохранив при этом как можно большую часть изображения.
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))
, но с правильным алгоритмом сортировки (который я могу прервать раньше) это потенциально можно было бы сделать намного лучше.