¿Cuál es el objeto de estructura más rápido (para acceder) en Python?

Estoy optimizando un código cuyo cuello de botella principal se está ejecutando y accediendo a una lista muy grande de objetos tipo estructura. Actualmente estoy usando namedtuples, por legibilidad. Sin embargo, algunas evaluaciones comparativas rápidas que usan ‘timeit’ muestran que esta es realmente la manera incorrecta de ir donde el rendimiento es un factor:

Tupla nombrada con a, b, c:

>>> timeit("z = ac", "from __main__ import a") 0.38655471766332994 

Clase usando __slots__ , con a, b, c:

 >>> timeit("z = bc", "from __main__ import b") 0.14527461047146062 

Diccionario con teclas a, b, c:

 >>> timeit("z = c['c']", "from __main__ import c") 0.11588272541098377 

Tupla con tres valores, utilizando una clave constante:

 >>> timeit("z = d[2]", "from __main__ import d") 0.11106188992948773 

Lista con tres valores, utilizando una clave constante:

 >>> timeit("z = e[2]", "from __main__ import e") 0.086038238242508669 

Tuple con tres valores, utilizando una clave local:

 >>> timeit("z = d[key]", "from __main__ import d, key") 0.11187358437882722 

Lista con tres valores, utilizando una clave local:

 >>> timeit("z = e[key]", "from __main__ import e, key") 0.088604143037173344 

En primer lugar, ¿hay algo en estas pruebas de tiempo que las haga inválidas? Corrí cada una de ellas varias veces, para asegurarme de que ningún evento aleatorio del sistema las había desactivado y los resultados eran casi idénticos.

Parece que los diccionarios ofrecen el mejor equilibrio entre rendimiento y legibilidad, con las clases en segundo lugar. Esto es desafortunado, ya que, para mis propósitos, también necesito que el objeto sea como una secuencia; de ahí mi elección de nameduuple.

Las listas son sustancialmente más rápidas, pero las claves constantes no se pueden mantener; Tendría que crear un grupo de constantes de índice, es decir, KEY_1 = 1, KEY_2 = 2, etc., lo que tampoco es ideal.

¿Estoy atascado con estas opciones o hay una alternativa que me he perdido?

Una cosa a tener en cuenta es que las tuplas nombradas están optimizadas para el acceso como tuplas. Si cambia su accesorio de acceso para que sea a[2] lugar de ac , verá un rendimiento similar al de las tuplas. La razón es que los accesores de nombres se traducen efectivamente en llamadas a self [idx], por lo tanto, pague tanto la indexación como el precio de búsqueda de nombres.

Si su patrón de uso es tal que el acceso por nombre es común, pero el acceso como tupla no lo es, puede escribir un equivalente rápido a nameduuple que hace las cosas de manera opuesta: difiere las búsquedas de índice para acceder a by-name. Sin embargo, entonces pagará el precio en las búsquedas de índice. Por ejemplo, aquí hay una implementación rápida:

 def makestruct(name, fields): fields = fields.split() import textwrap template = textwrap.dedent("""\ class {name}(object): __slots__ = {fields!r} def __init__(self, {args}): {self_fields} = {args} def __getitem__(self, idx): return getattr(self, fields[idx]) """).format( name=name, fields=fields, args=','.join(fields), self_fields=','.join('self.' + f for f in fields)) d = {'fields': fields} exec template in d return d[name] 

Pero los tiempos son muy malos cuando se debe llamar a __getitem__ :

 namedtuple.a : 0.473686933517 namedtuple[0] : 0.180409193039 struct.a : 0.180846214294 struct[0] : 1.32191514969 

es decir, el mismo rendimiento que una clase __slots__ para el acceso a los atributos (como es de esperar, eso es lo que es), pero con grandes multas debido a la doble búsqueda en los accesos basados ​​en índices. (Cabe destacar que __slots__ realidad no ayuda mucho en cuanto a la velocidad. Ahorra memoria, pero el tiempo de acceso es casi el mismo sin ellos).

Una tercera opción sería duplicar los datos, por ejemplo. Subclase de la lista y almacene los valores tanto en los atributos como en la lista de datos. Sin embargo, en realidad no se obtiene un rendimiento equivalente a la lista. Hay un gran golpe de velocidad solo por haber sido subclasificado (lo que trae cheques para sobrecargas de python puro). Por lo tanto, struct [0] todavía toma alrededor de 0.5s (en comparación con 0.18 para la lista en bruto) en este caso, y usted duplica el uso de la memoria, por lo que puede que no valga la pena.

