webentwicklung-frage-antwort-db.com.de

Unkomplizierte Gruppierung mit itertools.groups der Leistung

Ich habe viele große (> 35.000.000) Listen von ganzen Zahlen, die Duplikate enthalten werden. Ich muss für jede ganze Zahl in einer Liste eine Zählung erhalten. Der folgende Code funktioniert, scheint jedoch langsam zu sein. Kann jemand anderes besser den Benchmark mit Python und vorzugsweise Numpy verwenden?

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)

was gibt zurück:

$ python bench.py 
111.377498865

Prost!

Bearbeiten basierend auf Antworten:

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

was gibt zurück:

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

Obwohl Christophe derzeit falsche Ergebnisse liefert

26
Donny

ich bekomme eine dreifache Verbesserung, wenn ich so etwas mache:

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

Mehr als 5 Jahre sind vergangen, seit die Antwort von Paulus angenommen wurde. Interessanterweise ist Die sort() immer noch der Engpass in der akzeptierten Lösung. 

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)

Die akzeptierte Lösung läuft auf meiner Maschine für 4,0 s, während radix sort Auf 1,7 s sinkt. 

Durch das Umschalten auf "radix sort" bekomme ich insgesamt eine Beschleunigung von 2,35x. Die Radix-Sortierung ist in diesem Fall mehr als 4x schneller als Quicksort.

Siehe Wie sortiere ich ein Array von Ganzzahlen schneller als Quicksort? , Das durch Ihre Frage motiviert wurde.

10
Ali

Auf Wunsch ist hier eine Cython-Version davon. Ich habe zwei Durchgänge durch das Array gemacht. Der erste findet heraus, wie viele eindeutige Elemente es gibt, damit meine Arrays nach den eindeutigen Werten und Zählungen der entsprechenden Größe können.

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

Die Sortierung dauert hier bei weitem die meiste Zeit. Bei Verwendung des Werte-Arrays, das in meinem Code angegeben ist, dauert die Sortierung 4,75 Sekunden und das tatsächliche Finden der eindeutigen Werte und Zählzeiten dauert 0,67 Sekunden. Mit dem reinen Numpy-Code, der Pauls Code verwendet (aber mit der gleichen Form des Werte-Arrays) und dem in einem Kommentar vorgeschlagenen Fix, dauert das Finden der eindeutigen Werte und Zählungen 1,9 Sekunden (die Sortierung dauert natürlich immer noch dieselbe Zeit). 

Es ist sinnvoll, die meiste Zeit von der Sortierung in Anspruch zu nehmen, da es O (N log N) ist und die Zählung O (N) ist. Sie können die Sortierung etwas über Numpy's beschleunigen (was, wenn ich mich recht erinnere, Cs qsort verwendet), aber Sie müssen wirklich wissen, was Sie tun, und es lohnt sich wahrscheinlich nicht. Es gibt auch eine Möglichkeit, meinen Cython-Code etwas zu beschleunigen, aber es lohnt sich wahrscheinlich nicht.

4
Justin Peel

Ich denke, der naheliegendste und noch nicht erwähnte Ansatz ist, einfach collections.Counter zu verwenden. Anstatt eine große Anzahl von temporär verwendeten Listen mit Groupby zu erstellen, werden nur ganze Zahlen heraufgesetzt. Es ist ein Oneliner und eine zweifache Beschleunigung, aber immer noch langsamer als die reinen Numpy-Lösungen.

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)

Im Vergleich zu der ursprünglichen Lösung bekomme ich für meine Maschine eine Beschleunigung von 136 s auf 62 s.

2
Michael

Dies ist ein ziemlich alter Thread, aber ich dachte, ich würde erwähnen, dass an der derzeit akzeptierten Lösung eine kleine Verbesserung vorgenommen werden muss:

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)

Dies testete auf meiner Maschine etwa eine halbe Sekunde schneller; keine große Verbesserung, aber etwas wert. Außerdem denke ich, dass es klarer ist, was hier passiert. der zweistufige diff-Ansatz ist auf den ersten Blick ein wenig undurchsichtig. 

2
senderle

Dies ist eine numpy Lösung:

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)

Läuft in ungefähr 25 Sekunden auf meiner Maschine im Vergleich zu ungefähr 96 für Ihre ursprüngliche Lösung (was eine gute Verbesserung ist).

Möglicherweise gibt es noch Verbesserungsmöglichkeiten, ich benutze das nicht so oft.

Edit : fügte einige Kommentare im Code hinzu.

2
ChristopheD

Das Ersetzen von len(list(g)) durch sum(1 for i in g) führt zu einer zweifachen Beschleunigung

1
John La Rooy

Sie könnten die folgende (ab) Verwendung von scipy.sparse versuchen:

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

Dies ist langsamer als die gewinnende Antwort, möglicherweise weil scipy derzeit keine unsignierten Indizes unterstützt.

0
joeln

In der neuesten Version von numpy haben wir dies.

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

Sortieren ist Theta (NlogN), ich würde für amortisiertes O(N) gehen, das von der Python-Hashtable-Implementierung bereitgestellt wird. Verwenden Sie einfach defaultdict(int), um die Anzahl der ganzen Zahlen zu behalten, und wiederholen Sie das Array einmalig:

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

Dies ist theoretisch schneller, leider habe ich jetzt keine Möglichkeit, das zu überprüfen. Durch die Zuweisung des zusätzlichen Arbeitsspeichers wird der Speicher möglicherweise langsamer als die vorhandene Lösung.

Edit: Wenn Sie Speicherplatz benötigen, probieren Sie radix sort. Dies ist bei Integer-Werten viel schneller als bei quicksort (was meines Erachtens von numpy verwendet wird).

0
Rafał Dowgird