Dlaczego tablice Pythona są wolne?

Spodziewałem array.arraysię, że będę szybszy niż listy, ponieważ tablice wydają się być rozpakowane.

Jednak otrzymuję następujący wynik:

In [1]: import array

In [2]: L = list(range(100000000))

In [3]: A = array.array('l', range(100000000))

In [4]: %timeit sum(L)
1 loop, best of 3: 667 ms per loop

In [5]: %timeit sum(A)
1 loop, best of 3: 1.41 s per loop

In [6]: %timeit sum(L)
1 loop, best of 3: 627 ms per loop

In [7]: %timeit sum(A)
1 loop, best of 3: 1.39 s per loop

Co może być przyczyną takiej różnicy?

Przechowywanie jest „rozpakowanych”, ale za każdym razem uzyskać dostęp do elementu Python ma do „skrzynki” to (umieścić go w sposób regularny obiekt Pythona), aby zrobić coś z nim. Na przykład, twoja sum(A)iteracja po tablicy i umieszcza każdą liczbę całkowitą, pojedynczo, w zwykłym intobiekcie Pythona . To kosztuje czas. W twoim przypadku sum(L), wszystko zostało wykonane w momencie tworzenia listy.

Ostatecznie macierz jest generalnie wolniejsza, ale wymaga znacznie mniej pamięci.

Oto odpowiedni kod z najnowszej wersji Pythona 3, ale te same podstawowe pomysły dotyczą wszystkich implementacji CPythona od czasu pierwszego wydania Pythona.

Oto kod dostępu do elementu listy:

PyObject *
PyList_GetItem(PyObject *op, Py_ssize_t i)
{
    /* error checking omitted */
    return ((PyListObject *)op) -> ob_item[i];
}

Jest w tym bardzo mało: somelist[i]po prostu zwraca i'-ty obiekt na liście (a wszystkie obiekty Pythona w CPythonie są wskaźnikami do struktury, której początkowy segment jest zgodny z układem a struct PyObject).

A oto __getitem__implementacja dla arrayz kodem typu l:

static PyObject *
l_getitem(arrayobject *ap, Py_ssize_t i)
{
    return PyLong_FromLong(((long *)ap->ob_item)[i]);
}

Pamięć surowa jest traktowana jako wektor C longliczb całkowitych natywnych dla platformy ; i„th C longjest odczytywany w górę; a następnie PyLong_FromLong()jest wywoływana w celu zawijania („box”) natywnego obiektu C longw Pythonie long(który w Pythonie 3, który eliminuje rozróżnienie między inti w Pythonie 2 long, jest w rzeczywistości wyświetlany jako typ int).

To opakowanie musi przydzielić nową pamięć dla intobiektu Pythona i rozpylić C longdo niego bity natywnego . W kontekście oryginalnego przykładu, okres istnienia tego obiektu jest bardzo krótki (wystarczy, sum()aby dodać zawartość do bieżącej sumy), a następnie zwolnienie nowego intobiektu wymaga więcej czasu .

To stąd bierze się różnica prędkości, zawsze pochodziła i zawsze będzie pochodzić w implementacji CPythona.

Aby dodać do doskonałej odpowiedzi Tima Petersa, tablice implementują protokół bufora , podczas gdy listy nie. Oznacza to, że jeśli piszesz rozszerzenie C (lub moralny odpowiednik, taki jak pisanie modułu Cython ), możesz uzyskać dostęp do elementów tablicy i pracować z nimi znacznie szybciej niż cokolwiek Python może zrobić. Zapewni to znaczną poprawę szybkości, prawdopodobnie znacznie przekraczającą rząd wielkości. Ma jednak kilka wad:

