Dlaczego [] jest szybszy niż list ()?

Niedawno w porównaniu z przetwarzaniem prędkości []i list()i była zaskoczona, że []pracuje więcej niż trzy razy szybciej niż list(). Pobiegłem ten sam test z {}i dict()a wyniki były praktycznie identyczne: []i {}zarówno trwała około 0.128sec / milion cykli, podczas list()i dict()trwało około 0.428sec / milion cykli każdy.

Dlaczego to? Czy []i {}(a pewnie ()i ''też) natychmiast przechodzić z powrotem kopie jakiegoś pustego stanie dosłownym, podczas gdy ich odpowiedniki wyraźnie nazwie ( list(), dict(), tuple(), str()) w pełni go o stworzenie obiektu, czy one rzeczywiście mają elementy?

Nie mam pojęcia, jak różnią się te dwie metody, ale chciałbym się dowiedzieć. Nie mogłem znaleźć odpowiedzi w dokumentacji lub na SO, a wyszukiwanie pustych nawiasów okazało się bardziej problematyczne, niż się spodziewałem.

Otrzymałem wyniki pomiaru, dzwoniąc timeit.timeit("[]")i timeit.timeit("list()"), i, timeit.timeit("{}")i timeit.timeit("dict()"), porównując odpowiednio listy i słowniki. Korzystam z Python 2.7.9.

Niedawno odkryłem „ Dlaczego prawda jest wolniejsza niż 1? ”, Która porównuje wydajność if Truedo if 1i wydaje się, że dotyczy podobnego scenariusza dosłownie kontra globalnie; być może warto też to rozważyć.

Ponieważ []i {}są dosłowną składnią . Python może utworzyć kod bajtowy, aby utworzyć obiekty listy lub słownika:

>>> import dis
>>> dis.dis(compile('[]', '', 'eval'))
  1           0 BUILD_LIST               0
              3 RETURN_VALUE        
>>> dis.dis(compile('{}', '', 'eval'))
  1           0 BUILD_MAP                0
              3 RETURN_VALUE        

list()i dict()są osobnymi obiektami. Ich nazwy muszą zostać rozwiązane, stos musi być zaangażowany w popychanie argumentów, ramka musi być zapisana do późniejszego pobrania i musi zostać wykonane wywołanie. To wszystko zajmuje więcej czasu.

W przypadku pustego przypadku oznacza to, że masz co najmniej a LOAD_NAME(który musi przeszukiwać globalną przestrzeń nazw oraz __builtin__moduł ), a następnie a CALL_FUNCTION, który musi zachować bieżącą ramkę:

>>> dis.dis(compile('list()', '', 'eval'))
  1           0 LOAD_NAME                0 (list)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        
>>> dis.dis(compile('dict()', '', 'eval'))
  1           0 LOAD_NAME                0 (dict)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        

Możesz sprawdzić czas nazwy osobno timeit:

>>> import timeit
>>> timeit.timeit('list', number=10**7)
0.30749011039733887
>>> timeit.timeit('dict', number=10**7)
0.4215109348297119

Różnica czasu występuje prawdopodobnie w wyniku kolizji słownika. Odejmij te czasy od czasów wywołania tych obiektów i porównaj wynik z czasami użycia literałów:

>>> timeit.timeit('[]', number=10**7)
0.30478692054748535
>>> timeit.timeit('{}', number=10**7)
0.31482696533203125
>>> timeit.timeit('list()', number=10**7)
0.9991960525512695
>>> timeit.timeit('dict()', number=10**7)
1.0200958251953125

Zatem konieczność wywołania obiektu zajmuje dodatkowe 1.00 - 0.31 - 0.30 == 0.39sekundy na 10 milionów wywołań.

Możesz uniknąć globalnego kosztu wyszukiwania, aliasując nazwy globalne jako miejscowe (przy użyciu timeitkonfiguracji wszystko, co wiążesz z nazwą, jest lokalne):

>>> timeit.timeit('_list', '_list = list', number=10**7)
0.1866450309753418
>>> timeit.timeit('_dict', '_dict = dict', number=10**7)
0.19016098976135254
>>> timeit.timeit('_list()', '_list = list', number=10**7)
0.841480016708374
>>> timeit.timeit('_dict()', '_dict = dict', number=10**7)
0.7233691215515137

ale nigdy nie pokonasz tego CALL_FUNCTIONkosztu.

list()wymaga globalnego wyszukiwania i wywołania funkcji, ale []kompiluje się do pojedynczej instrukcji. Widzieć:

Python 2.7.3
>>> import dis
>>> print dis.dis(lambda: list())
  1           0 LOAD_GLOBAL              0 (list)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        
None
>>> print dis.dis(lambda: [])
  1           0 BUILD_LIST               0
              3 RETURN_VALUE        
None

Ponieważ listjest to funkcja do konwersji powiedzmy ciąg na obiekt listy, podczas gdy []jest używana do tworzenia listy poza batem. Wypróbuj to (może być dla ciebie bardziej sensowne):

