Est-il possible d'utiliser argsort en ordre décroissant ?

Question

Considérons le code suivant :

avgDists = np.array([1, 8, 6, 9, 4])
ids = avgDists.argsort()[:n]

Cela me donne des indices de la n les plus petits éléments. Est-il possible d'utiliser ce même argsort par ordre décroissant pour obtenir les indices de n les éléments les plus élevés ?

Answer 1

Si vous niez un tableau, les éléments les plus bas deviennent les éléments les plus hauts et vice-versa. Par conséquent, les indices du tableau n les éléments les plus élevés sont :

(-avgDists).argsort()[:n]

Une autre façon de raisonner à ce sujet, comme mentionné dans le document commentaires c'est d'observer que les grands éléments viennent dernier dans la liste d'arguments. Ainsi, vous pouvez lire la queue de l'argsort pour trouver l'élément n les éléments les plus élevés :

avgDists.argsort()[::-1][:n]

Les deux méthodes sont O(n log n) en termes de complexité temporelle, car le argsort L'appel est le terme dominant ici. Mais la deuxième approche présente un avantage appréciable : elle remplace un O(n) négation du tableau avec un O(1) tranche. Si vous travaillez avec de petits tableaux à l'intérieur de boucles, vous pouvez obtenir des gains de performance en évitant cette négation, et si vous travaillez avec d'énormes tableaux, vous pouvez économiser de la mémoire car la négation crée une copie de l'ensemble du tableau.

Notez que ces méthodes ne donnent pas toujours des résultats équivalents : si une implémentation de tri stable est demandée à argsort par exemple en passant l'argument du mot-clé kind='mergesort' alors la première stratégie préservera la stabilité du tri, mais la seconde rompra la stabilité (c'est-à-dire que les positions des éléments égaux seront inversées).

Exemples d'horaires :

En utilisant un petit tableau de 100 flottants et une queue de longueur 30, la méthode de visualisation était environ 15% plus rapide.

>>> avgDists = np.random.rand(100)
>>> n = 30
>>> timeit (-avgDists).argsort()[:n]
1.93 µs ± 6.68 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
>>> timeit avgDists.argsort()[::-1][:n]
1.64 µs ± 3.39 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
>>> timeit avgDists.argsort()[-n:][::-1]
1.64 µs ± 3.66 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Pour les tableaux plus grands, l'argsort est dominant et il n'y a pas de différence de temps significative.

>>> avgDists = np.random.rand(1000)
>>> n = 300
>>> timeit (-avgDists).argsort()[:n]
21.9 µs ± 51.2 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
>>> timeit avgDists.argsort()[::-1][:n]
21.7 µs ± 33.3 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
>>> timeit avgDists.argsort()[-n:][::-1]
21.9 µs ± 37.1 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Veuillez noter que le commentaire de nedim ci-dessous est incorrecte. Le fait de tronquer avant ou après l'inversion ne fait aucune différence en termes d'efficacité, puisque ces deux opérations ne font que déplacer une vue du tableau de manière différente et ne copient pas réellement les données.

Answer 2

Tout comme Python, dans lequel [::-1] inverse le tableau retourné par argsort() y [:n] donne les n derniers éléments :

>>> avgDists=np.array([1, 8, 6, 9, 4])
>>> n=3
>>> ids = avgDists.argsort()[::-1][:n]
>>> ids
array([3, 1, 2])

L'avantage de cette méthode est que ids est un voir de avgDists :

>>> ids.flags
  C_CONTIGUOUS : False
  F_CONTIGUOUS : False
  OWNDATA : False
  WRITEABLE : True
  ALIGNED : True
  UPDATEIFCOPY : False

(Le fait que 'OWNDATA' soit faux indique qu'il s'agit d'une vue et non d'une copie).

Une autre façon de faire est quelque chose comme :

(-avgDists).argsort()[:n]

Le problème est que la façon dont cela fonctionne est de créer un négatif de chaque élément du tableau :

>>> (-avgDists)
array([-1, -8, -6, -9, -4])

Et crée une copie pour le faire :

>>> (-avgDists_n).flags['OWNDATA']
True

Donc si vous chronométrez chaque, avec ce très petit ensemble de données :

>>> import timeit
>>> timeit.timeit('(-avgDists).argsort()[:3]', setup="from __main__ import avgDists")
4.2879798610229045
>>> timeit.timeit('avgDists.argsort()[::-1][:3]', setup="from __main__ import avgDists")
2.8372560259886086

La méthode de visualisation est nettement plus rapide (et utilise la moitié de la mémoire...).

Answer 3

Au lieu d'utiliser np.argsort vous pourriez utiliser np.argpartition - si vous n'avez besoin que des indices des n éléments les plus bas/les plus hauts.

Cela ne nécessite pas de trier tout le tableau mais juste la partie dont vous avez besoin. Notez que "l'ordre à l'intérieur de votre partition" n'est pas défini, donc même si cela donne les indices corrects, ils peuvent ne pas être correctement ordonnés :

>>> avgDists = [1, 8, 6, 9, 4]
>>> np.array(avgDists).argpartition(2)[:2]  # indices of lowest 2 items
array([0, 4], dtype=int64)

>>> np.array(avgDists).argpartition(-2)[-2:]  # indices of highest 2 items
array([1, 3], dtype=int64)

Answer 4

Vous pouvez utiliser les commandes flip numpy.flipud() o numpy.fliplr() pour obtenir les index dans l'ordre décroissant après avoir trié en utilisant la fonction argsort commande. C'est ce que je fais habituellement.

Answer 5

Comme l'a suggéré @Kanmani, une mise en œuvre plus facile à interpréter pourrait utiliser les éléments suivants numpy.flip comme dans l'exemple suivant :

import numpy as np

avgDists = np.array([1, 8, 6, 9, 4])
ids = np.flip(np.argsort(avgDists))
print(ids)

En utilisant le modèle visiteur plutôt que les fonctions membres, il est plus facile de lire l'ordre des opérations.