Dlaczego iteracja po małym łańcuchu jest wolniejsza niż po małej liście?

132

Bawiłem się czasem i zauważyłem, że wykonanie prostego rozumienia listy na małym łańcuchu trwało dłużej niż wykonanie tej samej operacji na liście małych ciągów pojedynczych znaków. Jakieś wyjaśnienie? To prawie 1,35 razy więcej czasu.

>>> from timeit import timeit
>>> timeit("[x for x in 'abc']")
2.0691067844831528
>>> timeit("[x for x in ['a', 'b', 'c']]")
1.5286479570345861

Co się dzieje na niższym poziomie, co to powoduje?

python performance cpython timeit python-internals Sunjay Varma
źródło

Odpowiedzi:

193

TL; DR

  • Rzeczywista różnica prędkości jest bliższa 70% (lub więcej) po usunięciu dużej części narzutu w przypadku Pythona 2.

  • Tworzenie obiektów nie jest winne. Żadna metoda nie tworzy nowego obiektu, ponieważ jednoznakowe ciągi są buforowane.

  • Różnica jest nieoczywista, ale prawdopodobnie wynika z większej liczby kontroli indeksowania ciągów, w odniesieniu do typu i poprawności sformułowania. Jest to również całkiem prawdopodobne dzięki konieczności sprawdzenia, co zwrócić.

  • Indeksowanie list jest niezwykle szybkie.

>>> python3 -m timeit '[x for x in "abc"]'
1000000 loops, best of 3: 0.388 usec per loop

>>> python3 -m timeit '[x for x in ["a", "b", "c"]]'
1000000 loops, best of 3: 0.436 usec per loop

To nie zgadza się z tym, co znalazłeś ...

Musisz więc używać Pythona 2.

>>> python2 -m timeit '[x for x in "abc"]'
1000000 loops, best of 3: 0.309 usec per loop

>>> python2 -m timeit '[x for x in ["a", "b", "c"]]'
1000000 loops, best of 3: 0.212 usec per loop

Wyjaśnijmy różnicę między wersjami. Zbadam skompilowany kod.

W przypadku Pythona 3:

import dis

def list_iterate():
    [item for item in ["a", "b", "c"]]

dis.dis(list_iterate)
#>>>   4           0 LOAD_CONST               1 (<code object <listcomp> at 0x7f4d06b118a0, file "", line 4>)
#>>>               3 LOAD_CONST               2 ('list_iterate.<locals>.<listcomp>')
#>>>               6 MAKE_FUNCTION            0
#>>>               9 LOAD_CONST               3 ('a')
#>>>              12 LOAD_CONST               4 ('b')
#>>>              15 LOAD_CONST               5 ('c')
#>>>              18 BUILD_LIST               3
#>>>              21 GET_ITER
#>>>              22 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
#>>>              25 POP_TOP
#>>>              26 LOAD_CONST               0 (None)
#>>>              29 RETURN_VALUE

def string_iterate():
    [item for item in "abc"]

dis.dis(string_iterate)
#>>>  21           0 LOAD_CONST               1 (<code object <listcomp> at 0x7f4d06b17150, file "", line 21>)
#>>>               3 LOAD_CONST               2 ('string_iterate.<locals>.<listcomp>')
#>>>               6 MAKE_FUNCTION            0
#>>>               9 LOAD_CONST               3 ('abc')
#>>>              12 GET_ITER
#>>>              13 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
#>>>              16 POP_TOP
#>>>              17 LOAD_CONST               0 (None)
#>>>              20 RETURN_VALUE

Widzisz tutaj, że wariant listy prawdopodobnie będzie wolniejszy ze względu na tworzenie listy za każdym razem.

To jest

 9 LOAD_CONST   3 ('a')
12 LOAD_CONST   4 ('b')
15 LOAD_CONST   5 ('c')
18 BUILD_LIST   3

część. Wariant string ma tylko

 9 LOAD_CONST   3 ('abc')

Możesz sprawdzić, czy to wydaje się mieć znaczenie:

def string_iterate():
    [item for item in ("a", "b", "c")]

