eliminare ciclo for in Python e Numpy costruisco

Question

Sto cercando un metodo in Python e/o Numpy vettorializzazione di eliminare l'uso di un ciclo for per i seguenti:

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

dove:

• list_range_values ​​è un elenco Python di valori interi es. [1, 3, 5], tratto dall'intervallo (0, R-1, 1)

• list_comp_values ​​è un elenco Python di valori numerici es. [0.7, 9.8, 1.2, 5, 10, 11.7, 6, 0.2] tale che len (list_comp_values) = R

• v è un vettore numerico di lunghezza V tale che R può essere <, =,> di V

• list_list_values ​​è un elenco di elenchi Python (ogni elenco contiene un numero diverso di valori interi ad es. [[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]]) estratti dall'intervallo (0, V -1, 1) e con len (list_list_values) = R

Es.

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) 

Esiste un metodo che consente di eliminare il ciclo?

Cython, Scipy/Weave/Blitz e un modulo C sono soluzioni alternative ma si vuole accertare se esiste una risposta di vettorizzazione Numpy prima.

Answer 1

Mentre spesso si verifica un notevole aumento della velocità per eliminare i loop e sfruttare la built-in/vettorizzazione numpy. Vorrei solo sottolineare che non è sempre il caso. Cronometrare il ciclo semplice per il ciclo vs la vettorizzazione molto più coinvolta, non ti dà una grande accelerazione ed è molto più prolisso. Solo una cosa da considerare:

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 

Per un bel gran numero di elementi nella lista:

Method1: (nessun ciclo for -jterrace) 1.43 secondi

Method2: (per ciclo) 4,62 secondi

method3: (no per ciclo - Bago) 2.99 secondi

Per un piccolo numero di liste (cambiamento Nlists-10) , il ciclo for è significativamente più veloce rispetto alla soluzione di jterrace:

Method1: (nessun ciclo for -jterrace) 1.05 secondi

012.

Method2: (per ciclo) 0.045 secondi

method3: (no per ciclo - Bago) 0,041 secondi

Questo non è quello di bussare soluzioni @jterrace o @ di Bago, che sono molto elegante . Piuttosto, è necessario sottolineare che spesso un semplice ciclo for non funziona così male.

Answer 2

In primo luogo, impostare le variabili ti ha dato:

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) 

Avanti, list_list_values e list_comp_values necessità di essere appiattito in modo che siano contigue:

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) 

Poi, gli indici di partenza di ogni sottomatrice sono necessario:

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

Ora che abbiamo entrambi i s tarting e termina valori, possiamo usare il indices function from this question per ottenere un array di indici di selezione:

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

Ora che abbiamo fatto tutta questa magia, l'array può essere aggiunto a questo modo:

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

Answer 3

Usando il vostro ingresso esempio:

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

primo luogo, alcuni imbrogli generatore:

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

Ora passiamo i dati numpy. Non riesco a capire come produrre un rec.array da un iteratore, quindi ho dovuto convertire il generatore di cui sopra in un elenco. Forse c'è un modo per evitare che ...

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

---

ho avuto un momento di follow-up sui test di JoshAdel con un paio di mio. La soluzione più veloce finora utilizza il set up di Bago, ma sostituisce la funzione sum_by_group con la funzione integrata histogram. Ecco i numeri che ho ottenuto (aggiornato):

Method1 (jterrace): 2,65

Method2 (per ciclo): 2,25

method3 (Bago): 1.14

Metodo4 (istogramma): 2,82

Method5 (3/4 combinata): 1.07

Si noti che come attuata qui, il primo metodo dà risultati errati secondo la mia prova. Non ho avuto il tempo di capire quale sia il problema. Il codice per il mio test è sotto; regola solo delicatamente il codice originale di JoshAdel, ma lo metto qui per intero per comodità. (Aggiornato per includere i commenti di Bago e in qualche modo disassemblati.)

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