Устранить цикл 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, такой, что 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 и гораздо более сложная векторизация не дают большого ускорения и намного более многословны.Просто кое-что рассмотреть:

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

Для довольно большого количества элементов в списке:

Method1: (нет для цикла -jterrace) 1,43 секунды

Метод 2: (для петли) 4,62 секунды

Метод 3: (нет для петли - баго) 2,99 секунды

Для небольшогочисло списков (измените Nlists на 10), цикл for значительно быстрее решения jterrace:

Method1: (нет для цикла -jterrace) 1,05 секунды

Метод2: (для петли) 0,045 секунд

Метод3: (нет для петли - баго) 0,041 секунды

Это не стучит @Решения jterrace или @ bago, которые довольно элегантны.Скорее следует отметить, что часто простой цикл for не работает так плохо.

Answer 2

Используя ваш пример ввода:

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

---

У меня был момент, чтобы проконтролировать тесты Джоша Аделя с парой моих собственных. Самое быстрое решение до сих пор использует настройку Bago, но заменяет функцию sum_by_group на встроенную функцию histogram. Вот числа, которые я получил (обновлено) :

Method1 (jterrace): 2,65

Метод 2 (для цикла): 2,25

Method3 (Bago): 1,14

Метод 4 (гистограмма): 2,82

Метод 5 (3/4 комбинированный): 1,07

Обратите внимание, что, как реализовано здесь, первый метод дает неверные результаты в соответствии с моим тестом. У меня не было времени выяснить, в чем проблема. Код для моего теста ниже; он лишь слегка корректирует исходный код Джошадела, но я выложу его здесь полностью для удобства. (Обновлено, чтобы включить комментарии Баго и несколько убрано.)

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

Answer 3

Сначала настройте переменные, которые вы дали:

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

Теперь, когда у нас есть начальное и конечное значения, мы можем использовать функцию индексов из этого вопроса , чтобы получить массив индексов селектора:

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]