dis.dis(string_iterate)
#>>>  35           0 LOAD_CONST               1 (<code object <listcomp> at 0x7f4d068be660, file "", line 35>)
#>>>               3 LOAD_CONST               2 ('string_iterate.<locals>.<listcomp>')
#>>>               6 MAKE_FUNCTION            0
#>>>               9 LOAD_CONST               6 (('a', 'b', 'c'))
#>>>              12 GET_ITER
#>>>              13 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
#>>>              16 POP_TOP
#>>>              17 LOAD_CONST               0 (None)
#>>>              20 RETURN_VALUE

To daje tylko

 9 LOAD_CONST               6 (('a', 'b', 'c'))

ponieważ krotki są niezmienne. Test:

>>> python3 -m timeit '[x for x in ("a", "b", "c")]'
1000000 loops, best of 3: 0.369 usec per loop

Świetnie, wracam do prędkości.

W przypadku Pythona 2:

def list_iterate():
    [item for item in ["a", "b", "c"]]

dis.dis(list_iterate)
#>>>   2           0 BUILD_LIST               0
#>>>               3 LOAD_CONST               1 ('a')
#>>>               6 LOAD_CONST               2 ('b')
#>>>               9 LOAD_CONST               3 ('c')
#>>>              12 BUILD_LIST               3
#>>>              15 GET_ITER            
#>>>         >>   16 FOR_ITER                12 (to 31)
#>>>              19 STORE_FAST               0 (item)
#>>>              22 LOAD_FAST                0 (item)
#>>>              25 LIST_APPEND              2
#>>>              28 JUMP_ABSOLUTE           16
#>>>         >>   31 POP_TOP             
#>>>              32 LOAD_CONST               0 (None)
#>>>              35 RETURN_VALUE        

def string_iterate():
    [item for item in "abc"]

dis.dis(string_iterate)
#>>>   2           0 BUILD_LIST               0
#>>>               3 LOAD_CONST               1 ('abc')
#>>>               6 GET_ITER            
#>>>         >>    7 FOR_ITER                12 (to 22)
#>>>              10 STORE_FAST               0 (item)
#>>>              13 LOAD_FAST                0 (item)
#>>>              16 LIST_APPEND              2
#>>>              19 JUMP_ABSOLUTE            7
#>>>         >>   22 POP_TOP             
#>>>              23 LOAD_CONST               0 (None)
#>>>              26 RETURN_VALUE

Dziwne jest to, że mamy ten sam budynek na liście, ale nadal jest to szybsze. Python 2 działa dziwnie szybko.

Usuńmy rozumienia i spróbujmy ponownie. Ma _ =to zapobiec optymalizacji.

>>> python3 -m timeit '_ = ["a", "b", "c"]'
10000000 loops, best of 3: 0.0707 usec per loop

>>> python3 -m timeit '_ = "abc"'
100000000 loops, best of 3: 0.0171 usec per loop

Widzimy, że inicjalizacja nie jest na tyle znacząca, aby uwzględnić różnicę między wersjami (te liczby są małe)! Możemy zatem stwierdzić, że Python 3 ma wolniejsze rozumienie. Ma to sens, ponieważ Python 3 zmienił rozumienie, aby zapewnić bezpieczniejsze określanie zakresu.

Cóż, teraz popraw test porównawczy (po prostu usuwam narzut, który nie jest iteracją). To usuwa tworzenie iterowalnych elementów poprzez wstępne przypisanie ich:

>>> python3 -m timeit -s 'iterable = "abc"'           '[x for x in iterable]'
1000000 loops, best of 3: 0.387 usec per loop

>>> python3 -m timeit -s 'iterable = ["a", "b", "c"]' '[x for x in iterable]'
1000000 loops, best of 3: 0.368 usec per loop

>>> python2 -m timeit -s 'iterable = "abc"'           '[x for x in iterable]'
1000000 loops, best of 3: 0.309 usec per loop

>>> python2 -m timeit -s 'iterable = ["a", "b", "c"]' '[x for x in iterable]'
10000000 loops, best of 3: 0.164 usec per loop

Możemy sprawdzić, czy dzwonienie iterjest narzutem:

