Группировка с использованием itertools.groupby

Ответ 1

Я получаю 3-кратное улучшение, делая что-то вроде этого:

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)

Ответ 2

Прошло более 5 лет с тех пор, как был принят ответ Павла. Интересно, sort() все еще является узким местом в принятом решении.

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)

Принятое решение работает на 4.0 с на моем компьютере, с его сортировкой по методу radix падает до 1,7 с.

Просто переключившись на сортировку radix, я получаю ускорение в 2,35 раза.. В этом случае сортировка radix более чем в 4 раза быстрее, чем quicksort.

Смотрите Как отсортировать массив целых чисел быстрее, чем quicksort?, который был мотивирован вашим вопросом.

Ответ 3

По просьбе здесь представлена ​​версия Cython. Я сделал два прохода через массив. Первый узнает, сколько уникальных элементов есть, чтобы мои массивы имели уникальные значения и подсчеты соответствующего размера.

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

Сортировка на самом деле занимает больше времени здесь. Используя массив значений, указанный в моем коде, сортировка занимает 4,75 секунды, и фактическое обнаружение уникальных значений и отсчетов занимает 0,67 секунды. С чистым кодом Numpy с использованием кода Paul (но с той же формой массива значений) с исправлением, которое я предложил в комментарии, поиск уникальных значений и отсчетов занимает 1,9 секунды (сортировка по-прежнему занимает такое же количество времени, конечно).

В большинстве случаев имеет смысл использовать сортировку, потому что это O (N log N), а подсчет - O (N). Вы можете немного ускорить сортировку по Numpy (который использует C qsort, если я правильно помню), но вы должны действительно знать, что делаете, и это, вероятно, не стоит. Кроме того, может быть некоторый способ ускорить мой Cython код немного больше, но это, вероятно, не стоит.

Ответ 4

Это многоуровневое решение:

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

Выполняется около 25 секунд на моей машине по сравнению с 96 для вашего первоначального решения (что является хорошим улучшением).

Там может быть место для улучшения, я часто не использую numpy.

Изменить: добавлены комментарии в код.

Ответ 5

Это довольно старый поток, но я подумал, что хочу упомянуть, что в текущем решении есть небольшое улучшение:

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)

Это было протестировано примерно на полсекунды быстрее на моей машине; не огромное улучшение, но что-то стоит. Кроме того, я думаю, что яснее, что происходит здесь; двухступенчатый подход diff на первый взгляд немного непрозрачен.

Ответ 6

Я думаю, что самый очевидный и до сих пор не упомянутый подход - просто использовать collections.Counter. Вместо того, чтобы создавать огромное количество временно используемых списков с groupby, он просто увеличивает число целых чисел. Это oneliner и 2-кратное ускорение, но все еще медленнее, чем чистые решения 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)

Я получаю ускорение от 136 с до 62 с для моей машины по сравнению с исходным решением.

Ответ 7

Замена len(list(g)) на sum(1 for i in g) дает 2x ускорение

Ответ 8

Сортировка - это theta (NlogN), я бы пошел на амортизацию O (N), предоставляемую реализацией хэш-таблицы Python. Просто используйте defaultdict(int) для хранения отсчетов целых чисел и просто итерации по массиву один раз:

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

Это теоретически быстрее, к сожалению, я не могу проверить сейчас. Выделение дополнительной памяти может сделать ее на самом деле медленнее, чем ваше решение, которое на месте.

Изменить: если вам нужно сохранить память, попробуйте сортировку radix, которая намного быстрее целых чисел, чем quicksort (что, по моему мнению, используется для использования numpy).

Ответ 9

Вы можете попробовать следующее (ab) использование 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

Это медленнее, чем выигрышный ответ, возможно потому, что scipy в настоящее время не поддерживает unsigned как типы индексов...

Ответ 10

В последней версии numpy у нас есть это.

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