x = "wham bam"
a = list(x)
>>> a
["w", "h", "a", "m", ...]

Podczas

y = ["wham bam"]
>>> y
["wham bam"]

Daje ci rzeczywistą listę zawierającą wszystko, co w niej umieścisz.

Odpowiedzi tutaj są świetne, do rzeczy i w pełni obejmują to pytanie. Zainteresowanych usunę kolejny krok w dół od kodu bajtowego. Korzystam z najnowszego repozytorium CPython; starsze wersje zachowują się pod tym względem podobnie, ale mogą występować niewielkie zmiany.

Oto podział wykonania dla każdego z nich BUILD_LISTdla []i CALL_FUNCTIONdla list().

BUILD_LISTInstrukcja:

Powinieneś po prostu zobaczyć horror:

PyObject *list =  PyList_New(oparg);
if (list == NULL)
    goto error;
while (--oparg >= 0) {
    PyObject *item = POP();
    PyList_SET_ITEM(list, oparg, item);
}
PUSH(list);
DISPATCH();

Okropnie zawiłe, wiem. Oto jakie to proste:

• Utwórz nową listę za pomocą PyList_New(przydziela to głównie pamięć dla nowego obiektu listy), opargsygnalizując liczbę argumentów na stosie. Prosto do celu.
• Sprawdź, czy nic nie poszło nie tak if (list==NULL).
• Dodaj dowolne argumenty (w naszym przypadku nie jest to wykonywane) znajdujące się na stosie za pomocą PyList_SET_ITEM(makra).

Nic dziwnego, że jest szybki! Jest dostosowany do tworzenia nowych list, nic więcej :-)

CALL_FUNCTIONInstrukcja:

Oto pierwsza rzecz, którą zobaczysz, gdy zajrzysz do obsługi kodu CALL_FUNCTION:

PyObject **sp, *res;
sp = stack_pointer;
res = call_function(&sp, oparg, NULL);
stack_pointer = sp;
PUSH(res);
if (res == NULL) {
    goto error;
}
DISPATCH();

Wygląda całkiem nieszkodliwie, prawda? Cóż, nie, niestety nie, call_functionnie jest prostym facetem, który wywoła funkcję natychmiast, nie może. Zamiast tego pobiera obiekt ze stosu, pobiera wszystkie argumenty stosu, a następnie przełącza się w zależności od typu obiektu; to jest:

• PyCFunction_Type? Nie, to jest list, listnie jest typuPyCFunction
• PyMethodType? Nie, patrz poprzedni.
• PyFunctionType? Nie, patrz poprzedni.

Jesteśmy wywołanie listtypu, argument przekazany do call_functionjest PyList_Type. CPython musi teraz wywołać funkcję ogólną, aby obsłużyć dowolne nazwane obiekty, które można wywoływać _PyObject_FastCallKeywords, i więcej wywołań funkcji.

Ta funkcja ponownie sprawdza niektóre typy funkcji (których nie rozumiem dlaczego), a następnie, po utworzeniu słownika dla kwargs, jeśli jest to wymagane , przechodzi do wywołania _PyObject_FastCallDict.

_PyObject_FastCallDictw końcu nas gdzieś zabiera! Po wykonaniu nawet więcej kontroli to chwyta tp_callgniazdo przeprowadzonątype z typemy przekazany, to znaczy, że chwyta type.tp_call. Następnie tworzy krotkę z argumentów przekazanych za pomocą _PyStack_AsTuplei wreszcie można wreszcie zadzwonić !

tp_call, który pasuje type.__call__przejmuje i ostatecznie tworzy obiekt listy. Wywołuje listy, __new__które odpowiadają PyType_GenericNewi przydziela mu pamięć za pomocą PyType_GenericAlloc: W rzeczywistości jest to część, w której PyList_Newwreszcie się dogania . Wszystkie poprzednie są niezbędne do obsługi obiektów w sposób ogólny.

Na koniec type_callwywołuje list.__init__i inicjuje listę dowolnymi dostępnymi argumentami, a następnie wracamy do poprzedniej wersji. :-)

Na koniec pamiętajcie LOAD_NAME, że to inny facet, który się tutaj przyczynia.

Łatwo zauważyć, że gdy mamy do czynienia z naszymi danymi wejściowymi, Python zazwyczaj musi przeskakiwać przez obręcze, aby faktycznie znaleźć odpowiednią Cfunkcję do wykonania zadania. Nie ma na to ochoty natychmiastowego nazywania go, ponieważ jest dynamiczny, ktoś może maskować list( a chłopiec robi to wiele osób ) i trzeba obrać inną ścieżkę.

Tu list()wiele traci: Eksplorujący Python musi zrobić, aby dowiedzieć się, co do cholery powinien zrobić.

Z drugiej strony, dosłowna składnia oznacza dokładnie jedno; nie można go zmienić i zawsze zachowuje się w określony sposób.

