Loại bỏ cho-loop bằng Python và NumPy xây dựng

Question

Tôi đang tìm một phương pháp trong Python và/hoặc NumPy vector hóa để loại bỏ việc sử dụng một cho vòng lặp sau:

for i in list_range_values: 
    v[list_list_values[i]] += list_comp_values[i] 

nơi:

• list_range_values ​​là danh sách các giá trị số nguyên Python ví dụ: [1, 3, 5], được vẽ từ phạm vi (0, R-1, 1)

• list_comp_values ​​là danh sách Python các giá trị số ví dụ. [0,7, 9,8, 1,2, 5, 10, 11,7, 6, 0,2] sao cho len (list_comp_values) = R

• v là vectơ có chiều dài V có độ dài sao cho R có thể là <, =,> so với V

• list_list_values ​​là danh sách các danh sách Python (mỗi danh sách chứa một số giá trị số nguyên khác nhau ví dụ [[3, 6, 7], [5, 7, 11, 25, 99], [8, 45] , [4, 7, 8], [0, 1], [21, 31, 41], [9, 11, 22, 33, 44], [17, 19]]) được vẽ từ phạm vi (0, V -1, 1) và với len (list_list_values) = R

Ví dụ:

for i in list_range_values (= [1, 3, 5]): 
    i=1: v[[5, 7, 11, 25, 99]] += list_comp_values[1] (= 9.8) 
    i=3: v[[4, 7, 8]] += list_comp_values[3] (= 5) 
    i=5: v[[21, 31, 41]] += list_comp_values[5] (= 11.7) 

Có phương pháp nào cho phép loại bỏ vòng lặp không?

Cython, Scipy/Weave/Blitz và mô-đun C là các giải pháp thay thế nhưng muốn đảm bảo nếu có câu trả lời vectơ Numpy trước.

Answer 1

Trong khi nó thường dẫn đến một tốc độ lớn để loại bỏ các vòng lặp và tận dụng lợi thế của việc xây dựng/in vectơ. Tôi sẽ chỉ ra rằng nó không phải luôn luôn như vậy. Thời gian đơn giản cho vòng lặp vs vectorization tham gia nhiều hơn, không cung cấp cho bạn một tốc độ lớn và có nhiều chi tiết hơn. Chỉ cần một cái gì đó để xem xét:

from timeit import Timer 

setstr="""import numpy as np 
import itertools 
import random 

Nlists = 1000 
total_lists = 5000 
outsz = 100 
maxsublistsz = 100 


# create random list of lists 
list_range_values = random.sample(xrange(total_lists),Nlists) 
list_list_values = [random.sample(xrange(outsz),np.random.randint(1,maxsublistsz)) for k in xrange(total_lists)] 

list_comp_values = 10*np.random.uniform(size=(total_lists,)) 

v = np.zeros((outsz,)) 

def indices(start, end): 
    lens = end - start 
    np.cumsum(lens, out=lens) 
    i = np.ones(lens[-1], dtype=int) 
    i[0] = start[0] 
    i[lens[:-1]] += start[1:] 
    i[lens[:-1]] -= end[:-1] 
    np.cumsum(i, out=i) 
    return i 

def sum_by_group(values, groups): 
    order = np.argsort(groups) 
    groups = groups[order] 
    values = values[order] 
    values.cumsum(out=values) 
    index = np.ones(len(groups), 'bool') 
    index[:-1] = groups[1:] != groups[:-1] 
    values = values[index] 
    groups = groups[index] 
    values[1:] = np.diff(values) 
    return values, groups 


""" 

method1=""" 
list_list_lens = np.array(map(len, list_list_values)) 
comp_vals_expanded = np.repeat(list_comp_values, list_list_lens) 

list_vals_flat = np.fromiter(itertools.chain.from_iterable(list_list_values),dtype=int) 
list_list_starts = np.concatenate(([0], np.cumsum(list_list_lens)[:-1])) 

toadd = indices(list_list_starts[list_range_values],(list_list_starts + list_list_lens)[list_range_values]) 

v[list_vals_flat[toadd]] += comp_vals_expanded[toadd] 
""" 

method2=""" 
for k in list_range_values: 
    v[list_list_values[k]] += list_comp_values[k] 

""" 

method3=""" 
llv = [list_list_values[i] for i in list_range_values] 
lcv = [list_comp_values[i] for i in list_range_values] 
counts = map(len, llv) 
indices = np.concatenate(llv) 
values = np.repeat(lcv, counts) 

totals, indices_unique = sum_by_group(values, indices) 
v[indices_unique] += totals 
""" 


t1 = Timer(method1,setup=setstr).timeit(100) 
print t1 

t2 = Timer(method2,setup=setstr).timeit(100) 
print t2 

t3 = Timer(method3,setup=setstr).timeit(100) 
print t3 

Đối với một số khá lớn các phần tử trong danh sách:

