Unkomplizierte Gruppierung mit itertools.groups der Leistung

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.

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.

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.

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. 

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.

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

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.

In der neuesten Version von numpy haben wir dies.

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

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