J'ai un vecteur de quelques centaines de millions d'éléments qui sont NP.UINT8. Ils ne vont que de la valeur de 0 à 255.
J'ai besoin de trier cette liste et je pense que cela devrait être traité plus rapidement que Quicksort. Je pense que je pourrais trouver des indices pour toutes les valeurs "0" et les mettre à l'avant, puis pour toutes les valeurs "1" et les mettre après le dernier insert et progresser jusqu'à ce que je sache. Ce serait la progéniture mutante d'unique et trier avec une indexation et devrait fonctionner très rapidement.
Y a-t-il un intégré qui fait cela bien, correctement et quelque chose de rapide comme "C" sans que je doive l'accomplir? Pourriez-vous me signaler?
Disons que comme un "jouet" de mon problème réel que je voulais trier les valeurs d'intensité pour chaque couleur (RVB) d'une version de 100 mégapixels du Mandrill Image où chaque couleur avait été convertie en une seule, très longue, vecteur de valeurs UINT8. Si je devais faire la différence entre les méthodes de tri, qui seraient raisonnables de calculer, en python?
3 Réponses :
Vous trouverez peut-être que numpy.bincount est tout ce dont vous avez besoin. Il compte le nombre d'occurrences de chaque entier dans les données.
Par exemple, voici quelques entiers 8 bits non signés aléatoires: p> comptez les entiers utilisant binount Code>: p> In [105]: b[0], b[13]
Out[105]: (0, 3)
Vous pouvez le faire sans tri en utilisant binount et répéter:
In [11]: a = np.bincount(np.array([71, 9, 1, 2, 3, 4, 4, 4, 8, 9, 9, 71], dtype=np.uint8), minlength=256) In [12]: np.repeat(np.arange(256, dtype=np.uint8), a) Out[12]: array([ 1, 2, 3, 4, 4, 4, 8, 9, 9, 9, 71, 71], dtype=uint8)
Si vous n'avez besoin que des valeurs de tri , alors bincount est en effet la voie à suivre. Si, toutefois, ce dont vous avez besoin est davantage d'Argsort, par exemple, vous devez co-trier un autre tableau de même longueur, vous pouvez utiliser Ce Q & A compare diverses méthodes dont certaines sont beaucoup plus rapides que le" code "naïf ' argsort .
Vous êtes correct, si vous n'avez qu'un petit nombre de valeurs (par exemple 256), vous pouvez simplement utiliser le «Seau de godet» que vous avez décrit (où le nombre de bacs est le nombre de valeurs). Il fonctionnera dans
O (n) heure (avec des implications supplémentaires sur l'espace)Ne réinventez pas la roue. La plupart des langues implémentent maintenant une tresse de fusion qui est plus rapide que tout ce que vous pouvez accomplir. Ce que vous décrivez ici, c'est Radix Trier, ce qui augmente simplement l'indice au moment où il frappe un nombre spécifique. Ensuite, vous pouvez recréer un tableau commandé.
Si vous effectuez une recherche sur la phrase «Tutoriel de tri Python», vous trouverez des ressources qui peuvent l'expliquer beaucoup mieux que possible dans une réponse ici.
Est-ce un tableau ou une liste? Si tableau, est-ce 1D?
Qu'allez-vous faire avec la liste de tri? Il pourrait y avoir quelque chose de plus simple qu'une copie triée des données, en fonction de ce que vous allez faire avec le résultat. Par exemple. Jetez un coup d'œil à
numpy.bincount .@Prune - j'ai regardé un peu un peu avant de venir ici. Il semble initialement, comme NUMPY n'a pas de type RadixSort ou Seau mentionné dans les commentaires ci-dessus. NUMPY a "rapide", "fusion" et "tas".
@Warrenweckesser - Merci beaucoup pour ce pointeur. Je peux concevoir mon problème dans le domaine de la CDF et avoir une liste de 256 au lieu de 128 millions d'éléments. Très très gentil. C'est un accessoire littéral 1M! C'est pourquoi je demande des choses comme ça ici. Aucun tri standard dans le monde ne donnerait à quoi je viens de recevoir en 5 minutes de demander à quelqu'un avec beaucoup plus d'indice que moi.
Ah; On dirait que vous essayez de "bin" ces choses, plutôt que d'un porc entier trier . Oui, le pointeur de Warrenweckesser est probablement ce dont vous avez besoin.
@Warrenweckesser voudriez-vous poster cela comme une réponse? Pense que ça vaut le coup.
@Divakar: fait.