消除for循環Python和NumPy的構建

Question

我正在尋找在Python和/或numpy的量化的方法來消除使用一個for循環以下：

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

其中：

• list_range_values是一個整數值的Python列表，例如。 [1，3，5]，從範圍（0，R-1，1）中抽取

• list_comp_values是一個Python數值列表，例如。 [0.7，9.8，1.2，5，10，11.7，6，0.2]使得len（list_comp_values）= R

• v是長度爲V的numpy向量，使得R可以是比V list_list_values是列表的Python列表（每個列表包含不同數目的整數值，例如[[3,6,7]，[5,7,11,25,99]，[8,45] ，[0，1，21,31,41]，[9,11,22,33,44]，[17,19]]）的範圍（0，V -1，1）和len（list_list_values）= R

例如，

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) 

有沒有一種方法可以消除for-loop？ Cython，Scipy/Weave/Blitz和C模塊是替代解決方案，但是要確定是否首先有Numpy向量化答案。你給

Answer 1

雖然它通常會導致大量加速消除循環，並利用numpy內置插件/矢量化。我只想指出，情況並非總是如此。對簡單循環和更多涉及的向量化進行定時，不會給你一個很大的加速並且更加冗長。只是要考慮：

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 

一個相當大量的列表中的元素：

方法一：（無for循環-jterrace）1。43秒

方法2：（用於環路）4.62秒

方法3：（無for循環 - 巴戈）2.99秒

對於少數列表（變化Nlists〜10） ，for循環比jterrace的解決方案明顯更快：

方法1：（no for loop -jterrace）1.05秒

方法二：（for循環）0.045秒

方法3：（無for循環 - 巴戈）0.041秒

這不是敲@jterrace或@巴戈的解決方案，這是很優雅。相反，需要指出的是，一個簡單的for循環通常不會很差。

Answer 2

首先，設置變量：

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) 

接下來，list_list_values和list_comp_values需要被夷爲平地所以他們連續：

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) 

然後，每個子陣列的起始指數需要：

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

既然我們有兩個s tarting和結束的值，我們可以使用indices function from this question獲得選擇索引數組：

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

現在，我們所做的這一切魔法，該陣列可以被添加到這樣的：

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

Answer 3

使用您的示例輸入：

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

首先，一些有心計的發電機：

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

現在我們將數據傳遞到numpy。我不知道如何從迭代器生成rec.array，所以我必須將上面的生成器轉換爲列表。也許有避免的方式...

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

---

我過會兒跟進JoshAdel與幾個我自己的測試。到目前爲止最快的解決方案使用Bago的設置，但用內置的histogram函數取代了sum_by_group功能。下面是我得到的數字（更新）：

方法1（jterrace）：2.65

方法2（用於環路）：2.25

方法3（巴戈）：1.14

方法4（直方圖）：2.82

Method5（3/4組合）：1.07

需要注意的是這裏實現的，第一種方法，根據我的測試給出了不正確的結果。我沒有時間弄清楚問題所在。我的測試代碼如下所示;它只是輕輕調整JoshAdel的原始代碼，但爲了方便起見，我在這裏完整地發佈它。 （已更新，以包括Bago的評論，並且有些被取消）

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