Индекс Numpy, отсортированный по целочисленному массиву, с сохранением порядка сортировки
У меня есть массив x и результат его сортировки i. Мне нужно отсортировать x (и y, здесь неважно) по i сотни раз. Поэтому невозможно отсортировать данные дважды, все должно быть достигнуто посредством первоначальной сортировки i.
Если я возьму x[i], он вернет отсортированный x, как и ожидалось. Однако теперь я хочу использовать только определенные строки от x до n. Итак, x[n] возвращает значения x, как и ожидалось.
Моя проблема в том, что мне нужно отсортировать эти x[n] через i (и мне придется сделать то же самое для y[n].
# Example data
x = np.array([14, 15, 9, 6, 19, 18, 4, 11, 10, 0])
i = np.argsort(x)
n = np.array([2, 5, 7, 8])
#x[n] -> array([ 9, 18, 11, 10])
Желаемый результат: index_sort(x, n, i) = array([ 9, 10, 11, 18])
Несколько простых (неудачных) попыток:
x[n][i] -> Ошибка индексации, так как x теперь слишком мал. x[i[n]] -> array([ 6, 11, 15, 18]), отсортировано, но содержит неправильные данные x[i][n] -> То же самое
Для большего контекста: я создаю модель дерева решений определенного типа. Для каждого слоя дерева мне нужна отдельная операция n. Сортировка становится непомерно дорогой, и даже проверка членства в наборе через np.isin уже может быть слишком медленной. Моя интуиция (хотя, возможно, и ошибочная) подсказывает, что этого можно добиться только с помощью индексации, без необходимости сортировки или проверки членства в наборе.
Для всех этих слоев x и i остаются прежними, но каждый раз используется другой n.
Неужели нельзя просто отсортировать x[n]? Не нужно использовать i
Извините, я добавил уточнение: мне нужно отсортировать и другие массивы по i и n, поэтому прямая сортировка x не сработает. Кроме того, эта процедура повторяется сотни раз и станет основным узким местом кода.
Рассмотрим эти индексы подробно. Не пробуйте что-то случайно, надеясь, что что-то волшебное сработает. i индексы x, переставляющие все элементы. n также индексирует x, выбирая подмножество значений (может быть, даже дубликаты?). Они не связаны между собой. Но как выглядит argsort(i)? Я думаю, это можно использовать для «отсортировки» x[i].
@hpaulj Я на самом деле использую это argsort(i) немного позже, чтобы отменить сортировку с помощью np.argsort(i)[n], чтобы восстановить исходные индексы каждого из x_i. Я просто не понимаю, как на самом деле получить там сортировку.
Ответы 3
Попытка отсортировать x[n] исключительно на основе i не будет более эффективной.
i дает вам окончательный массив и позиции x, из которых можно извлечь значения для отсортированного порядка.
Это означает, что вы не можете индексировать i с помощью n.
Если вы действительно хотите отсортировать x[n] по i, вам нужно будет определить позиции i, соответствующие n, а затем изменить порядок на основе этого:
out = x[n][np.argsort(i[np.isin(i, n)])]
# array([ 9, 10, 11, 18])
Наиболее эффективной, скорее всего, будет сортировка x[n]:
out = np.sort(x[n])
Или, чтобы повторить процесс, сначала проиндексируйте, затем argsort и вы можете повторно использовать i:
i = np.argsort(x[n])
# array([0, 3, 2, 1])
out = x[n][i]
# array([ 9, 10, 11, 18])
Спасибо за ваше решение. Хотя это работает, оно все равно требует сортировки дважды. Теоретически в этом не должно быть необходимости, поскольку все порядки одинаковы, и это решение, которое я ищу.
@NotProbable ваш точный вариант использования неясен, но если вы хотите повторно использовать один и тот же n, то лучший подход - i = np.argsort(x[n]) ; x[n][i], который сортируется только один раз. Пожалуйста, приведите минимальный пример вашего реального варианта использования (покажите нам, что является переменным/повторно используемым).
Я добавил больше контекста для конкретного варианта использования. Основная проблема в том, что x большой и постоянный, но n будет постоянно меняться.
@NotProbable, тогда извините, но это невозможно, вам придется либо отсортировать срез (O(k*logk) сложность с k размером среза), либо проверить членство (O(n) сложность с n размером x). Будет ли тот или иной лучше, зависит от n и k.
Такое ощущение, что это проблема XY. В любом случае вот решение с np.in1d:
x[i[np.in1d(i, n)]]
array([ 9, 10, 11, 18])
Обратите внимание, что цель состоит в том, чтобы получить n в порядке i. вот что i[np.in1d(i, n)] делает
Разве np.in1d не использует внутреннюю сортировку? Теперь мне интересно, можно ли каким-то образом добиться тех же результатов, что и in1d, с помощью индексации
@NotProbable нет, это не так. Он использует сравнение членства. т.е. он выводит true только в том случае, если значение находится в другом наборе, в противном случае — false. Никакой сортировки не происходит.
In [263]: x = np.array([14, 15, 9, 6, 19, 18, 4, 11, 10, 0])
...: i = np.argsort(x)
...: n = np.array([2, 5, 7, 8])
i и n выполняют разные и несвязанные операции индексации. Оба делают копии (не просмотры), которые не сохраняют никакой информации об оригинале x:
In [264]: x[i]
Out[264]: array([ 0, 4, 6, 9, 10, 11, 14, 15, 18, 19])
In [265]: x[n]
Out[265]: array([ 9, 18, 11, 10])
Попробуем поработать с логической маской:
In [266]: m = np.zeros_like(x, dtype=bool)
In [267]: m[n] = True; m
Out[267]:
array([False, False, True, False, False, True, False, True, True,
False])
Он выбирает элементы из x так же, как и n (хотя дубликаты обрабатываются по-разному):
In [268]: x[m]
Out[268]: array([ 9, 18, 11, 10])
Теперь попробуйте применить сортировку к m:
In [269]: mi = m[i]; m
Out[269]:
array([False, False, True, False, False, True, False, True, True,
False])
Он выбирает нужные элементы из отсортированных x[i]:
In [270]: x[i][mi]
Out[270]: array([ 9, 10, 11, 18])
Мы также могли бы преобразовать эту логическую маску обратно в индексы:
In [272]: ni = np.nonzero(mi)[0]; ni
Out[272]: array([3, 4, 5, 8], dtype=int64)
In [273]: x[i][ni]
Out[273]: array([ 9, 10, 11, 18])
Вы имеете в виду
print(np.sort(x[n]))?