Method1: (không vòng lặp for -jterrace) 1.43 giây

Method2: (đối với vòng lặp) 4,62 giây

Method3: (không vòng lặp for - Bago) 2.99 giây

Đối với một số lượng nhỏ các danh sách (thay đổi Nlists-10) , vòng lặp for nhanh hơn đáng kể so với giải pháp của jterrace:

Phương pháp 1: (không cho vòng lặp): 1,05 giây

Method2: (đối với vòng lặp) 0,045 giây

Method3: (không vòng lặp for - Bago) 0,041 giây

này không phải là để gõ các giải pháp @jterrace hoặc @ Bago, mà là khá thanh lịch . Thay vào đó nó là để chỉ ra rằng thường lần một vòng lặp đơn giản không thực hiện mà kém.

Answer 2

Thứ nhất, thiết lập các biến bạn đã cho:

import numpy as np 
list_range_values = [1, 3, 5] 
list_list_values = [[3, 6, 7], [5, 7, 11, 25, 99], [8, 45], 
        [4, 7, 8], [0, 1], [21, 31, 41]] 
list_comp_values = [0.7, 9.8, 1.2, 5, 10, 11.7] 
v = np.arange(100, dtype=float) 

Tiếp theo, list_list_values và list_comp_values cần phải được san phẳng để họ tiếp giáp:

list_list_lens = np.array(map(len, list_list_values)) 
comp_vals_expanded = np.repeat(list_comp_values, list_list_lens) 
import itertools 
list_vals_flat = np.fromiter(itertools.chain.from_iterable(list_list_values), 
          dtype=int) 

Sau đó, các chỉ số bắt đầu của mỗi mảng con là cần thiết:

list_list_starts = np.concatenate(([0], np.cumsum(list_list_lens)[:-1])) 

Bây giờ chúng tôi có cả hai tarting và kết thúc giá trị, chúng ta có thể sử dụng indices function from this question để có được một loạt các chỉ số selector:

def indices(start, end): 
    lens = end - start 
    np.cumsum(lens, out=lens) 
    i = np.ones(lens[-1], dtype=int) 
    i[0] = start[0] 
    i[lens[:-1]] += start[1:] 
    i[lens[:-1]] -= end[:-1] 
    np.cumsum(i, out=i) 
    return i 

toadd = indices(list_list_starts[list_range_values], 
       (list_list_starts + list_list_lens)[list_range_values]) 

Bây giờ chúng ta đã làm tất cả ma thuật này, mảng có thể được thêm vào như thế này:

v[list_vals_flat[toadd]] += comp_vals_expanded[toadd] 

Answer 3

Sử dụng ví dụ đầu vào của bạn:

>>> list_list_values = [[3, 6, 7], [5, 7, 11, 25, 99], [8, 45], [4, 7, 8], 
         [0, 1], [21, 31, 41], [9, 11, 22, 33, 44], [17, 19]] 
>>> list_comp_values = [0.7, 9.8, 1.2, 5, 10, 11.7, 6, 0.2] 
>>> list_range_values = [1, 3, 5] 

Thứ nhất, một số shenanigans máy phát điện:

>>> indices_weights = ((list_list_values[i], list_comp_values[i]) 
         for i in list_range_values) 
>>> flat_indices_weights = ((i, weight) for indices, weight in indices_weights 
          for i in indices) 

Bây giờ chúng ta vượt qua các dữ liệu để numpy. Tôi không thể tìm ra cách để tạo ra một rec.array từ một trình lặp, vì vậy tôi phải chuyển đổi trình tạo ở trên thành một danh sách. Có thể có một cách để tránh điều đó ...

>>> i_w = numpy.rec.array(list(flat_indices_weights),  
          dtype=[('i', int), ('weight', float)]) 
>>> numpy.histogram(i_w['i'], bins=range(0, 100), weights=i_w['weight']) 
(array([ 0. , 0. , 0. , 0. , 5. , 9.8, 0. , 14.8, 5. , 
     0. , 0. , 9.8, 0. , 0. , 0. , 0. , 0. , 0. , 
     0. , 0. , 0. , 11.7, 0. , 0. , 0. , 9.8, 0. , 
     0. , 0. , 0. , 0. , 11.7, 0. , 0. , 0. , 0. , 
     0. , 0. , 0. , 0. , 0. , 11.7, 0. , 0. , 0. , 
     0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 
     0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 
     0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 
     0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 
     0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 
     0. , 0. , 0. , 0. , 0. , 0. , 0. , 0. , 9.8]), 
array([ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 
     17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 
     34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 
     51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 
     68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 
     85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99])) 

---

Tôi đã có một chút thời gian để theo dõi các bài kiểm tra JoshAdel với một cặp vợ chồng của riêng tôi. Giải pháp nhanh nhất cho đến nay sử dụng thiết lập của Bago nhưng thay thế chức năng sum_by_group với chức năng được xây dựng trong histogram. Dưới đây là những số liệu mà tôi đã (cập nhật):

