Warum ist es langsamer, über eine kleine Zeichenfolge zu iterieren als über eine kleine Liste?

132

Ich spielte mit Timeit herum und bemerkte, dass das einfache Verstehen einer Liste über eine kleine Zeichenfolge länger dauerte als das Ausführen derselben Operation für eine Liste kleiner einzelner Zeichenfolgen. Irgendeine Erklärung? Es ist fast 1,35-mal so viel Zeit.

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

Was passiert auf einer niedrigeren Ebene, die dies verursacht?

python performance cpython timeit python-internals Sunjay Varma
quelle

Antworten:

193

TL; DR

  • Der tatsächliche Geschwindigkeitsunterschied liegt bei Python 2 näher bei 70% (oder mehr), wenn ein Großteil des Overheads entfernt wird.

  • Die Objekterstellung ist nicht schuld. Keine der beiden Methoden erstellt ein neues Objekt, da Zeichenfolgen mit einem Zeichen zwischengespeichert werden.

  • Der Unterschied ist nicht offensichtlich, wird jedoch wahrscheinlich durch eine größere Anzahl von Überprüfungen der Zeichenfolgenindizierung hinsichtlich des Typs und der Formgebung verursacht. Es ist auch sehr wahrscheinlich, dass überprüft werden muss, was zurückgegeben werden soll.

  • Die Listenindizierung ist bemerkenswert schnell.

>>> 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

Dies stimmt nicht mit dem überein, was Sie gefunden haben ...

Sie müssen also Python 2 verwenden.

>>> 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

Lassen Sie uns den Unterschied zwischen den Versionen erklären. Ich werde den kompilierten Code untersuchen.

Für Python 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

Sie sehen hier, dass die Listenvariante wahrscheinlich langsamer ist, da die Liste jedes Mal erstellt wird.

Dies ist das

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

Teil. Die String-Variante hat nur

 9 LOAD_CONST   3 ('abc')

Sie können überprüfen, ob dies einen Unterschied zu machen scheint:

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

Dies erzeugt nur

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

als Tupel sind unveränderlich. Prüfung:

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

Großartig, wieder auf dem neuesten Stand.

Für Python 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

Das Seltsame ist, dass wir das gleiche haben Gebäude der Liste haben, aber es ist immer noch schneller. Python 2 agiert seltsam schnell.

Lassen Sie uns das Verständnis entfernen und die Zeit neu festlegen. Dies _ =soll verhindern, dass es optimiert wird.

>>> 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

Wir können sehen, dass die Initialisierung nicht signifikant genug ist, um den Unterschied zwischen den Versionen zu berücksichtigen (diese Zahlen sind klein)! Wir können daraus schließen, dass Python 3 ein langsameres Verständnis hat. Dies ist sinnvoll, da Python 3 das Verständnis geändert hat, um ein sichereres Scoping zu gewährleisten.

Nun, verbessern Sie jetzt den Benchmark (ich entferne nur Overhead, der keine Iteration ist). Dadurch wird das Gebäude des Iterables entfernt, indem es vorab zugewiesen wird:

>>> 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

Wir können überprüfen, ob der Anruf iterder Overhead ist:

>>> 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

Nein, ist es nicht. Der Unterschied ist zu gering, insbesondere für Python 3.

Entfernen wir also noch mehr unerwünschte Gemeinkosten ... indem wir das Ganze langsamer machen! Das Ziel ist nur eine längere Iteration, damit sich die Zeit über dem Kopf verbirgt.

>>> 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

Das hat sich eigentlich nicht viel geändert , aber es hat ein wenig geholfen.

Entfernen Sie also das Verständnis. Es ist Overhead, der nicht Teil der Frage ist:

>>> 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

Das ist eher so! Wir können noch etwas schneller werden, indem wir dequeiterieren. Es ist im Grunde das gleiche, aber es ist schneller :

>>> 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

Was mich beeindruckt ist, dass Unicode mit Bytestrings konkurriert. Wir können dies explizit überprüfen, indem wir versuchen bytesund unicodein beiden:

  • 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

    Hier sehen Sie Python 3 tatsächlich schneller als 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

    Auch hier ist Python 3 schneller, obwohl dies zu erwarten ist ( strhat in Python 3 viel Aufmerksamkeit erhalten).

In der Tat ist dies unicode- bytesist der Unterschied sehr klein, was beeindruckend ist.

