Raggruppamento di Numpy che utilizza itertools.pagamento di gruppo

Question

Ho molti elenchi di numeri interi grandi (> 35.000.000) che conterranno duplicati. Devo ottenere un conteggio per ogni intero in una lista. Il seguente codice funziona, ma sembra lento. Qualcun altro può migliorare il benchmark usando Python e preferibilmente 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) 

che ritorna:

$ python bench.py 
111.377498865 

Cheers!

Modifica in base alle risposte:

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

che restituisce:

$ python bench.py 
Original: 113.385262966 secs 
Gnibbler: 71.7464978695 secs 
Christophe: 27.1690568924 secs 
Paul: 9.06268405914 secs 

Sebbene Christophe dà risultati errati attualmente

Answer 1

ho un 3x miglioramento fare qualcosa di simile:

def group(): 
    import numpy as np 
    values = np.array(np.random.randint(0,3298,size=35000000),dtype='u4') 
    values.sort() 
    dif = np.ones(values.shape,values.dtype) 
    dif[1:] = np.diff(values) 
    idx = np.where(dif>0) 
    vals = values[idx] 
    count = np.diff(idx) 

Answer 2

ordinamento è theta (N log N), mi piacerebbe andare per O (N) ammortizzato fornito dall'implementazione di hashtable di Python. Basta usare defaultdict(int) per tenere i conteggi degli interi ed appena iterare l'array una volta:

counts = collections.defaultdict(int) 
for v in values: 
    counts[v] += 1 

Questo è teoricamente più veloce, purtroppo non ho modo di controllare la società. L'allocazione della memoria aggiuntiva potrebbe renderla effettivamente più lenta della soluzione, che è sul posto.

Modifica: Se è necessario salvare la memoria, prova l'ordinamento digitale, che è molto più veloce su numeri interi di quicksort (che credo sia quello che usa numpy).

Answer 3

Questa è una soluzione NumPy:

def group(): 
    import numpy as np 
    values = np.array(np.random.randint(0,1<<32,size=35000000),dtype='u4') 

    # we sort in place 
    values.sort() 

    # when sorted the number of occurences for a unique element is the index of 
    # the first occurence when searching from the right - the index of the first 
    # occurence when searching from the left. 
    # 
    # np.dstack() is the numpy equivalent to Python's zip() 

    l = np.dstack((values, values.searchsorted(values, side='right') - \ 
        values.searchsorted(values, side='left'))) 

    index = np.fromiter(l, dtype='u4,u2') 

if __name__=='__main__': 
    from timeit import Timer 
    t = Timer("group()","from __main__ import group") 
    print t.timeit(number=1) 

Viene eseguito in circa 25 secondi sulla mia macchina, rispetto a circa il 96 per la soluzione iniziale (che è un bel miglioramento).

Potrebbero esserci ancora margini di miglioramento, non uso spesso numpy.

Modifica: aggiunti alcuni commenti nel codice.

Answer 4

Sostituzione len(list(g)) con sum(1 for i in g) dà un aumento di velocità 2x

Answer 5

Su richiesta, qui è una versione Cython di questo. Ho fatto due passaggi attraverso l'array. Il primo rileva quanti elementi unici ci sono in modo che possano i miei array per i valori e i conteggi unici delle dimensioni appropriate.

import numpy as np 
cimport numpy as np 
cimport cython 

@cython.boundscheck(False) 
def dogroup(): 
    cdef unsigned long tot = 1 
    cdef np.ndarray[np.uint32_t, ndim=1] values = np.array(np.random.randint(35000000,size=35000000),dtype=np.uint32) 
    cdef unsigned long i, ind, lastval 
    values.sort() 
    for i in xrange(1,len(values)): 
     if values[i] != values[i-1]: 
      tot += 1 
    cdef np.ndarray[np.uint32_t, ndim=1] vals = np.empty(tot,dtype=np.uint32) 
    cdef np.ndarray[np.uint32_t, ndim=1] count = np.empty(tot,dtype=np.uint32) 
    vals[0] = values[0] 
    ind = 1 
    lastval = 0 
    for i in xrange(1,len(values)): 
     if values[i] != values[i-1]: 
      vals[ind] = values[i] 
      count[ind-1] = i - lastval 
      lastval = i 
      ind += 1 
    count[ind-1] = len(values) - lastval 