>>> python3 -m timeit -s 'iterable = "abc"'           'iter(iterable)'
10000000 loops, best of 3: 0.099 usec per loop

>>> python3 -m timeit -s 'iterable = ["a", "b", "c"]' 'iter(iterable)'
10000000 loops, best of 3: 0.1 usec per loop

>>> python2 -m timeit -s 'iterable = "abc"'           'iter(iterable)'
10000000 loops, best of 3: 0.0913 usec per loop

>>> python2 -m timeit -s 'iterable = ["a", "b", "c"]' 'iter(iterable)'
10000000 loops, best of 3: 0.0854 usec per loop

Nie, nie jest. Różnica jest zbyt mała, szczególnie w przypadku Pythona 3.

Usuńmy więc jeszcze więcej niechcianych kosztów ogólnych ... spowolniając całość! Celem jest po prostu dłuższa iteracja, aby czas ukrywał się nad głową.

>>> python3 -m timeit -s 'import random; iterable = "".join(chr(random.randint(0, 127)) for _ in range(100000))' '[x for x in iterable]'
100 loops, best of 3: 3.12 msec per loop

>>> python3 -m timeit -s 'import random; iterable =        [chr(random.randint(0, 127)) for _ in range(100000)]' '[x for x in iterable]'
100 loops, best of 3: 2.77 msec per loop

>>> python2 -m timeit -s 'import random; iterable = "".join(chr(random.randint(0, 127)) for _ in range(100000))' '[x for x in iterable]'
100 loops, best of 3: 2.32 msec per loop

>>> python2 -m timeit -s 'import random; iterable =        [chr(random.randint(0, 127)) for _ in range(100000)]' '[x for x in iterable]'
100 loops, best of 3: 2.09 msec per loop

Właściwie to niewiele się zmieniło , ale trochę pomogło.

Więc usuń zrozumienie. To obciążenie, które nie jest częścią pytania:

>>> python3 -m timeit -s 'import random; iterable = "".join(chr(random.randint(0, 127)) for _ in range(100000))' 'for x in iterable: pass'
1000 loops, best of 3: 1.71 msec per loop

>>> python3 -m timeit -s 'import random; iterable =        [chr(random.randint(0, 127)) for _ in range(100000)]' 'for x in iterable: pass'
1000 loops, best of 3: 1.36 msec per loop

>>> python2 -m timeit -s 'import random; iterable = "".join(chr(random.randint(0, 127)) for _ in range(100000))' 'for x in iterable: pass'
1000 loops, best of 3: 1.27 msec per loop

>>> python2 -m timeit -s 'import random; iterable =        [chr(random.randint(0, 127)) for _ in range(100000)]' 'for x in iterable: pass'
1000 loops, best of 3: 935 usec per loop

Tak już lepiej! Możemy jeszcze trochę przyspieszyć, używając dequedo iteracji. Zasadniczo to samo, ale jest szybsze :

>>> python3 -m timeit -s 'import random; from collections import deque; iterable = "".join(chr(random.randint(0, 127)) for _ in range(100000))' 'deque(iterable, maxlen=0)'
1000 loops, best of 3: 777 usec per loop

>>> python3 -m timeit -s 'import random; from collections import deque; iterable =        [chr(random.randint(0, 127)) for _ in range(100000)]' 'deque(iterable, maxlen=0)'
1000 loops, best of 3: 405 usec per loop

>>> python2 -m timeit -s 'import random; from collections import deque; iterable = "".join(chr(random.randint(0, 127)) for _ in range(100000))' 'deque(iterable, maxlen=0)'
1000 loops, best of 3: 805 usec per loop

>>> python2 -m timeit -s 'import random; from collections import deque; iterable =        [chr(random.randint(0, 127)) for _ in range(100000)]' 'deque(iterable, maxlen=0)'
1000 loops, best of 3: 438 usec per loop

