Блог

Как 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) 
  

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

В других ответах упоминалось, что 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])
  

Я хотел бы вдаваться в почему.

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

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

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

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

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

Это потому, что 3 (cube) появилось раньше 3 (star) и 4 (star) раньше 4 (cube) .

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

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

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

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

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