Lassen Sie uns diesen einen Fall analysieren, da er für mich schnell und bequem ist:

>>> 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

Wir können Tim Peters 10-malige Antwort tatsächlich ausschließen!

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

Dies sind keine neuen Objekte!

Erwähnenswert ist jedoch: Indexierung der Kosten . Der Unterschied liegt wahrscheinlich in der Indizierung. Entfernen Sie also die Iteration und indizieren Sie einfach:

>>> 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

Der Unterschied scheint gering zu sein, aber mindestens die Hälfte der Kosten entfällt auf Gemeinkosten:

>>> 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

Der Geschwindigkeitsunterschied reicht also aus, um die Schuld dafür zu geben. Meiner Ansicht nach.

Warum ist die Indizierung einer Liste so viel schneller?

Nun, ich werde darauf zurückkommen, aber ich vermute, das liegt an der Überprüfung auf internierte Zeichenfolgen (oder zwischengespeicherte Zeichen, wenn es sich um einen separaten Mechanismus handelt). Dies ist weniger schnell als optimal. Aber ich werde die Quelle überprüfen (obwohl ich mich in C nicht wohl fühle ...) :).

Also hier ist die Quelle:

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;
}

Wenn wir von oben gehen, haben wir ein paar Schecks. Das ist langweilig. Dann einige Aufgaben, die auch langweilig sein sollten. Die erste interessante Zeile ist

ch = PyUnicode_READ(kind, data, index);

Wir hoffen jedoch, dass dies schnell geht, da wir aus einem zusammenhängenden C-Array lesen, indem wir es indizieren. Das Ergebnis ist chkleiner als 256, daher geben wir das zwischengespeicherte Zeichen zurückget_latin1_char(ch) .

Also rennen wir los (lassen die ersten Schecks fallen)

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

Wo

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

(was langweilig ist, weil Asserts beim Debuggen ignoriert werden [damit ich überprüfen kann, ob sie schnell sind] und ((PyASCIIObject *)(op))->state.kind)(glaube ich) eine Indirektion und eine Besetzung auf C-Ebene sind);

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

(was aus ähnlichen Gründen auch langweilig ist, vorausgesetzt, die Makros ( Something_CAPITALIZED) sind alle schnell),

#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)] \
        ) \
    ))

(was Indizes beinhaltet, aber wirklich überhaupt nicht langsam ist) und

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;
}

Was meinen Verdacht bestätigt, dass:

  • Dies wird zwischengespeichert:

    PyObject *unicode = unicode_latin1[ch];

  • Das sollte schnell gehen. Das if (!unicode)wird nicht ausgeführt, daher ist es in diesem Fall buchstäblich gleichbedeutend mit

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

Ehrlich gesagt, nach dem Testen sind die asserts schnell (durch Deaktivieren [ich denke, es funktioniert auf den C-Level-Asserts ...]), die einzigen plausibel langsamen Teile sind:

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

Welche sind:

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

(schnell wie zuvor),

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

(schnell, wenn das Makro IS_ASCIIschnell ist) und

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

(auch schnell, da es sich um eine Behauptung plus eine Indirektion plus eine Besetzung handelt).

Also sind wir unten (das Kaninchenloch), um:

PyUnicode_IS_ASCII

welches ist

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

Hmm ... das scheint auch schnell zu gehen ...

Na gut, aber vergleichen wir es mit PyList_GetItem. (Ja, danke Tim Peters, dass er mir mehr Arbeit gegeben hat: 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];
}

Wir können sehen, dass dies in Fällen ohne Fehler nur ausgeführt wird:

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

Wo PyList_Checkist

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

( TABS! TABS !!! ) ( issue21587 ) Das wurde behoben und in 5 Minuten zusammengeführt . Wie ... ja. Verdammt. Sie beschämen Skeet.

#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

Das ist normalerweise sehr trivial (zwei Indirektionen und ein paar boolesche Prüfungen), es sei denn Py_LIMITED_API sei ist aktiviert. In diesem Fall ... ???

Dann gibt es die Indizierung und eine Besetzung (((PyListObject *)op) -> ob_item[i] ) und wir sind fertig.

Es gibt also definitiv weniger Überprüfungen für Listen, und die kleinen Geschwindigkeitsunterschiede implizieren sicherlich, dass dies relevant sein könnte.

Ich denke, im Allgemeinen gibt es (->)für Unicode nur mehr Typprüfung und Indirektion . Es scheint, ich vermisse einen Punkt, aber was ?

