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.

InformationsquelleAutor Donny | 2011-01-10