una tiene separar saber por palabras funcion frase cuantas contar comparar como caracteres caracter cadenas python performance cpython timeit python-internals

tiene - python separar string por caracter



¿Por qué es más lento iterar sobre una cadena pequeña que una lista pequeña? (4)

TL; DR

  • La diferencia de velocidad real es más cercana al 70% (o más) una vez que se elimina la sobrecarga, para Python 2.

  • La creación de objetos no es la culpa. Ninguno de los métodos crea un nuevo objeto, ya que las cadenas de un carácter se almacenan en caché.

  • La diferencia es obvia, pero es probable que se cree a partir de un mayor número de controles en la indexación de cadenas, con respecto al tipo y la buena formación. También es bastante probable gracias a la necesidad de verificar qué devolver.

  • La indexación de listas es notablemente rápida.

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

Esto no concuerda con lo que has encontrado ...

Debes estar usando Python 2, entonces.

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

Vamos a explicar la diferencia entre las versiones. Examinaré el código compilado.

Para 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

Aquí verá que es probable que la variante de lista sea más lenta debido a la construcción de la lista cada vez.

Este es el

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

parte. La variante de cuerda solo tiene

9 LOAD_CONST 3 (''abc'')

Puedes comprobar que esto parece marcar la diferencia:

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

Esto produce solo

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

como las tuplas son inmutables. Prueba:

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

Genial, vuelve a la velocidad.

Para 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

Lo curioso es que tenemos el mismo edificio de la lista, pero aún es más rápido para esto. Python 2 actúa de manera extrañamente rápida.

Vamos a eliminar las comprensiones y el tiempo de reutilización. El _ = es para evitar que se optimice.

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

Podemos ver que la inicialización no es lo suficientemente significativa como para tener en cuenta la diferencia entre las versiones (¡esos números son pequeños)! Podemos concluir que Python 3 tiene una comprensión más lenta. Esto tiene sentido ya que Python 3 cambió las comprensiones para tener un alcance más seguro.

Bueno, ahora mejora el punto de referencia (solo estoy eliminando gastos generales que no es iteración). Esto elimina la creación de iterable al asignarle previamente:

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

Podemos verificar si llamar a iter es la sobrecarga:

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

No. No, no lo es. La diferencia es muy pequeña, especialmente para Python 3.

Así que eliminemos aún más sobrecarga no deseada ... ¡haciendo que todo sea más lento! El objetivo es solo tener una iteración más larga para que el tiempo oculte la sobrecarga.

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

Esto en realidad no ha cambiado mucho , pero ayudó un poco.

Entonces elimina la comprensión. Es sobrecargado que no es parte de la pregunta:

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

¡Eso es más como eso! Podemos obtener un poco más rápido aún usando deque para iterar. Es básicamente lo mismo, pero es más rápido :

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

Lo que me impresiona es que Unicode es competitivo con cadenas de bytes. Podemos comprobar esto explícitamente probando bytes y unicode en ambos:

  • 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

    Aquí puede ver que Python 3 es más rápido 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

    Una vez más, Python 3 es más rápido, aunque esto es de esperar ( str ha tenido mucha atención en Python 3).

De hecho, esta diferencia de unicode - bytes es muy pequeña, lo cual es impresionante.

Analicemos este caso, ya que es rápido y conveniente para mí:

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

¡De hecho, podemos descartar la respuesta de Tim Peter de 10 veces al alza!

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

¡Estos no son objetos nuevos!

Pero vale la pena mencionar esto: costos de indexación. La diferencia probablemente estará en la indexación, por lo tanto, elimine la iteración y solo indexe:

>>> 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 diferencia parece pequeña, pero al menos la mitad del costo es por encima:

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

entonces la diferencia de velocidad es suficiente para decidir culparlo. Creo.

Entonces, ¿por qué indexar una lista es mucho más rápido?

Bueno, voy a volver sobre eso, pero supongo que se debe a la verificación de cadenas internas (o caracteres en caché si se trata de un mecanismo separado). Esto será menos rápido que óptimo. Pero voy a revisar la fuente (aunque no me siento cómodo en C ...) :).

