Efektywne wykorzystanie generatorów python w ciasnej podwójnej pętli nad liczbowymi tablicami

Question

Wąskim gardłem prędkości w moim kodzie jest ciasna podwójna pętla nad elementami dwóch tablic, x i y. Standardową sztuczką hpc do poprawy wydajności jest wykonywanie pętli w porcjach, aby można było zminimalizować chybienia pamięci podręcznej. Próbuję użyć generatorów Pythona do robienia kawałków, ale potrzeba ciągłego odtwarzania zużytego generatora w zewnętrznej pętli fora zabija moje środowisko uruchomieniowe.

Pytanie:

Czy jest bardziej inteligentny algorytm konstruowania odpowiedni generator for the Performing pakietowego podwójnej pętli?

ilustracja Beton:

będę tworzyć dwie tablice obojętne, x i y. Będę trzymać je za ilustrację, ale w praktyce są to numpy tablice z ~ 1e6 elementami.

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

Naiwny podwójnej pętli będzie tylko:

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

Teraz użyjmy generatory to zrobić pętlę w kawałkach:

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 

pamiętać, że w celu wdrożenia rozwiązania generatora do tego problemu, muszę ciągle odtwarzać ychunk_gen w zewnętrznej pętli. Ponieważ y jest dużą tablicą, to zabija moje środowisko uruchomieniowe (dla ~ 1e6 elementów, stworzenie tego generatora zajmuje ~ 20ms na moim laptopie).

Czy istnieje sposób, aby być bardziej sprytnym na temat tego, w jaki sposób konstruuję generatory, które radzą sobie z tym problemem? A może trzeba będzie po prostu całkowicie zrezygnować z rozwiązania generatora?

(Uwaga: W praktyce używam cythonu do wykonania tej ciasnej pętli, ale wszystkie powyższe zasady obowiązują niezależnie).

Answer 1

Moim zdaniem, tworzenie ekspresji generatora zabija czas pracy, ponieważ nie jest zoptymalizowane przez cyton.

Lepszym rozwiązaniem, które dba o wszystkie funkcje optymalizacji pamięci podręcznej, jest użycie numexpr. Ponieważ manipulacja x i y jest algebraiczna, powinna bardzo dobrze pasować do twoich ograniczeń (numexpr może zrobić trochę więcej)

Answer 2

Definiujesz ponownie ychunk_gen w pętli Xchunk.Może dodaje będzie szybciej:

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 

Ale może jest jeszcze lepszy sposób:

Zakładam x i y są numpy tablice, dzięki czemu można przekształcić tablic i następnie pętli każdej linii:

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 

W http://docs.scipy.org/doc/numpy/reference/generated/numpy.reshape.html czytałem, że jeśli chciałeś dane nie mogą być kopiowane przez reshape, należy zmienić shape -property danych:

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

Answer 3

itertools.tee może dać skromne oszczędności czasowych:

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 

Ale na podstawie

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

Od Cython 0,13, niektóre wyrażenia generatory są obsługiwane, gdy mogą one być przekształcone w pętle inlined w połączeniu z wbudowanymi, np suma (x * 2 dla x w seq). Od wersji 0.14 obsługiwanymi wbudowaniami są: list(), set(), dict(), sum(), any(), all(), sorted().

Zastanawiam się, co robi cython z twoimi wyodrębnionymi wyrażeń generatora.

---

Przekształcanie i powtarzanie wierszy nie pomaga z upływem czasu.

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

jest nieco wolniejsza niż generatora teed. Oczywiście względne taktowanie może zmienić się wraz z rozmiarem macierzy.