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

Question

У меня много больших (> 35 000 000) списков целых чисел, которые будут содержать дубликаты.Мне нужно получить количество для каждого целого числа в списке.Следующий код работает, но кажется медленным.Может ли кто-нибудь еще улучшить тест с использованием Python и предпочтительно 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)

, который возвращает:

$ python bench.py 
111.377498865

Приветствия!

Редактировать на основеответы:

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

, что возвращает:

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

Хотя Кристоф в настоящее время дает неверные результаты

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

Answer 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 с, при радикальной сортировке оно падает до 1,7 с.

Просто переключаясь на сортировку по основанию, я получаю общее ускорение в 2,35 раза. В этом случае сортировка по основанию более чем в 4 раза быстрее, чем быстрая сортировка.* Как отсортировать массив целых чисел быстрее, чем быстрая сортировка? , который был мотивирован вашим вопросом.

Answer 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 с использованием кода Пола (но с той же формой массива значений) с исправлением, которое я предложил в комментарии, поиск уникальных значений и количества занимает 1,9 секунды (сортировка, конечно же, занимает столько же времени).

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

Answer 4

Полагаю, наиболее очевидный и до сих пор не упомянутый подход заключается в простом использовании collections.Counter.Вместо того, чтобы создавать огромное количество временно используемых списков с помощью groupby, он просто увеличивает целые числа.Это ускорение в 2 раза, но оно все же медленнее, чем у простых решений.

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 с для моей машины по сравнению с первоначальным решением.

Answer 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 на первый взгляд немного непрозрачен.

Answer 6

Это простое решение:

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)

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

Возможно, еще есть возможности для улучшения, я не часто использую numpy.

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

Answer 7

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

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

Answer 8

Замена len(list(g)) на sum(1 for i in g) увеличивает скорость в 2 раза

Answer 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 в настоящее время не поддерживает беззнаковые типы индексов ...

Answer 10

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

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

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

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