Pourquoi est-il plus lent d'itérer sur une petite chaîne qu'une petite liste?

132

Je jouais avec timeit et j'ai remarqué que faire une simple compréhension de liste sur une petite chaîne prenait plus de temps que de faire la même opération sur une liste de petites chaînes de caractères uniques. Une explication? C'est presque 1,35 fois plus de temps.

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

Qu'est-ce qui se passe à un niveau inférieur qui cause cela?

python performance cpython timeit python-internals Sunjay Varma
la source

Réponses:

193

TL; DR

  • La différence de vitesse réelle est plus proche de 70% (ou plus) une fois qu'une grande partie de la surcharge est supprimée, pour Python 2.

  • La création d'objet n'est pas en cause. Aucune des deux méthodes ne crée un nouvel objet, car les chaînes à un caractère sont mises en cache.

  • La différence n'est pas évidente, mais est probablement créée à partir d'un plus grand nombre de vérifications sur l'indexation des chaînes, en ce qui concerne le type et la bonne formation. C'est également très probable grâce à la nécessité de vérifier ce qu'il faut retourner.

  • L'indexation des listes est remarquablement rapide.

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

Cela ne correspond pas à ce que vous avez trouvé ...

Vous devez donc utiliser Python 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

Expliquons la différence entre les versions. Je vais examiner le code compilé.

Pour 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

Vous voyez ici que la variante de liste est susceptible d'être plus lente en raison de la construction de la liste à chaque fois.

C'est le

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

partie. La variante de chaîne n'a que

 9 LOAD_CONST   3 ('abc')

Vous pouvez vérifier que cela semble faire une différence:

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

Cela produit juste

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

car les tuples sont immuables. Tester:

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

Super, revenez à la vitesse supérieure.

Pour 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

La chose étrange est que nous avons le même bâtiment de la liste, mais c'est toujours plus rapide pour cela. Python 2 agit étrangement vite.

Supprimons les compréhensions et répétons le temps. Le but _ =est d'éviter qu'il ne soit optimisé.

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

On voit que l'initialisation n'est pas assez importante pour tenir compte de la différence entre les versions (ces nombres sont petits)! On peut donc conclure que Python 3 a des compréhensions plus lentes. Cela a du sens car Python 3 a changé ses compréhensions pour avoir une portée plus sûre.

Eh bien, améliorez maintenant le benchmark (je supprime simplement les frais généraux qui ne sont pas des itérations). Cela supprime la construction de l'itérable en le pré-assignant:

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

Nous pouvons vérifier si l'appel iterest la surcharge:

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

Non, ce n'est pas le cas. La différence est trop petite, en particulier pour Python 3.

Supprimons donc encore plus de frais généraux indésirables ... en ralentissant le tout! Le but est simplement d'avoir une itération plus longue afin que le temps cache les frais généraux.

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

Cela n'a en fait pas beaucoup changé , mais cela a un peu aidé.

Alors supprimez la compréhension. Ce sont les frais généraux qui ne font pas partie de la question:

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

C'est plus comme ça! Nous pouvons encore être légèrement plus rapides en utilisant dequepour itérer. C'est fondamentalement la même chose, mais c'est plus rapide :

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