Imponuje mi to, że Unicode konkuruje z bajtami. Możemy to wyraźnie sprawdzić, próbując bytesi unicodejednocześnie:

  • bytes

    >>> python3 -m timeit -s 'import random; from collections import deque; iterable = b"".join(chr(random.randint(0, 127)).encode("ascii") for _ in range(100000))' 'deque(iterable, maxlen=0)'                                                                    :(
1000 loops, best of 3: 571 usec per loop

>>> python3 -m timeit -s 'import random; from collections import deque; iterable =         [chr(random.randint(0, 127)).encode("ascii") for _ in range(100000)]' 'deque(iterable, maxlen=0)'
1000 loops, best of 3: 394 usec per loop

    >>> python2 -m timeit -s 'import random; from collections import deque; iterable = b"".join(chr(random.randint(0, 127))                 for _ in range(100000))' 'deque(iterable, maxlen=0)'
1000 loops, best of 3: 757 usec per loop

>>> python2 -m timeit -s 'import random; from collections import deque; iterable =         [chr(random.randint(0, 127))                 for _ in range(100000)]' 'deque(iterable, maxlen=0)'
1000 loops, best of 3: 438 usec per loop

    Tutaj widać, że Python 3 jest faktycznie szybszy niż Python 2.

  • unicode

    >>> python3 -m timeit -s 'import random; from collections import deque; iterable = u"".join(   chr(random.randint(0, 127)) for _ in range(100000))' 'deque(iterable, maxlen=0)'
1000 loops, best of 3: 800 usec per loop

>>> python3 -m timeit -s 'import random; from collections import deque; iterable =         [   chr(random.randint(0, 127)) for _ in range(100000)]' 'deque(iterable, maxlen=0)'
1000 loops, best of 3: 394 usec per loop

    >>> python2 -m timeit -s 'import random; from collections import deque; iterable = u"".join(unichr(random.randint(0, 127)) for _ in range(100000))' 'deque(iterable, maxlen=0)'
1000 loops, best of 3: 1.07 msec per loop

>>> python2 -m timeit -s 'import random; from collections import deque; iterable =         [unichr(random.randint(0, 127)) for _ in range(100000)]' 'deque(iterable, maxlen=0)'
1000 loops, best of 3: 469 usec per loop

    Ponownie, Python 3 jest szybszy, chociaż należy się tego spodziewać ( strpoświęcono mu wiele uwagi w Pythonie 3).

W rzeczywistości ta unicode- bytesróżnica jest bardzo mała, co robi wrażenie.

Przeanalizujmy więc ten jeden przypadek, widząc, że jest to dla mnie szybkie i wygodne:

>>> python3 -m timeit -s 'import random; from collections import deque; iterable = "".join(chr(random.randint(0, 127)) for _ in range(100000))' 'deque(iterable, maxlen=0)'
1000 loops, best of 3: 777 usec per loop

>>> python3 -m timeit -s 'import random; from collections import deque; iterable =        [chr(random.randint(0, 127)) for _ in range(100000)]' 'deque(iterable, maxlen=0)'
1000 loops, best of 3: 405 usec per loop

Możemy faktycznie wykluczyć odpowiedź Tima Petera, na którą głosował 10 razy!

>>> foo = iterable[123]
>>> iterable[36] is foo
True

To nie są nowe obiekty!

Ale warto wspomnieć: koszty indeksowania . Różnica będzie prawdopodobnie dotyczyła indeksowania, więc usuń iterację i po prostu zindeksuj:

>>> python3 -m timeit -s 'import random; iterable = "".join(chr(random.randint(0, 127)) for _ in range(100000))' 'iterable[123]'
10000000 loops, best of 3: 0.0397 usec per loop

>>> python3 -m timeit -s 'import random; iterable =        [chr(random.randint(0, 127)) for _ in range(100000)]' 'iterable[123]'
10000000 loops, best of 3: 0.0374 usec per loop

Różnica wydaje się niewielka, ale przynajmniej połowa kosztów to koszty ogólne:

>>> python3 -m timeit -s 'import random; iterable =        [chr(random.randint(0, 127)) for _ in range(100000)]' 'iterable; 123'
100000000 loops, best of 3: 0.0173 usec per loop

więc różnica prędkości jest wystarczająca, aby zdecydować o winie. Myślę.

Dlaczego więc indeksowanie listy jest o wiele szybsze?

Cóż, wrócę do ciebie w tej sprawie, ale przypuszczam, że to zależy od sprawdzenia wewnętrznych ciągów (lub znaków w pamięci podręcznej, jeśli jest to oddzielny mechanizm). Będzie to mniej szybkie niż optymalne. Ale pójdę sprawdzić źródło (chociaż nie czuję się komfortowo w C ...) :).

