Numpy regroupement à l'aide de itertools.groupby performance
J'ai beaucoup de gros (>des 35.000.000) des listes d'entiers qui contient des doublons. J'ai besoin d'obtenir un décompte pour chaque entier dans une liste. Le code suivant fonctionne, mais semble lent. Peut quelqu'un d'autre de mieux à l'indice de référence à l'aide de Python et de préférence Numpy?
def group():
import numpy as np
from itertools import groupby
values = np.array(np.random.randint(0,1<<32,size=35000000),dtype='u4')
values.sort()
groups = ((k,len(list(g))) for k,g in groupby(values))
index = np.fromiter(groups,dtype='u4,u2')
if __name__=='__main__':
from timeit import Timer
t = Timer("group()","from __main__ import group")
print t.timeit(number=1)
qui retourne:
$ python bench.py
111.377498865
Cheers!
Modifier sur la base des réponses:
def group_original():
import numpy as np
from itertools import groupby
values = np.array(np.random.randint(0,1<<32,size=35000000),dtype='u4')
values.sort()
groups = ((k,len(list(g))) for k,g in groupby(values))
index = np.fromiter(groups,dtype='u4,u2')
def group_gnibbler():
import numpy as np
from itertools import groupby
values = np.array(np.random.randint(0,1<<32,size=35000000),dtype='u4')
values.sort()
groups = ((k,sum(1 for i in g)) for k,g in groupby(values))
index = np.fromiter(groups,dtype='u4,u2')
def group_christophe():
import numpy as np
values = np.array(np.random.randint(0,1<<32,size=35000000),dtype='u4')
values.sort()
counts=values.searchsorted(values, side='right') - values.searchsorted(values, side='left')
index = np.zeros(len(values),dtype='u4,u2')
index['f0']=values
index['f1']=counts
#Erroneous result!
def group_paul():
import numpy as np
values = np.array(np.random.randint(0,1<<32,size=35000000),dtype='u4')
values.sort()
diff = np.concatenate(([1],np.diff(values)))
idx = np.concatenate((np.where(diff)[0],[len(values)]))
index = np.empty(len(idx)-1,dtype='u4,u2')
index['f0']=values[idx[:-1]]
index['f1']=np.diff(idx)
if __name__=='__main__':
from timeit import Timer
timings=[
("group_original","Original"),
("group_gnibbler","Gnibbler"),
("group_christophe","Christophe"),
("group_paul","Paul"),
]
for method,title in timings:
t = Timer("%s()"%method,"from __main__ import %s"%method)
print "%s: %s secs"%(title,t.timeit(number=1))
qui retourne:
$ python bench.py
Original: 113.385262966 secs
Gnibbler: 71.7464978695 secs
Christophe: 27.1690568924 secs
Paul: 9.06268405914 secs
Bien que Christophe donne des résultats incorrects actuellement
- Des restrictions s'appliquent à l'ensemble des entiers? Peuvent tous les 2^32 possible entiers se produire?
- Avez-vous besoin de la sortie de
group()
triés par clé? - Bonjour Sven, il y a une chance égale de chaque 2^32 entier se produise, et la sortie groupée (index) ne doivent être en ordre croissant. Les valeurs.sort() n'est pas vraiment le goulot d'étranglement, c'est la dernière ligne de groupe() qui est de la lenteur de la peu! Cheers!
- Si vous voulez juste pour obtenir le nombre d'occurrences des nombres entiers, np.bincount est de le faire. np.bincount retourne le nombre de tous les nombres entiers de gamme(max(valeur)), même pour zéro, ce qui pourrait ne pas être ce que vous voulez, mais c'est rapide.
- Salut user333700. Je pense que la fourchette de valeur comprise entre 0 et 2^32 signifie que bincount permettrait d'utiliser plus de mémoire que la plupart des ordinateurs possèdent!
- Pourquoi aurais-je obtenir "OverflowError: Python int trop grand pour convertir C long" lorsque j'exécute le code ci-dessus? Je suis à l'aide de Python à partir de l'Anaconda.
Vous devez vous connecter pour publier un commentaire.
- je obtenir un 3x amélioration de faire quelque chose comme ceci:
count
est absent de la valeur finale. comptage doit être:np.diff(inx.tolist+[len(values)])
ou quelque chose de moins laid.idx = np.concatenate((np.where(dif)[0],[len(values)]))
etvals = values[idx[:-1]]
en place de la 3ème et la 2ème à la dernière ligne, respectivement. C'est vraiment la meilleure réponse à l'aide seulement de numpy. Si vous voulais plus rapide, je recommande l'utilisation de Cython. Il serait assez facile à faire et donner une jolie amélioration significative de la vitesse et de la mémoire au cours de cette numpy code.Plus de 5 ans ont passé depuis que Paul réponse a été acceptée. Il est intéressant de noter,
le
sort()
est toujours le goulot d'étranglement dans la solution retenue.La solution retenue s'exécute pour la version 4.0 s sur ma machine, avec le tri radix
descend à 1.7 s.
Simplement en changeant de tri radix, je reçois un ensemble de 2,35 x speedup. Le radix, le tri est plus de 4 fois plus rapide que quicksort dans ce cas.
Voir Comment trier un tableau d'entiers plus rapidement que quicksort?, qui était motivée par votre question.
@profile
décorateur? L'air très joli.À la demande, voici un Cython version de ce. J'ai fait deux passes dans le tableau. Le premier découvre comment de nombreux éléments uniques, il y a tellement que mes tableaux pour les valeurs uniques et des comtes de la taille appropriée.
Le tri est fait en prenant le plus de temps ici, et de loin. En utilisant les valeurs de la matrice de données dans mon code, le tri est la prise de 4,75 secondes et les découvertes réelles des valeurs uniques et compte prend .67 secondes. Avec la pure Numpy code à l'aide de Paul du code (mais avec la même forme de valeurs array) avec la correction je l'ai suggéré dans un commentaire, trouver les valeurs uniques et compte prend 1.9 secondes (tri prend toujours la même quantité de temps de parcours).
Il fait sens pour la plupart du temps à être pris en compte par le tri, car il est O(N log N) et le comptage est O(N). Vous pouvez accélérer le tri un peu plus de Numpy (qui utilise C est qsort si je me souviens bien), mais vous devez vraiment savoir ce que vous faites et il n'est probablement pas la peine. Aussi, il pourrait y avoir une façon d'accélérer mon Cython code un peu plus, mais il n'est probablement pas la peine.
C'est un numpy solution:
S'étend en 25 secondes sur ma machine, comparativement à environ 96 pour votre solution initiale (qui est une belle amélioration).
Il pourrait y avoir encore de la place pour de l'amélioration, je n'ai pas utiliser numpy que souvent.
Modifier: ajout de quelques commentaires dans le code.
values
est égale à [2,2,3] ensuite, vous obtiendrezarray([[[2,2],[2,2],[3,1]]])
pourl
etarray([(2L, 2)], dtype=[('f0','<u4'),('f1','<u2')])
pourindex
. Vous souhaitez trouver les valeurs uniques d'abord en utilisant quelque chose comme np.unique et puis faire de la recherche binaire trucs en n'utilisant que les valeurs uniques.[1,1,1,2,2,1]
vous aurez[(1, 4), (1, 4), (1, 4), (2, 2), (2, 2), (1, 4)]
qui représente la bonne fréquence de comptage, mais a besoin de doublons supprimés.uv = np.unique(values)
puisl = np.dstack((uv, values.searchsorted(uv, side='right') - values.searchsorted(uv, side='left')))
C'est un assez vieux thread, mais j'ai pensé que je le mentionne qu'il y a une petite amélioration à apporter sur le actuellement acceptées solution:
Cette épreuve comme une demi-seconde plus vite sur ma machine; pas une énorme amélioration, mais la valeur de quelque chose. En outre, je pense que c'est plus clair ce qui se passe ici; les deux étape
diff
approche est un peu opaque au premier coup d'œil.Je pense que le plus évident et pas encore mentionné approche est d'utiliser simplement
collections.Counter
. Au lieu de construire une énorme quantité de temporairement listes avec groupby, c'est juste upcounts entiers. C'est un oneliner et 2 fois plus rapide, mais encore plus lente que la pure numpy solutions.- Je obtenir une accélération à partir de 136 s 62 s pour ma machine, par rapport à la solution initiale.
Remplacement
len(list(g))
avecsum(1 for i in g)
donne un 2x speedupDans la dernière version de numpy, nous avons cette.
Tri est theta(NlogN), j'irais pour amorti O(N) fournis par Python de la table de hachage de la mise en œuvre. Utilisez simplement
defaultdict(int)
pour tenir compte des entiers et viens de parcourir le tableau une fois:C'est théoriquement plus rapide, malheureusement je n'ai aucun moyen de vérifier maintenant. L'allocation de la mémoire supplémentaire pourrait rendre effectivement plus lent que votre solution, qui est en place.
Edit: Si vous avez besoin pour économiser de la mémoire essayer radix, ce qui est beaucoup plus rapide sur des entiers que quicksort (qui je crois est ce que numpy utilise).
Vous pouvez essayer la (ab)utilisation de
scipy.sparse
:C'est plus lent que la réponse gagnante, peut-être parce que
scipy
actuellement ne prend pas en charge unsigned que les indices des types...