Ce qui m'impressionne, c'est qu'Unicode est compétitif avec les bytestrings. Nous pouvons vérifier cela explicitement en essayant byteset unicodedans les deux:

  • 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

    Ici, vous voyez Python 3 en fait plus rapide que 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

    Encore une fois, Python 3 est plus rapide, bien que cela soit prévisible ( stra eu beaucoup d'attention dans Python 3).

En fait, cette unicode- bytesdifférence est très faible, ce qui est impressionnant.

Analysons donc ce cas, car c'est rapide et pratique pour moi:

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

Nous pouvons en fait exclure la réponse 10 fois plus élevée de Tim Peter!

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

Ce ne sont pas des objets nouveaux!

Mais cela mérite d'être mentionné: les coûts d' indexation . La différence sera probablement dans l'indexation, supprimez donc l'itération et indexez simplement:

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

La différence semble faible, mais au moins la moitié du coût est des frais généraux:

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

donc la différence de vitesse est suffisante pour décider de la blâmer. Je pense.

Alors pourquoi l'indexation d'une liste est-elle beaucoup plus rapide?

Eh bien, je vais vous revenir là-dessus, mais je suppose que cela dépend de la vérification des chaînes internes (ou des caractères mis en cache s'il s'agit d'un mécanisme distinct). Ce sera moins rapide qu'optimal. Mais je vais vérifier la source (même si je ne suis pas à l'aise en C ...) :).

Voici donc la source:

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

En marchant du haut, nous aurons quelques contrôles. Ce sont ennuyeux. Puis quelques assignations, qui devraient aussi être ennuyeuses. La première ligne intéressante est

ch = PyUnicode_READ(kind, data, index);

mais nous espérons que ce sera rapide, car nous lisons à partir d'un tableau C contigu en l'indexant. Le résultat chsera inférieur à 256 donc nous retournerons le caractère mis en cache dans get_latin1_char(ch).

Alors nous allons courir (abandonner les premiers contrôles)

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

Où

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

(ce qui est ennuyeux parce que les assertions sont ignorées dans le débogage [afin que je puisse vérifier qu'elles sont rapides] et ((PyASCIIObject *)(op))->state.kind)est (je pense) une indirection et une distribution de niveau C);

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

(ce qui est également ennuyeux pour des raisons similaires, en supposant que les macros ( Something_CAPITALIZED) sont toutes rapides),

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

(qui implique des index mais n'est vraiment pas lent du tout) et

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

Ce qui confirme mon soupçon que:

  • Ceci est mis en cache:

    PyObject *unicode = unicode_latin1[ch];

  • Cela devrait être rapide. Le if (!unicode)n'est pas exécuté, donc c'est littéralement équivalent dans ce cas à

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

Honnêtement, après avoir testé les asserts sont rapides (en les désactivant [je pense que cela fonctionne sur les assertions de niveau C ...]), les seules parties plausiblement lentes sont:

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

Qui sont:

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

(rapide, comme avant),

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

(rapide si la macro IS_ASCIIest rapide), et

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

(aussi rapide car c'est une affirmation plus une indirection plus un casting).

Nous sommes donc en bas (le terrier du lapin) pour:

PyUnicode_IS_ASCII

lequel est

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

Hmm ... ça semble rapide aussi ...

Eh bien, OK, mais comparons-le à PyList_GetItem. (Oui, merci Tim Peters de m'avoir donné plus de travail à faire: 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];
}

Nous pouvons voir que dans les cas sans erreur, cela va simplement fonctionner:

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

Où PyList_Checkest

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

( TABS! TABS !!! ) ( issue21587 ) Cela a été corrigé et fusionné en 5 minutes . Comme ... ouais. Zut. Ils ont fait honte à 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

Donc c'est normalement vraiment trivial (deux indirections et quelques vérifications booléennes) à moins qu'il ne Py_LIMITED_APIsoit activé, auquel cas ... ???

Ensuite, il y a l'indexation et un cast ( ((PyListObject *)op) -> ob_item[i]) et nous avons terminé.

Il y a donc certainement moins de vérifications pour les listes, et les petites différences de vitesse impliquent certainement que cela pourrait être pertinent.

Je pense qu'en général, il y a juste plus de vérification de type et d'indirection (->)pour Unicode. Il semble que je manque un point, mais quoi ?

Veedrac
la source
17
Vous présentez le code comme explicite; vous présentez même les extraits comme des conclusions. Malheureusement pour moi, je ne peux pas vraiment le suivre. Ne pas dire que votre approche pour découvrir ce qui ne va pas n'est pas solide, mais ce serait bien si elle était plus facile à suivre.
PascalVKooten
2
J'ai essayé de l'améliorer, mais je ne sais pas comment le rendre plus clair. Notez que je n'écris pas C, il s'agit donc d'une analyse de haut niveau du code et seuls les concepts globaux sont importants.
Veedrac
@Nit j'ai ajouté. Dites-moi si cela manque. Malheureusement, cela souligne également que je ne connais pas vraiment la réponse (* halètement *).
Veedrac
3
Je vais vous donner un autre jour avant d'accepter votre réponse (j'aimerais voir quelque chose de plus concret apparaître), mais merci pour la réponse très intéressante et bien documentée.
Sunjay Varma
4
Notez que vous tirez sur une cible en mouvement ;-) Cette implémentation ne diffère pas seulement entre Python 2 et Python 3, mais aussi entre différentes versions. Par exemple, sur le tronc de développement actuel, l' get_latin1_char()astuce n'existe plus dans unicode_getitem(), mais au niveau inférieur unicode_char. Il y a donc un autre niveau d'appel de fonction maintenant - ou pas (selon le compilateur et les indicateurs d'optimisation utilisés). À ce niveau de détail, il n'y a tout simplement pas de réponses fiables ;-)
Tim Peters
31

Lorsque vous itérez sur la plupart des objets conteneurs (listes, tuples, dicts, ...), l'itérateur délivre les objets dans le conteneur.

Mais lorsque vous parcourez une chaîne, un nouvel objet doit être créé pour chaque caractère livré - une chaîne n'est pas "un conteneur" dans le même sens qu'une liste est un conteneur. Les caractères individuels d'une chaîne n'existent pas en tant qu'objets distincts avant que l'itération ne crée ces objets.

Tim Peters
la source
3
Je ne pense pas que ce soit vrai, en fait. Vous pouvez vérifier avec is. Cela semble juste, mais je ne pense vraiment pas que cela puisse être.
Veedrac
Jetez un œil à la réponse @Veedrac.
Christian
3
stringobject.cmontre que __getitem__pour les chaînes récupère simplement le résultat d'une table de chaînes stockées à 1 caractère, les coûts d'allocation pour celles-ci ne sont donc encourus qu'une seule fois.
user2357112 prend en charge Monica
10
@ user2357112, oui, pour les chaînes simples en Python 2, c'est un point vital. Dans Python 3, toutes les chaînes sont "officiellement" Unicode et beaucoup plus de détails sont impliqués (voir la réponse de Veedrac). Par exemple, dans Python 3, après s = chr(256), s is chr(256)retourne False- connaître le type seul ne suffit pas, car des tas de cas spéciaux existent sous les couvertures se déclenchant sur les valeurs de données .
Tim Peters
1

La création de l'itérateur de la chaîne peut entraîner des frais supplémentaires. Alors que le tableau contient déjà un itérateur lors de l'instanciation.

ÉDITER:

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

Cela a été exécuté avec 2.7, mais sur mon mac book pro i7. Cela peut être le résultat d'une différence de configuration du système.

Robert Chumley
la source
Même en utilisant simplement les itérateurs droits, la chaîne est encore beaucoup plus lente. 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