Uso efficiente di generatori Python in uno stretto doppio per array loop su numpy

Question

Il collo di bottiglia della velocità nel mio codice è un doppio stretto per gli elementi di loop su due array, xe y. Un trucco hpc standard per migliorare le prestazioni consiste nel fare il ciclo in blocchi in modo che i problemi di cache possano essere ridotti al minimo. Sto cercando di usare i generatori Python per eseguire lo chunking, ma la necessità di ricreare continuamente il generatore speso all'interno del ciclo for esterno sta uccidendo il mio runtime.

Domanda:

Esiste un algoritmo più intelligente per costruire il generatore appropriata per l'esecuzione di chunked doppio per i cicli?

illustrazione Calcestruzzo:

creerò due array fittizi, x, e y. Li terremo cortesi per l'illustrazione, ma in pratica si tratta di array numpy con elementi ~ 1e6.

x = np.array(['a', 'b', 'b', 'c', 'c', 'd']) 
y = np.array(['e', 'f', 'f', 'g']) 

Il doppio ingenua ciclo for sarebbe solo:

for xletter in x: 
    for yletter in y: 
     # algebraic manipulations on x & y 

Ora cerchiamo di usare i generatori di fare questo ciclo in blocchi:

chunk_size = 3 
xchunk_gen = (x[i: i+chunk_size] for i in range(0, len(x), chunk_size)) 
for xchunk in xchunk_gen: 
    ychunk_gen = (y[i: i+chunk_size] for i in range(0, len(y), chunk_size)) 
    for ychunk in ychunk_gen: 
     for xletter in xchunk: 
      for yletter in ychunk: 
       # algebraic manipulations on x & y 

Nota che, al fine di implementare una soluzione generatore a questo problema, devo ricreare continuamente ychunk_gen all'interno del ciclo esterno. Dal y è un array di grandi dimensioni, questo sta uccidendo il mio runtime (per elementi ~ 1e6, la creazione di questo generatore richiede ~ 20ms sul mio laptop).

C'è un modo per essere più intelligente su come sto costruendo i miei generatori che aggirano questo problema? O sarà necessario abbandonare del tutto la soluzione del generatore?

(Nota: in pratica, sto usando cython per eseguire questo ciclo stretto, ma tutto quanto sopra si applica a prescindere).

Answer 1

A mio parere, la creazione dell'espressione del generatore sta uccidendo il tempo di esecuzione perché non è ottimizzato da cython.

Una soluzione migliore, che si occupa di tutte le operazioni di ottimizzazione della cache, è l'utilizzo di numexpr. Poiché la manipolazione di x e y è algebrica, dovrebbe adattarsi molto bene ai vincoli (numexpr può fare un po 'di più)

Answer 2

Si sta definendo lo ychunk_gen di nuovo all'interno del ciclo xchunk.Forse il seguente sarà più veloce:

chunk_size = 3 
xchunk_gen = (x[i: i+chunk_size] for i in xrange(0, len(x), chunk_size)) 

def ychunk_gen(some_dependency_on_outer_loop): 
    # use some_dependency_on_outer_loop 
    for i in xrange(0, len(y), chunk_size): 
     yield y[i: i+chunk_size] 

for xchunk in xchunk_gen: 
    for ychunk in ychunk_gen(chunk_or_something_else): 
     for xletter in xchunk: 
      for yletter in ychunk: 
       # algebraic manipulations on x & y 

Ma forse c'è un modo ancora migliore:

Presumo x e y sono numpy array, in modo da poter rimodellare gli array e quindi scorrere ogni riga:

for xchunk in x.reshape((len(x)//chunk_size, chunk_size)): 
    for ychunk in y.reshape((len(y)//chunk_size, chunk_size)): 
     # the letter loops 

In http://docs.scipy.org/doc/numpy/reference/generated/numpy.reshape.html ho letto che se si voleva i dati non devono essere copiati da reshape, è necessario modificare il shape -property dei dati:

x.shape = len(x)//chunk_size, chunk_size 
y.shape = len(y)//chunk_size, chunk_size 

Answer 3

itertools.tee possono dare un modesto risparmio di tempo:

y = np.arange(100) 
def foo1(y): 
    # create ygen each loop 
    # py3 so range is a generator 
    for j in range(100): 
     ygen=(y[i:i+10] for i in range(0,1000,10)) 
     r = [x.sum() for x in ygen] 
    return r 

def foo3(y): 
    # use tee to replicate the gen 
    ygen=(y[i:i+10] for i in range(0,1000,10)) 
    ygens=itertools.tee(ygen,100) 
    for g in ygens: 
     r=[x.sum() for x in g] 
    return r 

In [1123]: timeit foo3(y) 
10 loops, best of 3: 108 ms per loop 
In [1125]: timeit foo1(y) 
10 loops, best of 3: 144 ms per loop 

Ma sulla base

http://docs.cython.org/0.15/src/userguide/limitations.html#generators-and-generator-expressions

Dal Cython 0,13, alcune espressioni del generatore sono supportati quando possono essere trasformati in anelli interni in combinazione con builtin, ad es somma (x * 2 per x in seq). A partire da 0.14, i builtin supportati sono list(), set(), dict(), sum(), any(), all(), ordinati().

Mi chiedo cosa cython sta facendo con le espressioni del generatore Chunked.

---

Rimodellare e iterazione su righe non aiuta molto con il tempo.

def foo4(y): 
    y2d=y.reshape(100,10) 
    for _ in range(100): 
     r=[x.sum() for x in y2d] 
    return r 

è un po 'più lento del generatore teed. Naturalmente tempistiche relative come questa potrebbero cambiare con le dimensioni dell'array.