Oto źródło:

static PyObject *
unicode_getitem(PyObject *self, Py_ssize_t index)
{
    void *data;
    enum PyUnicode_Kind kind;
    Py_UCS4 ch;
    PyObject *res;

    if (!PyUnicode_Check(self) || PyUnicode_READY(self) == -1) {
        PyErr_BadArgument();
        return NULL;
    }
    if (index < 0 || index >= PyUnicode_GET_LENGTH(self)) {
        PyErr_SetString(PyExc_IndexError, "string index out of range");
        return NULL;
    }
    kind = PyUnicode_KIND(self);
    data = PyUnicode_DATA(self);
    ch = PyUnicode_READ(kind, data, index);
    if (ch < 256)
        return get_latin1_char(ch);

    res = PyUnicode_New(1, ch);
    if (res == NULL)
        return NULL;
    kind = PyUnicode_KIND(res);
    data = PyUnicode_DATA(res);
    PyUnicode_WRITE(kind, data, 0, ch);
    assert(_PyUnicode_CheckConsistency(res, 1));
    return res;
}

Idąc z góry, będziemy mieć kilka czeków. Te są nudne. Następnie kilka zleceń, które również powinny być nudne. Pierwsza ciekawa linia to

ch = PyUnicode_READ(kind, data, index);

ale mamy nadzieję, że to szybko, ponieważ czytamy z ciągłej tablicy C, indeksując ją. Wynik chbędzie mniejszy niż 256, więc zwrócimy znak z pamięci podręcznej w formacie get_latin1_char(ch).

Więc będziemy działać (porzucimy pierwsze testy)

kind = PyUnicode_KIND(self);
data = PyUnicode_DATA(self);
ch = PyUnicode_READ(kind, data, index);
return get_latin1_char(ch);

Gdzie

#define PyUnicode_KIND(op) \
    (assert(PyUnicode_Check(op)), \
     assert(PyUnicode_IS_READY(op)),            \
     ((PyASCIIObject *)(op))->state.kind)

(co jest nudne, ponieważ potwierdzenia są ignorowane podczas debugowania [więc mogę sprawdzić, czy są szybkie] i ((PyASCIIObject *)(op))->state.kind)jest (myślę) pośrednim i rzutowaniem na poziomie C);

#define PyUnicode_DATA(op) \
    (assert(PyUnicode_Check(op)), \
     PyUnicode_IS_COMPACT(op) ? _PyUnicode_COMPACT_DATA(op) :   \
     _PyUnicode_NONCOMPACT_DATA(op))

(co również jest nudne z podobnych powodów, zakładając, że wszystkie makra ( Something_CAPITALIZED) są szybkie),

#define PyUnicode_READ(kind, data, index) \
    ((Py_UCS4) \
    ((kind) == PyUnicode_1BYTE_KIND ? \
        ((const Py_UCS1 *)(data))[(index)] : \
        ((kind) == PyUnicode_2BYTE_KIND ? \
            ((const Py_UCS2 *)(data))[(index)] : \
            ((const Py_UCS4 *)(data))[(index)] \
        ) \
    ))

(który obejmuje indeksy, ale tak naprawdę wcale nie jest wolny) i

static PyObject*
get_latin1_char(unsigned char ch)
{
    PyObject *unicode = unicode_latin1[ch];
    if (!unicode) {
        unicode = PyUnicode_New(1, ch);
        if (!unicode)
            return NULL;
        PyUnicode_1BYTE_DATA(unicode)[0] = ch;
        assert(_PyUnicode_CheckConsistency(unicode, 1));
        unicode_latin1[ch] = unicode;
    }
    Py_INCREF(unicode);
    return unicode;
}

