¿Cuál es el objeto similar a una estructura más rápido (de acceso) en Python?

Question

Estoy optimizando algún código cuyo cuello de botella principal se está ejecutando y accediendo a una lista muy grande de objetos similares a estructuras. Actualmente estoy usando namedtuples, para la legibilidad. Sin embargo, algunos de evaluación comparativa rápida usando 'timeit' muestra que este es realmente el camino equivocado donde el rendimiento es un factor:

tupla nombre con a, b, c:

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

Clase usando __slots__, con una , b, c:

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

diccionario con claves 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 

tupla con tres valores, utilizando una clave local:

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

Lista con tres valores, usando una clave local:

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

En primer lugar, ¿hay algo acerca de estas pequeñas pruebas timeit que las invalidaría? Corrí varias veces para asegurarme de que ningún evento aleatorio del sistema los hubiera descartado, y los resultados fueron casi idénticos.

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

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

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

Answer 1

Una cosa a tener en cuenta es que las listas con nombre están optimizadas para el acceso como tuplas. Si cambia su acceso para ser a[2] en lugar de a.c, verá un rendimiento similar a las tuplas. La razón es que los accesadores de nombre se están traduciendo de manera efectiva en llamadas a self [idx], así que pague a la indexación y el precio de búsqueda de nombre.

Si su patrón de uso es tal que el acceso de nombre es común, pero el acceso como tupla no es así, podría escribe un equivalente rápida a namedtuple que hace las cosas de la manera opuesta: aplaza operaciones de búsqueda de índice para el acceso de nombre . Sin embargo, pagará el precio en las búsquedas de índice entonces. Por ejemplo, he aquí una rápida implementación:

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 están muy mal cuando __getitem__ debe llamarse:

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 acceder atributo (como era de esperar - que es lo que se es), pero enormes sanciones debido a la doble búsqueda en los accesos basados ​​en índices. (Cabe destacar que __slots__ en realidad no ayuda mucho 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 ej. subclase de la lista y almacena los valores tanto en los atributos como en los datos de la lista. Sin embargo, en realidad no obtienes un rendimiento equivalente a la lista. Hay un gran golpe de velocidad solo por haber subclasificado (trayendo cheques por sobrecargas de python puro). Por lo tanto, struct [0] aún tarda alrededor de 0,5 s (en comparación con 0.18 para la lista sin formato) en este caso, y se duplica el uso de la memoria, por lo que puede no valer la pena.

Answer 2

Me sentiría tentado a (a) inventar algún tipo de caché específico de 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.

Se podría empezar con esto: http://www.xs4all.nl/~anthon/Python/ordereddict/

Answer 3

Usted puede hacer su secuencia de clases como mediante la adición de __iter__ y __getitem__ métodos, para que sean seguidas, como si

qué un trabajo OrderedDict (indexable y iterable). ? Hay varias implementaciones disponibles, y está incluida en el módulo Python31 collections.

Answer 4

un par de puntos e ideas:

1) Estás sincronización acceder al mismo índice muchas veces en una fila. Su programa real probablemente use acceso aleatorio o lineal, que tendrá un comportamiento diferente. En particular, habrá más errores de caché de la CPU. Es posible que obtenga resultados ligeramente diferentes con su programa real.

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

3) ¿Has probado tanto las clases de estilo nuevo como las antiguas? (las clases de nuevo estilo heredan de object; las clases de estilo antiguo no)

4) ¿Ha intentado usar psyco o Unladen Swallow?

5) ¿Su bucle interior modifica los datos o simplemente accede a ellos? Es posible transformar los datos en la forma más eficiente posible antes de ingresar al ciclo, pero use la forma más conveniente en cualquier otro lugar del programa.

Answer 5

Esta pregunta es bastante antigua (internet-time), así que pensé en intentar duplicar la prueba hoy, tanto con CPython regular (2.7.6), y con pypy (2.2.1) y ver cómo los diferentes métodos comparados. (También agregué en una búsqueda indexada para la tupla nombrada.)

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

from collections import namedtuple 

STest = namedtuple("TEST", "a b c") 
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 = a.c", "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 = b.c", "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")) 

Python Resultados:

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 

PyPy Resultados:

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