^{Przypis: Wszystkie nazwy funkcji mogą ulec zmianie z jednej wersji na drugą. Chodzi o punkt, który najprawdopodobniej pozostanie w przyszłych wersjach, to dynamiczne wyszukiwanie spowalnia działanie.}

Dlaczego jest []szybszy niż list()?

Największym powodem jest to, że Python traktuje list()jak funkcję zdefiniowaną przez użytkownika, co oznacza, że ​​możesz ją przechwycić, aliasingując coś innego listi zrobić coś innego (np. Użyć własnej listy w sklasyfikowanej klasie lub być może deque).

Natychmiast tworzy nowe wystąpienie wbudowanej listy za pomocą [].

Moje wyjaśnienie ma na celu dać ci do tego intuicję.

Wyjaśnienie

[] jest powszechnie znany jako dosłowna składnia.

W gramatyce jest to określane jako „wyświetlanie listy”. Z dokumentów :

Wyświetlanie listy jest prawdopodobnie pustą serią wyrażeń zawartych w nawiasach kwadratowych:

list_display ::=  "[" [starred_list | comprehension] "]"

Wyświetlanie listy daje nowy obiekt listy, a treść jest określana albo przez listę wyrażeń, albo przez zrozumienie. Gdy podana jest lista wyrażeń oddzielona przecinkami, jej elementy są oceniane od lewej do prawej i umieszczane w obiekcie listy w tej kolejności. Kiedy dostarczane jest zrozumienie, lista jest tworzona z elementów wynikających ze zrozumienia.

Krótko mówiąc, oznacza to, że listtworzony jest wbudowany obiekt typu .

Nie można tego obejść - co oznacza, że ​​Python może to zrobić tak szybko, jak to możliwe.

Z drugiej strony list()można przechwycić tworzenie wbudowanego programu listza pomocą wbudowanego konstruktora listy.

Załóżmy na przykład, że chcemy, aby nasze listy były tworzone głośno:

class List(list):
    def __init__(self, iterable=None):
        if iterable is None:
            super().__init__()
        else:
            super().__init__(iterable)
        print('List initialized.')

Możemy wtedy przechwycić nazwę listw zasięgu globalnym na poziomie modułu, a następnie, gdy tworzymy list, tworzymy naszą listę podtypów:

>>> list = List
>>> a_list = list()
List initialized.
>>> type(a_list)
<class '__main__.List'>

Podobnie możemy usunąć go z globalnej przestrzeni nazw

del list

i umieść go we wbudowanej przestrzeni nazw:

import builtins
builtins.list = List

I teraz:

>>> list_0 = list()
List initialized.
>>> type(list_0)
<class '__main__.List'>

I zauważ, że wyświetlenie listy tworzy listę bezwarunkowo:

>>> list_1 = []
>>> type(list_1)
<class 'list'>

Prawdopodobnie robimy to tylko tymczasowo, więc Listcofnijmy nasze zmiany - najpierw usuń nowy obiekt z wbudowanych:

>>> del builtins.list
>>> builtins.list
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: module 'builtins' has no attribute 'list'
>>> list()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'list' is not defined

Och, nie, zgubiliśmy oryginał.

Nie martw się, wciąż możemy uzyskać list- to rodzaj literału listy:

>>> builtins.list = type([])
>>> list()
[]

Więc...

Dlaczego jest []szybszy niż list()?

Jak widzieliśmy - możemy nadpisać list- ale nie możemy przechwycić stworzenia literalnego typu. Kiedy korzystamy, listmusimy wyszukiwać, aby sprawdzić, czy coś tam jest.

Następnie musimy zadzwonić do każdej wywoływanej przez nas funkcji. Z gramatyki:

Wywołanie wywołuje wywoływalny obiekt (np. Funkcję) z możliwie pustą serią argumentów:

call                 ::=  primary "(" [argument_list [","] | comprehension] ")"

Widzimy, że robi to samo dla dowolnej nazwy, nie tylko listy:

>>> import dis
>>> dis.dis('list()')
  1           0 LOAD_NAME                0 (list)
              2 CALL_FUNCTION            0
              4 RETURN_VALUE
>>> dis.dis('doesnotexist()')
  1           0 LOAD_NAME                0 (doesnotexist)
              2 CALL_FUNCTION            0
              4 RETURN_VALUE

Ponieważ []na poziomie kodu bajtowego języka Python nie ma wywołania funkcji:

>>> dis.dis('[]')
  1           0 BUILD_LIST               0
              2 RETURN_VALUE

Po prostu idzie prosto do budowania listy bez wyszukiwania lub wywołań na poziomie kodu bajtowego.

Wniosek

Wykazaliśmy, że listmożna przechwycić kod użytkownika za pomocą reguł określania zakresu, który list()wyszukuje wywołanie, a następnie je wywołuje.

Natomiast []wyświetla listę lub dosłownie, dzięki czemu unika się wyszukiwania nazwy i wywoływania funkcji.