Veedrac
quelle
17
Sie präsentieren den Code als selbsterklärend. Sie präsentieren sogar die Schnipsel als Schlussfolgerungen. Leider kann ich dem nicht wirklich folgen. Nicht zu sagen, dass Ihr Ansatz, um herauszufinden, was falsch ist, nicht solide ist, aber es wäre schön, wenn es einfacher wäre, zu folgen.
PascalVKooten
2
Ich habe versucht, es zu verbessern, bin mir aber nicht sicher, wie ich es klarer machen soll. Beachten Sie, dass ich kein C schreibe. Dies ist also eine allgemeine Analyse des Codes, und nur die Gesamtkonzepte sind wichtig.
Veedrac
@Nit habe ich hinzugefügt. Sag mir, ob es sich mangelhaft anfühlt. Leider zeigt es auch, dass ich die Antwort nicht wirklich kenne (* keuch *).
Veedrac
3
Ich werde dies einen weiteren Tag geben, bevor ich Ihre Antwort akzeptiere (ich würde gerne etwas Konkreteres sehen), aber ich danke Ihnen für die sehr interessante und gut recherchierte Antwort.
Sunjay Varma
4
Beachten Sie, dass Sie auf ein sich bewegendes Ziel schießen ;-) Diese Implementierung unterscheidet sich nicht nur zwischen Python 2 und Python 3, sondern auch zwischen verschiedenen Versionen. Auf dem aktuellen Entwicklungs-Trunk existiert der get_latin1_char()Trick beispielsweise nicht mehr in unicode_getitem(), sondern in der unteren Ebene unicode_char. Es gibt also jetzt eine andere Ebene des Funktionsaufrufs - oder auch nicht (abhängig vom verwendeten Compiler und den verwendeten Optimierungsflags). Auf dieser Detailebene gibt es einfach keine verlässlichen Antworten ;-)
Tim Peters
31

Wenn Sie über die meisten Containerobjekte (Listen, Tupel, Diktate, ...) iterieren, liefert der Iterator die Objekte in Container.

Wenn Sie jedoch über eine Zeichenfolge iterieren , muss für jedes gelieferte Zeichen ein neues Objekt erstellt werden - eine Zeichenfolge ist nicht "ein Container" im gleichen Sinne wie eine Liste ein Container. Die einzelnen Zeichen in einer Zeichenfolge sind nicht als unterschiedliche Objekte vorhanden, bevor die Iteration diese Objekte erstellt.

Tim Peters
quelle
3
Ich denke nicht, dass das wahr ist. Sie können mit überprüfen is. Es klingt richtig, aber ich glaube wirklich nicht, dass es sein kann.
Veedrac
Schauen Sie sich die Antwort von @Veedrac an.
Christian
3
stringobject.czeigt, dass __getitem__für Zeichenfolgen nur das Ergebnis aus einer Tabelle gespeicherter 1-Zeichen-Zeichenfolgen abgerufen wird, sodass die Zuordnungskosten für diese nur einmal anfallen.
user2357112 unterstützt Monica
10
@ user2357112, ja, für einfache Zeichenfolgen in Python 2 ist dies ein wichtiger Punkt. In Python 3 sind alle Zeichenfolgen "offiziell" Unicode und es sind viel mehr Details involviert (siehe Veedracs Antwort). Zum Beispiel in Python 3 nach s = chr(256), s is chr(256)kehrt False- die Art allein zu wissen , ist nicht genug, denn Berge von Sonderfällen unter den Abdeckungen bestehen Triggern auf den Datenwert .
Tim Peters
1

Das Erstellen des Iterators für die Zeichenfolge kann zu einem Mehraufwand führen. Während das Array bereits bei der Instanziierung einen Iterator enthält.

BEARBEITEN:

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

Dies wurde mit 2.7 ausgeführt, aber auf meinem MacBook Pro i7. Dies kann auf einen Unterschied in der Systemkonfiguration zurückzuführen sein.

Robert Chumley
quelle
Selbst wenn nur die geraden Iteratoren verwendet werden, ist die Zeichenfolge immer noch erheblich langsamer. timeit ("[x für x darin]", "it = iter ('abc')") = 0,34543599384033535; timeit ("[x für x darin]", "it = iter (Liste ('abc'))") = 0.2791691380446508
Sunjay Varma