1. Zajmujesz się teraz pisaniem w C zamiast w Pythonie. Cython to jeden ze sposobów na poprawę tego, ale nie eliminuje on wielu fundamentalnych różnic między językami; musisz znać semantykę języka C i rozumieć, co on robi.
2. C API PyPy działa do pewnego stopnia , ale nie jest zbyt szybki. Jeśli celujesz w PyPy, prawdopodobnie powinieneś po prostu napisać prosty kod ze zwykłymi listami, a następnie pozwolić JITterowi zoptymalizować go dla Ciebie.
3. Rozszerzenia C są trudniejsze w dystrybucji niż czysty kod Pythona, ponieważ muszą zostać skompilowane. Kompilacja jest zwykle zależna od architektury i systemu operacyjnego, więc musisz upewnić się, że kompilujesz dla platformy docelowej.

Idąc prosto do rozszerzeń C, możesz użyć młota kowalskiego do uderzenia muchy, w zależności od przypadku użycia. Najpierw powinieneś zbadać NumPy i sprawdzić, czy jest wystarczająco potężny, aby wykonać dowolną matematykę, którą próbujesz zrobić. Będzie również znacznie szybszy niż natywny Python, jeśli będzie używany poprawnie.

Tim Peters odpowiedział, dlaczego jest to powolne, ale zobaczmy, jak to poprawić .

Trzymając się twojego przykładu sum(range(...))(współczynnik 10 mniejszy niż twój przykład, aby zmieścić się w pamięci tutaj):

import numpy
import array
L = list(range(10**7))
A = array.array('l', L)
N = numpy.array(L)

%timeit sum(L)
10 loops, best of 3: 101 ms per loop

%timeit sum(A)
1 loop, best of 3: 237 ms per loop

%timeit sum(N)
1 loop, best of 3: 743 ms per loop

W ten sposób numpy musi również box / unbox, co ma dodatkowy narzut. Aby było to szybkie, należy trzymać się kodu numpy c:

%timeit N.sum()
100 loops, best of 3: 6.27 ms per loop

Więc od rozwiązania listy do wersji numpy jest to współczynnik 16 w czasie wykonywania.

Sprawdźmy też, jak długo trwa tworzenie tych struktur danych

%timeit list(range(10**7))
1 loop, best of 3: 283 ms per loop

%timeit array.array('l', range(10**7))
1 loop, best of 3: 884 ms per loop

%timeit numpy.array(range(10**7))
1 loop, best of 3: 1.49 s per loop

%timeit numpy.arange(10**7)
10 loops, best of 3: 21.7 ms per loop

Zdecydowany zwycięzca: Numpy

Należy również pamiętać, że tworzenie struktury danych zajmuje mniej więcej tyle samo czasu, co sumowanie, jeśli nie więcej. Przydzielanie pamięci jest powolne.

Wykorzystanie pamięci tych:

sys.getsizeof(L)
90000112
sys.getsizeof(A)
81940352
sys.getsizeof(N)
80000096

Więc zajmują one 8 bajtów na liczbę z różnym narzutem. Dla zakresu, którego używamy, wystarczą liczby 32-bitowe, więc możemy zaoszczędzić trochę pamięci.

N=numpy.arange(10**7, dtype=numpy.int32)

sys.getsizeof(N)
40000096

%timeit N.sum()
100 loops, best of 3: 8.35 ms per loop

Okazuje się jednak, że dodanie 64-bitowych intów jest szybsze niż 32-bitowe int na moim komputerze, więc jest to tego warte tylko wtedy, gdy jesteś ograniczony pamięcią / przepustowością.

proszę zauważyć, że 100000000oznacza to, że 10^8nie należy 10^7, a moje wyniki są następujące:

100000000 == 10**8

# my test results on a Linux virtual machine:
#<L = list(range(100000000))> Time: 0:00:03.263585
#<A = array.array('l', range(100000000))> Time: 0:00:16.728709
#<L = list(range(10**8))> Time: 0:00:03.119379
#<A = array.array('l', range(10**8))> Time: 0:00:18.042187
#<A = array.array('l', L)> Time: 0:00:07.524478
#<sum(L)> Time: 0:00:01.640671
#<np.sum(L)> Time: 0:00:20.762153