Jak odejść od szkoły myślenia „for-loop”?

79

To dość konceptualne pytanie, ale miałem nadzieję, że uda mi się uzyskać w tym zakresie kilka dobrych rad. Wiele programowania, które wykonuję, to tablice ( NumPy ); Często muszę dopasowywać elementy w co najmniej dwóch tablicach o różnych rozmiarach, a pierwszą rzeczą, do której się wybieram, jest pętla for lub, co gorsza, zagnieżdżona pętla for. Chcę jak najbardziej unikać pętli for, ponieważ są one powolne (przynajmniej w Pythonie).

Wiem, że w wielu sprawach z NumPy istnieją wcześniej zdefiniowane polecenia, które muszę po prostu zbadać, ale czy ty (jako bardziej doświadczeni programiści) masz ogólny proces myślowy, który przychodzi ci na myśl, gdy musisz coś powtórzyć?

Często mam coś takiego, co jest okropne i chcę tego uniknąć:

small_array = np.array(["one", "two"])
big_array = np.array(["one", "two", "three", "one"])

for i in range(len(small_array)):
    for p in range(len(big_array)):
        if small_array[i] == big_array[p]:
            print "This item is matched: ", small_array[i]

Wiem, że istnieje wiele różnych sposobów osiągnięcia tego w szczególności, ale interesuje mnie ogólna metoda myślenia, jeśli istnieje.

Rzepa
źródło
10
Szukasz programowania funkcjonalnego : wyrażeń lambda, funkcji wyższego rzędu, generowania wyrażeń itp. Google.
Kilian Foth
42
I want to avoid for-loops as much as possible because they are slow (at least in Python).Wygląda na to, że rozwiązujesz tutaj zły problem. Jeśli potrzebujesz iterować nad czymś, musisz iterować nad czymś; uzyskasz podobny wynik wydajności bez względu na to, jakiej konstrukcji Python używasz. Jeśli twój kod jest wolny, to nie dlatego, że masz forpętle; to dlatego, że wykonujesz niepotrzebną pracę lub pracę po stronie Pythona, którą można wykonać po stronie C. W twoim przykładzie wykonujesz dodatkową pracę; mogłeś to zrobić za pomocą jednej pętli zamiast dwóch.
Doval
24
@Doval Niestety nie - w NumPy . Python do pętli wykonujący dodawanie elementarne może być kilka razy (!) Wolniejszy niż wektoryzowany operator NumPy (który jest napisany nie tylko w C, ale używa instrukcji SSE i innych sztuczek) dla uzyskania realistycznych rozmiarów tablicy.
46
Niektóre z powyższych komentarzy wydają się źle rozumieć pytanie. Programując w NumPy, możesz uzyskać najlepsze wyniki, jeśli możesz wektoryzować swoje obliczenia - to znaczy zastąpić wyraźne pętle w Pythonie operacjami na całej tablicy w NumPy. Jest to bardzo różniące się koncepcyjnie od zwykłego programowania w Pythonie i wymaga czasu na naukę. Sądzę więc, że OP powinien poprosić o radę, jak się uczyć.
Gareth Rees
3
@PieterB: Tak, zgadza się. „Wektoryzacja” to nie to samo, co „wybranie najlepszego algorytmu”. Są to dwa osobne źródła trudności w opracowywaniu wydajnych implementacji, dlatego najlepiej o nich myśleć pojedynczo.
Gareth Rees

Odpowiedzi:

89

Jest to powszechna trudność koncepcyjna podczas nauki efektywnego używania NumPy . Zwykle przetwarzanie danych w Pythonie najlepiej wyraża się w postaci iteratorów , aby utrzymać niskie zużycie pamięci, zmaksymalizować możliwości równoległości z systemem I / O oraz zapewnić ponowne użycie i kombinację części algorytmów.

Ale NumPy odwraca to wszystko na lewą stronę: najlepszym podejściem jest wyrażenie algorytmu jako sekwencji operacji na całej tablicy , aby zminimalizować czas spędzany w wolnym interpreterze Pythona i zmaksymalizować ilość czasu spędzonego w szybko skompilowanych procedurach NumPy.