Co potwierdza moje podejrzenie, że:

  • To jest buforowane:

    PyObject *unicode = unicode_latin1[ch];

  • To powinno być szybkie. Nie if (!unicode)jest uruchamiany, więc w tym przypadku jest dosłownie odpowiednikiem

    PyObject *unicode = unicode_latin1[ch];
Py_INCREF(unicode);
return unicode;

Szczerze mówiąc, po przetestowaniu asserts są szybkie (wyłączając je [myślę, że to działa na potwierdzeniach na poziomie C ...]), jedynymi wiarygodnie wolnymi częściami są:

PyUnicode_IS_COMPACT(op)
_PyUnicode_COMPACT_DATA(op)
_PyUnicode_NONCOMPACT_DATA(op)

Które są:

#define PyUnicode_IS_COMPACT(op) \
    (((PyASCIIObject*)(op))->state.compact)

(szybko, jak poprzednio),

#define _PyUnicode_COMPACT_DATA(op)                     \
    (PyUnicode_IS_ASCII(op) ?                   \
     ((void*)((PyASCIIObject*)(op) + 1)) :              \
     ((void*)((PyCompactUnicodeObject*)(op) + 1)))

(szybko, jeśli makro IS_ASCIIjest szybkie) i

#define _PyUnicode_NONCOMPACT_DATA(op)                  \
    (assert(((PyUnicodeObject*)(op))->data.any),        \
     ((((PyUnicodeObject *)(op))->data.any)))

(również szybki, ponieważ jest to asercja plus pośrednia i obsada).

Więc jesteśmy na dole (królicza nora), aby:

PyUnicode_IS_ASCII

który jest

#define PyUnicode_IS_ASCII(op)                   \
    (assert(PyUnicode_Check(op)),                \
     assert(PyUnicode_IS_READY(op)),             \
     ((PyASCIIObject*)op)->state.ascii)

Hmm ... to też wydaje się szybkie ...

Dobrze, ale porównajmy to z PyList_GetItem. (Tak, dziękuję Timowi Petersowi, że dał mi więcej pracy: P.)

PyObject *
PyList_GetItem(PyObject *op, Py_ssize_t i)
{
    if (!PyList_Check(op)) {
        PyErr_BadInternalCall();
        return NULL;
    }
    if (i < 0 || i >= Py_SIZE(op)) {
        if (indexerr == NULL) {
            indexerr = PyUnicode_FromString(
                "list index out of range");
            if (indexerr == NULL)
                return NULL;
        }
        PyErr_SetObject(PyExc_IndexError, indexerr);
        return NULL;
    }
    return ((PyListObject *)op) -> ob_item[i];
}

Widzimy, że w przypadkach bez błędów to po prostu zadziała:

PyList_Check(op)
Py_SIZE(op)
((PyListObject *)op) -> ob_item[i]

Gdzie PyList_Checkjest

#define PyList_Check(op) \
     PyType_FastSubclass(Py_TYPE(op), Py_TPFLAGS_LIST_SUBCLASS)

( TABS! TABS !!! ) ( issue21587 ) To zostało naprawione i scalone w 5 minut . Jak ... tak. Cholera. Zawstydzili Skeeta.

#define Py_SIZE(ob)             (((PyVarObject*)(ob))->ob_size)

#define PyType_FastSubclass(t,f)  PyType_HasFeature(t,f)

#ifdef Py_LIMITED_API
#define PyType_HasFeature(t,f)  ((PyType_GetFlags(t) & (f)) != 0)
#else
#define PyType_HasFeature(t,f)  (((t)->tp_flags & (f)) != 0)
#endif

Zwykle jest to naprawdę trywialne (dwie pośrednie i kilka logicznych kontroli), chyba że Py_LIMITED_APIjest włączone, w takim przypadku ... ???

Następnie jest indeksowanie i rzutowanie ( ((PyListObject *)op) -> ob_item[i]) i gotowe.

Tak więc jest zdecydowanie mniej sprawdzeń list, a niewielkie różnice prędkości z pewnością sugerują, że może to być istotne.

Myślę, że ogólnie rzecz biorąc, jest po prostu więcej sprawdzania typu i pośrednictwa (->)dla Unicode. Wygląda na to, że brakuje mi punktu, ale co ?