L'ordinamento in realtà richiede più tempo qui di gran lunga. Utilizzando l'array di valori fornito nel mio codice, l'ordinamento richiede 4.75 secondi e il rilevamento effettivo dei valori e dei conteggi univoci richiede .67 secondi. Con il puro codice Numpy che usa il codice di Paul (ma con la stessa forma dell'array dei valori) con la correzione che ho suggerito in un commento, trovo i valori e i conteggi univoci 1.9 secondi (l'ordinamento richiede comunque lo stesso tempo).

Per la maggior parte del tempo è logico utilizzare l'ordinamento perché è O (N log N) e il conteggio è O (N). È possibile velocizzare l'ordinamento un po 'su Numpy (che usa il qsort di C se ricordo bene), ma devi sapere davvero cosa stai facendo e probabilmente non ne vale la pena. Inoltre, potrebbe esserci un modo per velocizzare il mio codice Cython un po 'di più, ma probabilmente non ne vale la pena.

Answer 6

Questa è una discussione piuttosto vecchio, ma ho pensato di ricordare che c'è un piccolo miglioramento da apportare alla soluzione attualmente accettata:

def group_by_edge(): 
    import numpy as np 
    values = np.array(np.random.randint(0,1<<32,size=35000000),dtype='u4') 
    values.sort() 
    edges = (values[1:] != values[:-1]).nonzero()[0] - 1 
    idx = np.concatenate(([0], edges, [len(values)])) 
    index = np.empty(len(idx) - 1, dtype= 'u4, u2') 
    index['f0'] = values[idx[:-1]] 
    index['f1'] = np.diff(idx) 

Questa testata come circa mezzo secondo più veloce su la mia macchina; non un enorme miglioramento, ma vale la pena qualcosa. Inoltre, penso che sia più chiaro cosa sta succedendo qui; l'approccio a due step diff è un po 'opaco a prima vista.

Answer 7

Immagino che l'approccio più ovvio e non ancora menzionato sia quello di utilizzare semplicemente collections.Counter. Invece di creare una grande quantità di elenchi usati temporaneamente con groupby, fa semplicemente conti interi. È un oneliner e una velocità di 2 volte, ma è ancora più lento delle soluzioni di puro numpy.

def group(): 
    import sys 
    import numpy as np 
    from collections import Counter 
    values = np.array(np.random.randint(0,sys.maxint,size=35000000),dtype='u4') 
    c = Counter(values) 

if __name__=='__main__': 
    from timeit import Timer 
    t = Timer("group()","from __main__ import group") 
    print t.timeit(number=1) 

ho ottenere un aumento di velocità da 136 a 62 s s per la mia macchina, rispetto alla soluzione iniziale.

Answer 8

Si potrebbe provare la seguente (ab) uso di scipy.sparse:

from scipy import sparse 
def sparse_bincount(values): 
    M = sparse.csr_matrix((np.ones(len(values)), values.astype(int), [0, len(values)])) 
    M.sum_duplicates() 
    index = np.empty(len(M.indices),dtype='u4,u2') 
    index['f0'] = M.indices 
    index['f1']= M.data 
    return index 

Questo è più lenta la risposta vincente, forse perché scipy attualmente non supporta senza segno come indici tipi ...

Answer 9

Sono passati più di 5 anni da quando la risposta di Paolo fu accettata. È interessante notare che il sort() è ancora il collo di bottiglia nella soluzione accettata.

Line #  Hits   Time Per Hit % Time Line Contents 
============================================================== 
    3           @profile 
    4           def group_paul(): 
    5   1  99040 99040.0  2.4  import numpy as np 
    6   1  305651 305651.0  7.4  values = np.array(np.random.randint(0, 2**32,size=35000000),dtype='u4') 
    7   1  2928204 2928204.0 71.3  values.sort() 
    8   1  78268 78268.0  1.9  diff = np.concatenate(([1],np.diff(values))) 
    9   1  215774 215774.0  5.3  idx = np.concatenate((np.where(diff)[0],[len(values)])) 
    10   1   95  95.0  0.0  index = np.empty(len(idx)-1,dtype='u4,u2') 
    11   1  386673 386673.0  9.4  index['f0'] = values[idx[:-1]] 
    12   1  91492 91492.0  2.2  index['f1'] = np.diff(idx) 

La soluzione accettata corre per 4,0 s sulla mia macchina, con radix sort che scende a 1,7 s.

Semplicemente passando a radix sort, ottengo un aumento complessivo di 2,35x. L'ordinamento digitale è più di 4x più veloce di Quicksort in questo caso.

Vedere How to sort an array of integers faster than quicksort? motivato dalla domanda.

Answer 10

Nell'ultima versione di numpy, abbiamo questo.

import numpy as np 
frequency = np.unique(values, return_counts=True)