Así que aquí está la fuente:

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

Caminando desde la parte superior, tendremos algunos controles. Estos son aburridos. Luego algunos asignados, que también deberían ser aburridos. La primera línea interesante es

ch = PyUnicode_READ(kind, data, index);

pero esperamos que sea rápido, ya que estamos leyendo desde una matriz C contigua al indexarla. El resultado, ch , será menor que 256, así que devolveremos el carácter en caché en get_latin1_char(ch) .

Así que correremos (dejando caer los primeros controles)

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

Dónde

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

(que es aburrido porque afirma que se ignora en la depuración [para que pueda comprobar que son rápidos] y ((PyASCIIObject *)(op))->state.kind) es (creo) un indirecto y un elenco de nivel C );

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

(que también es aburrido por razones similares, suponiendo que las macros ( Something_CAPITALIZED ) son todas rápidas),

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

(que involucra índices pero realmente no es lento en absoluto) y

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

Lo que confirma mi sospecha de que:

  • Esto está en caché:

    PyObject *unicode = unicode_latin1[ch];

  • Esto debería ser rápido. El if (!unicode) no se ejecuta, por lo que es literalmente equivalente en este caso a

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

Honestamente, después de probar las assert son rápidas (deshabilitándolas [ creo que funciona en el nivel C afirma ...]), las únicas partes plausiblemente lentas son:

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

Que son:

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

(rápido, como antes),

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

(rápido si la macro IS_ASCII es rápida), y

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

(También es rápido, ya que es una afirmación más una indirección más un elenco).

Así que estamos abajo (el agujero del conejo) para:

PyUnicode_IS_ASCII

cual es

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

Hmm ... eso parece rápido también ...

Bueno, está bien, pero vamos a compararlo con PyList_GetItem . (Sí, gracias Tim Peters por darme más trabajo que hacer: 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]; }

Podemos ver que en casos que no son de error, esto solo se ejecutará:

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

Donde PyList_Check es

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

( ¡TABS! TABS !!! ) ( issue21587 ) Eso se corrigió y se fusionó en 5 minutos . Como ... si. Maldita sea. Ellos ponen a Skeet a la vergüenza.

#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

Entonces esto es realmente trivial (dos indirecciones y un par de verificaciones booleanas) a menos que Py_LIMITED_API esté Py_LIMITED_API , en cuyo caso ... ???

Luego está la indexación y un molde ( ((PyListObject *)op) -> ob_item[i] ) y hemos terminado.

Así que definitivamente hay menos controles para las listas, y las pequeñas diferencias de velocidad ciertamente implican que podría ser relevante.

Creo que, en general, solo hay más comprobación de tipos e indirección (->) para Unicode. Parece que me falta un punto, pero ¿qué ?

Estaba jugando con timeit y me di cuenta de que hacer una simple lista de comprensión en una cadena pequeña llevó más tiempo que hacer la misma operación en una lista de cadenas de caracteres individuales pequeñas. ¿Alguna explicación? Es casi 1,35 veces más tiempo.

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

¿Qué está sucediendo en un nivel inferior que está causando esto?

Cuando itera sobre la mayoría de los objetos del contenedor (listas, tuplas, dicts, ...), el iterador entrega los objetos en el contenedor.

Pero cuando itera sobre una cadena, se debe crear un nuevo objeto para cada carácter entregado: una cadena no es "un contenedor" en el mismo sentido en que una lista es un contenedor. Los caracteres individuales en una cadena no existen como objetos distintos antes de que la iteración cree esos objetos.

No se pueden confirmar los resultados para Python 2: en Python 2 no parece marcar la diferencia si itera sobre cadenas o listas ... ¡y las tuplas son bastante rápidas!

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

Podría incurrir en una sobrecarga para crear el iterador de la cadena. Mientras que la matriz ya contiene un iterador en la creación de instancias.

EDITAR:

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

Esto se ejecutó usando 2.7, pero en mi mac book pro i7. Esto podría ser el resultado de una diferencia de configuración del sistema.