python - 消除 Python 和 Numpy 构造中的 for 循环

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 ], [4, 7, 8], [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 循环？

Cython、Scipy/Weave/Blitz 和 C 模块是替代解决方案，但首先要确定是否有 Numpy 向量化答案。

Answer 1

虽然它通常会导致大幅加速以消除 for 循环并利用 numpy 内置函数/矢量化。我只想指出，情况并非总是如此。为简单的 for 循环计时与更复杂的矢量化相比，不会给你带来很大的加速，而且更加冗长。只是需要考虑的事情:

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:(for循环)4.62秒

方法 3:(无 for 循环 - bago)2.99 秒

对于少量列表(将Nlists改为10)，for循环明显比jterrace的方案快:

方法一:(无for循环-jterrace)1.05秒

方法2:(for循环)0.045秒

方法 3:(无 for 循环 - bago)0.041 秒

这里不是敲@jterrace或者@bago的方案，还是比较优雅的。而是要指出，简单的 for 循环通常不会执行得那么差。