Nhóm kết quả bằng cách sử dụng itertools.groupby hiệu suất

Question

Tôi có nhiều danh sách số nguyên lớn (> 35.000.000) sẽ chứa các bản sao. Tôi cần lấy số đếm cho mỗi số nguyên trong một danh sách. Mã sau hoạt động, nhưng có vẻ chậm. Bất cứ ai có thể tốt hơn các điểm chuẩn bằng cách sử dụng Python và tốt nhất là 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) 

trả về:

$ python bench.py 
111.377498865 

Cheers!

Sửa dựa trên phản ứng:

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

trả về:

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

Mặc dù Christophe cho kết quả không chính xác hiện

Answer 1

tôi nhận được một sự cải thiện 3x làm một cái gì đó như thế này:

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

Sắp xếp là theta (NlogN), tôi muốn đi cho phân bổ O (N) được cung cấp bởi triển khai Hashtable của Python. Chỉ cần sử dụng defaultdict(int) để giữ tội danh các số nguyên và chỉ lặp qua mảng một lần:

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

Đây là lý thuyết nhanh hơn, tiếc là tôi không có cách nào để kiểm tra ngay bây giờ. Phân bổ bộ nhớ bổ sung có thể làm cho nó thực sự chậm hơn so với giải pháp của bạn, đó là tại chỗ.

Chỉnh sửa: Nếu bạn cần lưu bộ nhớ, hãy thử sắp xếp radix, nhanh hơn nhiều so với số nguyên so với quicksort (mà tôi tin là sử dụng gọn gàng).

Answer 3

Đây là một giải pháp 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) 

Chạy trong khoảng giây trên máy tính của tôi so với khoảng cho giải pháp ban đầu của bạn (mà là một cải tiến tốt đẹp).

Có thể vẫn còn chỗ để cải thiện, tôi không sử dụng thường xuyên.

Chỉnh sửa: đã thêm một số nhận xét bằng mã.

Answer 4

Thay len(list(g)) với sum(1 for i in g) đưa ra một 2x tăng tốc

Answer 5

Bằng cách yêu cầu, đây là một phiên bản Cython về điều này. Tôi đã làm hai đi qua mảng. Cái đầu tiên tìm ra có bao nhiêu phần tử duy nhất có để có thể mảng của tôi cho các giá trị duy nhất và số lượng của kích thước thích hợp.

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 

Việc phân loại thực sự dành nhiều thời gian nhất ở đây cho đến nay. Sử dụng mảng giá trị được đưa ra trong mã của tôi, việc sắp xếp mất 4,75 giây và tìm kiếm thực tế của các giá trị duy nhất và số lượng mất 0,67 giây. Với mã Numpy thuần túy sử dụng mã của Paul (nhưng với cùng một dạng của mảng giá trị) với sửa chữa mà tôi đã đề xuất trong một nhận xét, việc tìm kiếm các giá trị và số lượng duy nhất mất 1.9 giây (sắp xếp vẫn mất cùng một lượng thời gian của khóa học).

Điều này có ý nghĩa đối với phần lớn thời gian được phân loại bởi vì nó là O (N log N) và đếm là O (N). Bạn có thể tăng tốc độ sắp xếp một chút so với Numpy (sử dụng qsort của C nếu tôi nhớ chính xác), nhưng bạn phải thực sự biết những gì bạn đang làm và nó có lẽ không phải là đáng giá. Ngoài ra, có thể có một số cách để tăng tốc mã Cython của tôi nhiều hơn một chút, nhưng nó có lẽ không đáng giá.

Answer 6

Đây là một chủ đề khá cũ, nhưng tôi nghĩ rằng tôi muốn đề cập đến rằng có một sự cải thiện nhỏ để có thể thực hiện trên các giải pháp hiện nay được chấp nhận:

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) 

này được thử nghiệm như khoảng nửa giây nhanh hơn trên máy của tôi; không phải là một cải tiến lớn, nhưng đáng giá. Ngoài ra, tôi nghĩ rằng nó rõ ràng hơn những gì đang xảy ra ở đây; hai bước diff cách tiếp cận là một chút mờ đục ở cái nhìn đầu tiên.

Answer 7

Tôi đoán cách tiếp cận rõ ràng nhất và vẫn chưa được đề cập là, chỉ cần sử dụng collections.Counter. Thay vì xây dựng một số lượng lớn các danh sách tạm thời được sử dụng với groupby, nó chỉ tăng số nguyên. Đó là một oneliner và tăng tốc gấp 2 lần, nhưng vẫn chậm hơn so với các giải pháp vất vả tinh khiết.

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) 

Tôi tăng tốc từ 136 s lên 62 s cho máy của mình, so với giải pháp ban đầu.

Answer 8

Bạn có thể thử như sau (ab) sử dụng 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 

Đây là chậm hơn so với câu trả lời chiến thắng, có lẽ vì scipy hiện không hỗ trợ unsigned như chỉ số loại ...

Answer 9

Đã hơn 5 năm trôi qua kể từ khi câu trả lời của Paul được chấp nhận. Điều thú vị là, sort() vẫn là nút cổ chai trong giải pháp được chấp nhận.

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) 

Giải pháp được chấp nhận chạy trong 4.0 giây trên máy tính của tôi, với radix sắp xếp nó giảm xuống 1,7 s.

Chỉ bằng cách chuyển sang sắp xếp kết hợp, tôi nhận được tốc độ tổng thể là 2,35x. Loại radix nhanh hơn gấp 4 lần so với quicksort trong trường hợp này.

Xem How to sort an array of integers faster than quicksort? được thúc đẩy bởi câu hỏi của bạn.

Answer 10

Trong phiên bản mới nhất của numpy, chúng tôi có điều này.

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