Je jouait avec timeit et remarqué que faisant une compréhension de liste simple sur une petite chaîne a pris plus de temps que de faire la même opération sur une liste de chaînes de caractères unique Petit. Aucune explication ? C’est presque 1,35 fois plus de temps.
Ce qui se passe à un niveau inférieur qui est la cause ?
La réelle différence de vitesse est plus proche de 70% (ou plus) une fois beaucoup de la charge est retirée, pour Python 2.
Création de l'objet n'est pas en faute. Aucune méthode crée un nouvel objet, comme les chaînes de caractères sont mises en cache.
La différence, c'est évident, mais il est probable créé à partir d'un plus grand nombre de contrôles sur la chaîne d'indexation, en ce qui concerne le type et le bien-formation. Il est également très probable que grâce à la nécessité de vérifier ce qu'il doit retourner.
Liste d'indexation 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
Ce n'est pas d'accord avec ce que vous avez trouvé...
Vous devez être à l'aide de Python 2, puis.
>>> 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
Nous allons expliquer 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 lent 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 chaîne variante a
9 LOAD_CONST 3 ('abc')
Vous pouvez vérifier que cela ne semble pas 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
Ce produit juste
9 LOAD_CONST 6 (('a', 'b', 'c'))
comme les tuples sont immuables. Test:
>>> python3 -m timeit '[x for x in ("a", "b", "c")]'
1000000 loops, best of 3: 0.369 usec per loop
Grand, retour à la vitesse.
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 encore plus rapide pour cela. Python 2 est agi étrangement rapide.
Nous allons supprimer les interprétations de la et de ré-temps. L' _ = est de l'empêcher d'obtenir 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
Nous pouvons voir que l'initialisation n'est pas assez important pour rendre compte de la différence entre les versions (ces nombres sont petits)! Nous pouvons donc conclure que Python 3 est plus lent interprétations. Ceci n'a de sens que Python 3 changé interprétations avoir saner portée.
Eh bien, maintenant améliorer l'indice de référence (je suis juste éliminer la surcharge qui n'est pas de l'itération). Cela supprime la construction de l'objet iterable par pré-affectation:
>>> 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 vous appelez iter est 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
Pas de. Non, il n'est pas. La différence est trop petite, surtout pour Python 3.
Donc, nous allons supprimer encore plus indésirables généraux... en rendant le tout plus lent! Le but est juste d'avoir une plus longue itération, donc le temps de peaux de 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 pas réellement changé beaucoup, mais il est un peu aidé.
Donc, supprimer la compréhension. C'est frais généraux qui ne fait 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 mieux comme ça! Nous pouvons obtenir un peu plus rapide encore en utilisant deque pour itérer. C'est fondamentalement la même, 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 que l'Unicode est en concurrence avec bytestrings. On peut vérifier cela explicitement en essayant bytes et unicode à la fois:
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, même si ce n'est à prévoir (str a eu beaucoup d'attention en Python 3).
En fait, c' unicode-bytes différence est très petite, ce qui est impressionnant.
Donc, nous allons analyser ce cas, vu comme 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 la règle Tim-Pierre 10-fois-upvoted réponse!
>>> foo = iterable[123]
>>> iterable[36] is foo
True
Mais cela vaut la peine de mentionner: l'indexation des coûts. La différence sera probablement dans l'indexation, donc supprimer l'itération et indexer:
>>> 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 au-dessus:
>>> 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
si la différence de vitesse est suffisante pour décider de la blâmer. Je pense que.
Alors, pourquoi est-indexation d'une liste beaucoup plus vite?
Eh bien, je vais revenir à vous sur ce point, mais je pense que c'est est vers le bas de la case pour les internés des chaînes de caractères (ou de mettre en cache les caractères si c'est un autre mécanisme). Ce sera moins rapide qu'optimale. Mais je vais aller vérifier la source (bien que je ne suis pas à l'aise en C...) :).
Alors, voici 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;
}
La marche du haut, nous avons quelques vérifications. Ces sont ennuyeux. Ensuite, certains ayants droit, qui devrait également être ennuyeux. La première ligne est intéressante
ch = PyUnicode_READ(kind, data, index);
mais nous avions l'espoir que bientôt, comme nous sommes la lecture à partir d'une ligne de C tableau par l'indexation. Le résultat, ch, sera de moins de 256 donc, nous allons retourner la mise en cache de caractère en get_latin1_char(ch).
Donc, nous allons exécuter (chute de la première recherche)
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 affirme ignoré dans debug [afin que je puisse vérifier qu'ils sont rapide] et ((PyASCIIObject *)(op))->state.kind) est (je pense) une indirection et un C-niveau de fonte);
#define PyUnicode_DATA(op) \
(assert(PyUnicode_Check(op)), \
PyUnicode_IS_COMPACT(op) ? _PyUnicode_COMPACT_DATA(op) : \
_PyUnicode_NONCOMPACT_DATA(op))
(qui est aussi ennuyeux pour des raisons similaires, en supposant que les macros (Something_CAPITALIZED) sont tous rapide),
#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)] \
) \
))
(ce qui implique d'index, mais n'est pas vraiment lent) 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 mes soupçons:
Ceci est mis en cache:
PyObject *unicode = unicode_latin1[ch];
Cela devrait être rapide. L' if (!unicode) n'est pas exécuté, il est donc littéralement équivalent dans ce cas
PyObject *unicode = unicode_latin1[ch];
Py_INCREF(unicode);
return unicode;
Honnêtement, après avoir testé l' asserts sont rapides (en les désactivant [je pense que cela fonctionne sur le C-level affirme...]), la seule plausible-parties 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_ASCII est rapide), et
#define _PyUnicode_NONCOMPACT_DATA(op) \
(assert(((PyUnicodeObject*)(op))->data.any), \
((((PyUnicodeObject *)(op))->data.any)))
(aussi vite que c'est une assertion plus une indirection en plus d'une distribution).
Nous en sommes (le trou du lapin):
PyUnicode_IS_ASCII
qui est
#define PyUnicode_IS_ASCII(op) \
(assert(PyUnicode_Check(op)), \
assert(PyUnicode_IS_READY(op)), \
((PyASCIIObject*)op)->state.ascii)
Hmm... qui semble trop rapide...
Eh bien, OK, mais nous allons la comparer à l' PyList_GetItem. (Ouais, merci Tim Peters pour me donner 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 sur la non-cas d'erreur, c'est juste de la faire fonctionner:
PyList_Check(op)
Py_SIZE(op)
((PyListObject *)op) -> ob_item[i]
Où PyList_Check est
#define PyList_Check(op) \
PyType_FastSubclass(Py_TYPE(op), Py_TPFLAGS_LIST_SUBCLASS)
(ONGLETS! Les ONGLETS!!!) (issue21587) Qui a obtenu fixes et regroupées en 5 minutes. Comme... ouais. Merde. Ils ont mis au pigeon d'argile à la honte.
#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 normalement, c'est vraiment trivial (deux indirections et un couple de booléenne contrôles) à moins d' Py_LIMITED_API est sur, dans ce cas... ???
Puis il y a l'indexation et de la fonte (((PyListObject *)op) -> ob_item[i]) et nous avons fini.
Il y a donc certainement moins de contrôles pour les listes et les petites différences de vitesse certainement dire qu'il pourrait être pertinent.
Je pense en général, il y a juste plus de la vérification de type et d'indirection (->) pour l'unicode. Il semble que je suis en manque un point, mais quoi?
Lorsque vous parcourez la plupart des objets conteneur (listes, tuples, dicts,...), l’itérateur fournit les objets dans le conteneur.
Mais lorsque vous parcourez une chaîne, un nouvel objet doit être créé pour chaque caractère prononcé - une chaîne n’est pas « conteneur » dans le même sens, une liste est un conteneur. Les différents caractères d’une chaîne n’existent pas en tant qu’objets distincts avant itération crée ces objets.
Vous pourriez avoir à engager et à créer un itérateur pour la chaîne. Alors que le tableau contient déjà un itérateur lors de l'instanciation.
MODIFIER:
>>> timeit("[x for x in ['a','b','c']]")
0.3818681240081787
>>> timeit("[x for x in 'abc']")
0.3732869625091553
Cela a été exécuté en utilisant 2.7, mais sur mon mac book pro i7. Cela pourrait être le résultat d'une différence de configuration du système.
Impossible de confirmer les résultats pour Python 2: En Python 2, cela ne semble pas faire de différence si vous parcourez des chaînes ou des listes ... et les tuples sont assez rapides!
import platform
print('Python', platform.python_version())
%timeit [c for c in 'abcd']
%timeit [c for c in ['a', 'b', 'c', 'd']]
%timeit [c for c in ('a', 'b', 'c', 'd')]
Python 3.4.0
1000000 loops, best of 3: 502 ns per loop
1000000 loops, best of 3: 638 ns per loop
1000000 loops, best of 3: 475 ns per loop
import platform
print 'Python', platform.python_version()
%timeit [c for c in 'abcd']
%timeit [c for c in ['a', 'b', 'c', 'd']]
%timeit [c for c in ('a', 'b', 'c', 'd')]
Python 2.7.6
1000000 loops, best of 3: 458 ns per loop
1000000 loops, best of 3: 464 ns per loop
1000000 loops, best of 3: 280 ns per loop
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