Oto moje ogólne podejście:

  1. Zachowaj oryginalną wersję funkcji (co do której masz pewność, że jest poprawna), abyś mógł przetestować ją pod kątem poprawionych wersji zarówno pod względem poprawności, jak i szybkości.

  2. Pracuj od wewnątrz: to znaczy zacznij od wewnętrznej pętli i sprawdź, czy można ją wektoryzować; kiedy to zrobisz, wyjdź o jeden poziom i kontynuuj.

  3. Poświęć dużo czasu na czytanie dokumentacji NumPy . Jest tam wiele funkcji i operacji i nie zawsze są one genialnie nazwane, więc warto je poznać. W szczególności, jeśli pomyślisz, że „gdyby tylko istniała funkcja, która spełniała takie i takie”, to warto poświęcić dziesięć minut na jej szukanie. Zazwyczaj gdzieś tam jest.

Nie ma substytutu dla praktyki, więc dam wam kilka przykładowych problemów. Celem dla każdego problemu jest przepisać funkcję tak, że jest w pełni wektorowy , to znaczy tak, że składa się z sekwencji operacji NumPy na całych tablic, bez rodzimych pętli Pythona (bez forlub whilesprawozdania nie iteratorów lub listowe).

Problem 1

def sumproducts(x, y):
    """Return the sum of x[i] * y[j] for all pairs of indices i, j.

    >>> sumproducts(np.arange(3000), np.arange(3000))
    20236502250000

    """
    result = 0
    for i in range(len(x)):
        for j in range(len(y)):
            result += x[i] * y[j]
    return result

Problem 2

def countlower(x, y):
    """Return the number of pairs i, j such that x[i] < y[j].

    >>> countlower(np.arange(0, 200, 2), np.arange(40, 140))
    4500

    """
    result = 0
    for i in range(len(x)):
        for j in range(len(y)):
            if x[i] < y[j]:
                result += 1
    return result

Problem 3

def cleanup(x, missing=-1, value=0):
    """Return an array that's the same as x, except that where x ==
    missing, it has value instead.

    >>> cleanup(np.arange(-3, 3), value=10)
    ... # doctest: +NORMALIZE_WHITESPACE
    array([-3, -2, 10, 0, 1, 2])

    """
    result = []
    for i in range(len(x)):
        if x[i] == missing:
            result.append(value)
        else:
            result.append(x[i])
    return np.array(result)

Spojlery poniżej. Osiągniesz najlepsze wyniki, jeśli sam spróbujesz, zanim spojrzysz na moje rozwiązania!

odpowiedź 1

np.sum (x) * np.sum (y)

Odpowiedź 2

np.sum (np.searchsorted (np.sort (x), y))

Odpowiedź 3

np. gdzie (x == brak, wartość, x)

Gareth Rees
źródło
Zaraz, czy w ostatniej odpowiedzi jest literówka, czy też NumPy modyfikuje sposób, w jaki Python interpretuje kod?
Izkata
1
@Izkata Nic nie modyfikuje per se, ale zdefiniowano operacje logiczne zastosowane do tablic, aby zwrócić tablice boolowskie.
sapi
@sapi Ach, tęskniłem za tym, co dzieje się w trakcie doctestów, myślałem, że to było jasnelist
Izkata
Może powinien istnieć sposób na osadzenie APL?
Uwielbiam sposób odrabiania lekcji.
Koray Tugay,
8

Aby przyspieszyć, musisz przeczytać swoje struktury danych i użyć odpowiednich.

W przypadku nietrywialnych rozmiarów małej tablicy i dużej tablicy (powiedzmy mała = 100 elementów i duża = 10.000 elementów) jednym ze sposobów jest posortowanie małej tablicy, a następnie iteracja po dużej tablicy i użycie wyszukiwania binarnego w celu znalezienia pasujących elementów w małej tablicy.

To spowodowałoby maksymalną złożoność czasową, O (N log N) (a dla małych małych i bardzo dużych dużych tablic jest bliżej O (N)), gdzie rozwiązaniem zagnieżdżonej pętli jest O (N ^ 2)

Jednak. to, które struktury danych są najbardziej wydajne, zależy w dużym stopniu od rzeczywistego problemu.

Pieter B.
źródło
-3

Możesz użyć słownika, aby znacznie zoptymalizować wydajność

To kolejny przykład:

locations = {}
for i in range(len(airports)):
    locations[airports["abb"][i][1:-1]] = (airports["height"][i], airports["width"][i])

for i in range(len(uniqueData)):
    h, w = locations[uniqueData["dept_apt"][i]]
    uniqueData["dept_apt_height"][i] = h
    uniqueData["dept_apt_width"][i] = w
Jakub Bares
źródło
2
Jest to nadal całkiem wyraźnie przy użyciu szkoły myślenia „for-loop”.
8bittree,