Method1 (jterrace): 2,65

Method2 (đối với vòng lặp): 2,25

Method3 (Bago): 1,14

Method4 (biểu đồ): 2.82

Method5 (3/4 combo): 1.07

Lưu ý rằng khi được triển khai ở đây, phương pháp đầu tiên cho kết quả không chính xác theo thử nghiệm của tôi. Tôi không có thời gian để tìm ra vấn đề là gì. Mã cho thử nghiệm của tôi là dưới đây; nó chỉ nhẹ nhàng điều chỉnh mã gốc của JoshAdel, nhưng tôi đăng nó ở đây đầy đủ để thuận tiện. (Được cập nhật để bao gồm các bình luận của Bago và phần nào bị loại bỏ.)

from timeit import Timer 

setstr="""import numpy as np 
import itertools 
import random 

Nlists = 1000 
total_lists = 5000 
outsz = 100 
maxsublistsz = 100 

# create random list of lists 
list_range_values = random.sample(xrange(total_lists),Nlists) 
list_list_values = [random.sample(xrange(outsz),np.random.randint(1,maxsublistsz)) for k in xrange(total_lists)] 

list_comp_values = list(10*np.random.uniform(size=(total_lists,))) 

v = np.zeros((outsz,)) 

def indices(start, end): 
    lens = end - start 
    np.cumsum(lens, out=lens) 
    i = np.ones(lens[-1], dtype=int) 
    i[0] = start[0] 
    i[lens[:-1]] += start[1:] 
    i[lens[:-1]] -= end[:-1] 
    np.cumsum(i, out=i) 
    return i 

def sum_by_group(values, groups): 
    order = np.argsort(groups) 
    groups = groups[order] 
    values = values[order] 
    values.cumsum(out=values) 
    index = np.ones(len(groups), 'bool') 
    index[:-1] = groups[1:] != groups[:-1] 
    values = values[index] 
    groups = groups[index] 
    values[1:] = np.diff(values) 
    return values, groups 


""" 

setstr_test = setstr + "\nprint_v = True\n" 

method1=""" 
list_list_lens = np.array(map(len, list_list_values)) 
comp_vals_expanded = np.repeat(list_comp_values, list_list_lens) 

list_vals_flat = np.fromiter(itertools.chain.from_iterable(list_list_values),dtype=int) 
list_list_starts = np.concatenate(([0], np.cumsum(list_list_lens)[:-1])) 

toadd = indices(list_list_starts[list_range_values],(list_list_starts + list_list_lens)[list_range_values]) 

v[list_vals_flat[toadd]] += comp_vals_expanded[toadd] 
""" 

method2=""" 
for k in list_range_values: 
    v[list_list_values[k]] += list_comp_values[k] 
""" 

method3=""" 
llv = [np.fromiter(list_list_values[i], 'int') for i in list_range_values] 
lcv = [list_comp_values[i] for i in list_range_values] 
counts = map(len, llv) 
indices = np.concatenate(llv) 
values = np.repeat(lcv, counts) 

totals, indices_unique = sum_by_group(values, indices) 
v[indices_unique] += totals 
""" 

method4=""" 
indices_weights = ((list_list_values[i], list_comp_values[i]) for i in list_range_values) 
flat_indices_weights = ((i, weight) for indices, weight in indices_weights for i in indices) 
i_w = np.rec.array(list(flat_indices_weights), dtype=[('i', 'i'), ('weight', 'd')]) 
v += np.histogram(i_w['i'], bins=range(0, outsz + 1), weights=i_w['weight'], new=True)[0] 
""" 

method5=""" 
llv = [np.fromiter(list_list_values[i], 'int') for i in list_range_values] 
lcv = [list_comp_values[i] for i in list_range_values] 
counts = map(len, llv) 
indices = np.concatenate(llv) 
values = np.repeat(lcv, counts) 

v += np.histogram(indices, bins=range(0, outsz + 1), weights=values, new=True)[0] 
""" 


t1 = Timer(method1,setup=setstr).timeit(100) 
print t1 

t2 = Timer(method2,setup=setstr).timeit(100) 
print t2 

t3 = Timer(method3,setup=setstr).timeit(100) 
print t3 

t4 = Timer(method4,setup=setstr).timeit(100) 
print t4 

t5 = Timer(method5,setup=setstr).timeit(100) 
print t5 

exec(setstr_test + method1 + "\nprint v\n") 
exec("\nv = np.zeros((outsz,))\n" + method2 + "\nprint v\n") 
exec("\nv = np.zeros((outsz,))\n" + method3 + "\nprint v\n") 
exec("\nv = np.zeros((outsz,))\n" + method4 + "\nprint v\n") 
exec("\nv = np.zeros((outsz,))\n" + method5 + "\nprint v\n")