Veedrac
źródło
17
Przedstawiasz kod jako zrozumiały; nawet przedstawiasz fragmenty jako wnioski. Niestety dla mnie tak naprawdę nie mogę tego śledzić. Nie mówię, że twoje podejście do ustalenia, co jest nie tak, nie jest solidne, ale byłoby miło, gdyby było łatwiejsze do naśladowania.
PascalVKooten
2
Próbowałem to ulepszyć, ale nie jestem pewien, jak to wyjaśnić. Zauważ, że nie piszę C, więc jest to analiza kodu na wysokim poziomie i ważne są tylko ogólne pojęcia.
Veedrac
@Nit dodałem. Powiedz mi, jeśli czujesz, że czegoś brakuje. Niestety podkreśla również, że tak naprawdę nie znam odpowiedzi (* sapnięcie *).
Veedrac
3
Podam to jeszcze jeden dzień, zanim przyjmuję twoją odpowiedź (chciałbym zobaczyć coś bardziej konkretnego), ale dziękuję za bardzo interesującą i dobrze zbadaną odpowiedź.
Sunjay Varma
4
Zwróć uwagę, że strzelasz do ruchomego celu ;-) Ta implementacja różni się nie tylko między Pythonem 2 i Pythonem 3, ale także między różnymi wydaniami. Na przykład w obecnym pniu programistycznym get_latin1_char()sztuczka nie istnieje już w unicode_getitem(), ale na niższym poziomie unicode_char. Jest więc teraz inny poziom wywołania funkcji - lub nie (w zależności od używanego kompilatora i flag optymalizacji). Na tym poziomie szczegółowości po prostu nie ma wiarygodnych odpowiedzi ;-)
Tim Peters
31

Podczas iteracji po większości obiektów kontenerów (list, krotek, dykt, ...) iterator dostarcza obiekty w kontenerze.

Ale kiedy iterujesz po ciągu, dla każdego dostarczonego znaku musi zostać utworzony nowy obiekt - łańcuch nie jest „kontenerem” w tym samym sensie, że lista jest kontenerem. Poszczególne znaki w ciągu nie istnieją jako odrębne obiekty, zanim iteracja utworzy te obiekty.

Tim Peters
źródło
3
Właściwie nie sądzę, żeby to była prawda. Możesz to sprawdzić is. To brzmi dobrze, ale ja naprawdę nie sądzę, że to może być.
Veedrac
Spójrz na odpowiedź @Veedrac.
Christian
3
stringobject.cpokazuje, że __getitem__dla łańcuchów po prostu pobiera wynik z tabeli przechowywanych 1-znakowych ciągów, więc koszty alokacji dla nich są ponoszone tylko raz.
user2357112 obsługuje Monikę
10
@ user2357112, tak, dla zwykłych ciągów znaków w Pythonie 2 to kluczowy punkt. W Pythonie 3 wszystkie ciągi znaków są „oficjalnie” Unicode i zawiera o wiele więcej szczegółów (zobacz odpowiedź Veedrac). Na przykład w Pythonie 3, po s = chr(256), s is chr(256)powraca False- znając typ nie wystarcza, bo kopce szczególnych przypadkach istnieje pod kołdrą Wyzwalanie Dane wartości .
Tim Peters
1

Tworzenie iteratora dla ciągu może wiązać się z dodatkowymi kosztami. Podczas gdy tablica zawiera już iterator po utworzeniu instancji.

EDYTOWAĆ:

>>> timeit("[x for x in ['a','b','c']]")
0.3818681240081787
>>> timeit("[x for x in 'abc']")
0.3732869625091553

Zostało to uruchomione przy użyciu wersji 2.7, ale na moim Mac Book Pro i7. Może to być wynikiem różnicy w konfiguracji systemu.

Robert Chumley
źródło
Nawet używając prostych iteratorów, ciąg jest nadal znacznie wolniejszy. timeit ("[x for x in it]", "it = iter ('abc')") = 0,34543599384033535; timeit ("[x for x in it]", "it = iter (list ('abc'))") = 0.2791691380446508
Sunjay Varma