Esta pregunta es bastante antigua (tiempo de Internet), así que pensé que hoy intentaría duplicar su prueba, tanto con CPython regular (2.7.6) como con pypy (2.2.1) y ver cómo se comparan los distintos métodos. (También agregué en una búsqueda indexada para la tupla nombrada).

Esto es un poco de un micro-punto de referencia, por lo que YMMV, pero pypy pareció acelerar el acceso a la tupla de nombre por un factor de 30 vs CPython (mientras que el acceso al diccionario solo se aceleró por un factor de 3).

 from collections import namedtuple STest = namedtuple("TEST", "abc") a = STest(a=1,b=2,c=3) class Test(object): __slots__ = ["a","b","c"] a=1 b=2 c=3 b = Test() c = {'a':1, 'b':2, 'c':3} d = (1,2,3) e = [1,2,3] f = (1,2,3) g = [1,2,3] key = 2 if __name__ == '__main__': from timeit import timeit print("Named tuple with a, b, c:") print(timeit("z = ac", "from __main__ import a")) print("Named tuple, using index:") print(timeit("z = a[2]", "from __main__ import a")) print("Class using __slots__, with a, b, c:") print(timeit("z = bc", "from __main__ import b")) print("Dictionary with keys a, b, c:") print(timeit("z = c['c']", "from __main__ import c")) print("Tuple with three values, using a constant key:") print(timeit("z = d[2]", "from __main__ import d")) print("List with three values, using a constant key:") print(timeit("z = e[2]", "from __main__ import e")) print("Tuple with three values, using a local key:") print(timeit("z = d[key]", "from __main__ import d, key")) print("List with three values, using a local key:") print(timeit("z = e[key]", "from __main__ import e, key")) 

Resultados de Python:

 Named tuple with a, b, c: 0.124072679784 Named tuple, using index: 0.0447055962367 Class using __slots__, with a, b, c: 0.0409136944224 Dictionary with keys a, b, c: 0.0412045334915 Tuple with three values, using a constant key: 0.0449477955531 List with three values, using a constant key: 0.0331083467148 Tuple with three values, using a local key: 0.0453569025139 List with three values, using a local key: 0.033030056702 

Resultados de PyPy:

 Named tuple with a, b, c: 0.00444889068604 Named tuple, using index: 0.00265598297119 Class using __slots__, with a, b, c: 0.00208616256714 Dictionary with keys a, b, c: 0.013897895813 Tuple with three values, using a constant key: 0.00275301933289 List with three values, using a constant key: 0.002760887146 Tuple with three values, using a local key: 0.002769947052 List with three values, using a local key: 0.00278806686401 

Un par de puntos e ideas:

1) Estás sincronizando el acceso al mismo índice muchas veces seguidas. Su progtwig real probablemente utiliza acceso aleatorio o lineal, que tendrá un comportamiento diferente. En particular, habrá más errores de caché de CPU. Puede obtener resultados ligeramente diferentes utilizando su progtwig real.

2) OrderedDictionary se escribe como un envoltorio alrededor de dict , ergo será más lento que dict . Eso no es una solución.

3) ¿Has probado clases de estilo nuevo y antiguo? (las clases de estilo nuevo se heredan del object ; las clases de estilo antiguo no lo hacen)

4) ¿Ha intentado usar psyco o Unladen Swallow ?

5) ¿Su bucle interno para modificar los datos o simplemente acceder a ellos? Podría ser posible transformar los datos en la forma más eficiente posible antes de ingresar al bucle, pero usar la forma más conveniente en otra parte del progtwig.

Me sentiría tentado a (a) inventar algún tipo de almacenamiento en caché específico de la carga de trabajo y descargar el almacenamiento y recuperación de mis datos a un proceso similar a memcachedb, para mejorar la escalabilidad en lugar del rendimiento solo o (b) reescribir como una extensión C, Con almacenamiento de datos nativos. Un tipo de diccionario ordenado tal vez.

Puede comenzar con esto: http://www.xs4all.nl/~anthon/Python/ordereddict/

Puedes hacer que tus clases se secuencian agregando los __iter__ , y __getitem__ , para hacer que la secuencia sea similar (indexable e iterable).

¿ OrderedDict un OrderedDict ? Hay varias implementaciones disponibles, y se incluye en el módulo de collections Python31.