np.argsort () в жестком ранге

Question

Как np.argsort() работает со связями?

test = [1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0, 1.0, 1.0, 0.0, 0.0, 1.0, 0.0, 1.0, 1.0, 0.0, 1.0, 1.0, 0.0, 1.0]
np.argsort(test)

Почему индекс 20 занимает первое место в результате?

Я проверил другие ресурсы, но не смог найти объяснение,Индексы назначаются случайным образом там, где есть связи?Спасибо!

array([20,  4,  5,  8,  9, 10, 11, 23, 17, 14, 15,  0, 22, 21, 19, 18, 12,
       13,  7,  6,  3,  2,  1, 16, 24], dtype=int64) 

Answer 1

Я думаю, что нет одного ответа на это:

>>> np.argsort(test, kind="quicksort")
array([20,  4,  5,  8,  9, 10, 11, 23, 17, 14, ... ])
>>> np.argsort(test, kind="mergesort")
array([ 4,  5,  8,  9, 10, 11, 14, 15, 17, 20, ... ])
>>> np.argsort(test, kind="stable")
array([ 4,  5,  8,  9, 10, 11, 14, 15, 17, 20, ... ])
>>> np.argsort(test, kind="heapsort")
array([17, 11, 20,  8, 15, 14, 23, 10,  4,  9, ... ])

Я думаю, мы могли бы прочитать код , чтобы действительно понять, почему это происходит, но я думаю, что порядокявляется произвольным и, вероятно, является следствием, а не выбором.

С другой стороны, если вам нужна пользовательская под-сортировка для связей, вы можете использовать np.unique.В качестве примера я просто отсортирую вывод quicksort, чтобы он имитировал вывод скажем mergesort:

ranks = np.argsort(test, kind="quicksort")
# split the indexes so we can sort them independently:
_, counts = np.unique(test, return_counts=True)
cuts = np.cumsum(counts)[:-1]
rank_bins = np.split(ranks, cuts)
sorted_rank_bins = [np.sort(b) for b in rank_bins]
# glue them back together: 
ranks = np.concatenate(sorted_rank_bins)

Теперь ranks содержит:

array([ 4,  5,  8,  9, 10, 11, 14, 15, 17, 20, 23,  0,  1,  2,  3,  6,  7,
       12, 13, 16, 18, 19, 21, 22, 24])

Эторешение довольно длинное, я думаю, что можно прийти с более коротким / быстрым решением этого.Также здесь я просто отсортировал индексы по их значениям, но вы можете представить любой другой порядок.

Answer 2

В других ответах упоминалось, что np.argsort возвращает индексы, которые будут сортировать массив, и что эти индексы зависят от алгоритма сортировки, например:

>>> np.random.seed(0)  # for reproducibility
>>> a = np.random.randint(0, 5, 20)
>>> np.argsort(a, kind='mergesort')
array([ 2,  6,  8, 11, 16,  0,  1,  3, 12, 17, 18, 19,  9,  5,  7, 10, 13,
       14, 15,  4])
>>> np.argsort(a, kind='quicksort')
array([ 2, 16, 11,  6,  8,  0, 17, 12, 18, 19,  3,  1,  9, 10,  5, 13, 14,
       15,  7,  4])

I 'Хотелось бы перейти к , почему .

Вкратце, алгоритмы сортировки могут быть стабильными или нестабильными.Стабильность в этом контексте означает, что они не изменяют относительный порядок элементов, которые сравниваются равными .

Представьте, что мы «помечаем» элементы с некоторым значением, чтобы показать, что они являются различными объектами.Например:

unsorted = [4 (star), 3 (cube), 3 (star), 4 (cube)]

Стабильная сортировка, такая как mergesort, будет всегда возвращать следующее:

sorted = [3 (cube), 3 (star), 4 (star), 4 (cube)]

Это потому, что 3 (cube) был раньше3 (star) и 4 (star) до 4 (cube).

И наоборот, нестабильная сортировка, такая как быстрая сортировка, может возвращать элементы в любом порядке, за исключением того, что все 3 должны предшествовать всем 4.

Когда мы применим это к нашей первоначальной проблеме, мы можем понять, почему она возникла.Даже если элементы имеют одинаковое значение (они сравниваются одинаково), они не имеют одинаковую идентичность (это разные объекты).Соответственно, в каждом «кластере» равных объектов они могут быть упорядочены по-разному в зависимости от алгоритма сортировки.

Answer 3

numpy.argsort() возвращает индексы массива, которые будут сортировать элементы массива. В случае наличия дублированных записей возвращаемые индексы зависят от типа алгоритма сортировки, который используется для сортировки массива. На основании этого выбора вы можете увидеть другие результаты, как показано ниже:

# input
In [90]: a
Out[90]: 
array([1., 1., 1., 1., 0., 0., 1., 1., 0., 0., 0., 0., 1., 1., 0., 0., 1.,
       0., 1., 1., 0., 1., 1., 0., 1.])

# more intuitive
In [85]: np.argsort(a, kind='mergesort')
Out[85]: 
array([ 4,  5,  8,  9, 10, 11, 14, 15, 17, 20, 23,  0,  1,  2,  3,  6,  7,
       12, 13, 16, 18, 19, 21, 22, 24])

# default choice
In [86]: np.argsort(a, kind='quicksort')
Out[86]: 
array([20,  4,  5,  8,  9, 10, 11, 23, 17, 14, 15,  0, 22, 21, 19, 18, 12,
       13,  7,  6,  3,  2,  1, 16, 24])

In [88]: np.argsort(a, kind='heapsort')
Out[88]: 
array([17, 11, 20,  8, 15, 14, 23, 10,  4,  9,  5, 13,  6, 12, 24,  2, 21,
       19, 18, 16,  7, 22,  3,  1,  0])

# more intuitive
In [89]: np.argsort(a, kind='stable')
Out[89]: 
array([ 4,  5,  8,  9, 10, 11, 14, 15, 17, 20, 23,  0,  1,  2,  3,  6,  7,
       12, 13, 16, 18, 19, 21, 22, 24])