python - dict to ordereddict

OrderedDict vs defaultdict vs dict

Question

En la biblioteca de Python, ahora tenemos dos implementaciones de Python de diccionarios cuyas subclases dict más allá del tipo de dict nativo.

Los defensores de Python siempre han preferido el dict.setdefault en dict.setdefault usar dict.setdefault cuando sea posible. Incluso el doc cita que This technique is simpler and faster than an equivalent technique using dict.setdefault():

De manera similar, dado que los diccionarios no mantienen el orden, es OrderedDict usar OrderedDict sobre el uso de dict seguido de ordenar los elementos, siempre que sea posible para el uso alternativo.

En ambos casos, el código es definitivamente más limpio, pero a costa de una penalización de rendimiento.

Mientras respondía y comentaba una de las preguntas de la lista única de Python basada en un ítem , me topé con la penalización de rendimiento sobre el dict nativo al usar defaultdict y OrderedDict . También parece que el tamaño de los datos tampoco es inmaterial para la ventaja de rendimiento que la solución dict tiene sobre otros.

Creo que There should be one-- and preferably only one --obvious way to do it. , entonces, ¿cuál es la forma preferida?

Answer 1

No hay una sola respuesta ni un solo dict verdadero y único. Entre muchas variables, depende de:

1. Tamaño del conjunto de datos;
2. Número de claves únicas
3. Velocidad de la fábrica subyacente para el incumplimiento;
4. Velocidad de OrderDict vs algún paso posterior de pedido;
5. Versión de Python.

No me gusta generalizar, pero he aquí algunas generalidades:

1. La declaración This technique is simpler and faster than an equivalent technique using dict.setdefault() simplemente está mal. Depende de los datos;
2. setdefault es más rápido y simple con pequeños conjuntos de datos;
3. defaultdict es más rápido para conjuntos de datos más grandes con conjuntos de claves más homogéneos;
4. setdefault tiene una ventaja con conjuntos de claves más heterogéneas;
5. estos resultados son diferentes para Python 3 vs Python 2;
6. OrderedDict es más lento en todos los casos que no sea un algoritmo que depende del orden y el orden no es fácil de reconstruir o ordenar;
7. Python 3 generalmente es más rápido para la mayoría de las operaciones de dict ;
8. El dict de Python 3.6 ahora está ordenado por orden de inserción.

La única verdad: ¡Depende! Las tres técnicas son útiles.

Aquí hay un código de tiempo para mostrar:

from __future__ import print_function
from collections import defaultdict
from collections import OrderedDict

try:
    t=unichr(100)
except NameError:
    unichr=chr

def f1(li):
    ''''''defaultdict''''''
    d = defaultdict(list)
    for k, v in li:
        d[k].append(v)
    return d.items()

def f2(li):
    ''''''setdefault''''''
    d={}
    for k, v in li:
        d.setdefault(k, []).append(v)
    return d.items()

def f3(li):
    ''''''OrderedDict''''''
    d=OrderedDict()
    for k, v in li:
        d.setdefault(k, []).append(v)
    return d.items()      


if __name__ == ''__main__'':
    import timeit
    import sys
    print(sys.version)
    few=[(''yellow'', 1), (''blue'', 2), (''yellow'', 3), (''blue'', 4), (''red'', 1)]
    fmt=''{:>12}: {:10.2f} micro sec/call ({:,} elements, {:,} keys)''
    for tag, m, n in [(''small'',5,10000), (''medium'',20,1000), (''bigger'',1000,100), (''large'',5000,10)]:
        for f in [f1,f2,f3]:
            s = few*m
            res=timeit.timeit("{}(s)".format(f.__name__), setup="from __main__ import {}, s".format(f.__name__), number=n)
            st=fmt.format(f.__doc__, res/n*1000000, len(s), len(f(s)))
            print(st)
            s = [(unichr(i%0x10000),i) for i in range(1,len(s)+1)]
            res=timeit.timeit("{}(s)".format(f.__name__), setup="from __main__ import {}, s".format(f.__name__), number=n)
            st=fmt.format(f.__doc__, res/n*1000000, len(s), len(f(s)))
            print(st)            
        print() 

Resultado de Python 2.7:

2.7.5 (default, Aug 25 2013, 00:04:04) 
[GCC 4.2.1 Compatible Apple LLVM 5.0 (clang-500.0.68)]
 defaultdict:      10.20 micro sec/call (25 elements, 3 keys)
 defaultdict:      21.08 micro sec/call (25 elements, 25 keys)
  setdefault:      13.41 micro sec/call (25 elements, 3 keys)
  setdefault:      18.24 micro sec/call (25 elements, 25 keys)
 OrderedDict:      49.47 micro sec/call (25 elements, 3 keys)
 OrderedDict:     102.16 micro sec/call (25 elements, 25 keys)

 defaultdict:      28.28 micro sec/call (100 elements, 3 keys)
 defaultdict:      79.78 micro sec/call (100 elements, 100 keys)
  setdefault:      45.68 micro sec/call (100 elements, 3 keys)
  setdefault:      68.66 micro sec/call (100 elements, 100 keys)
 OrderedDict:     117.78 micro sec/call (100 elements, 3 keys)
 OrderedDict:     343.17 micro sec/call (100 elements, 100 keys)

 defaultdict:    1123.60 micro sec/call (5,000 elements, 3 keys)
 defaultdict:    4250.44 micro sec/call (5,000 elements, 5,000 keys)
  setdefault:    2089.86 micro sec/call (5,000 elements, 3 keys)
  setdefault:    3803.03 micro sec/call (5,000 elements, 5,000 keys)
 OrderedDict:    4399.16 micro sec/call (5,000 elements, 3 keys)
 OrderedDict:   16279.14 micro sec/call (5,000 elements, 5,000 keys)

 defaultdict:    5609.39 micro sec/call (25,000 elements, 3 keys)
 defaultdict:   25351.60 micro sec/call (25,000 elements, 25,000 keys)
  setdefault:   10267.00 micro sec/call (25,000 elements, 3 keys)
  setdefault:   24091.51 micro sec/call (25,000 elements, 25,000 keys)
 OrderedDict:   22091.98 micro sec/call (25,000 elements, 3 keys)
 OrderedDict:   94028.00 micro sec/call (25,000 elements, 25,000 keys)

Resultado de Python 3.3:

3.3.2 (default, May 21 2013, 11:50:47) 
[GCC 4.2.1 Compatible Apple Clang 4.1 ((tags/Apple/clang-421.11.66))]
 defaultdict:       8.58 micro sec/call (25 elements, 3 keys)
 defaultdict:      21.18 micro sec/call (25 elements, 25 keys)
  setdefault:      10.42 micro sec/call (25 elements, 3 keys)
  setdefault:      14.58 micro sec/call (25 elements, 25 keys)
 OrderedDict:      45.43 micro sec/call (25 elements, 3 keys)
 OrderedDict:      92.69 micro sec/call (25 elements, 25 keys)

 defaultdict:      20.47 micro sec/call (100 elements, 3 keys)
 defaultdict:      77.48 micro sec/call (100 elements, 100 keys)
  setdefault:      34.22 micro sec/call (100 elements, 3 keys)
  setdefault:      54.86 micro sec/call (100 elements, 100 keys)
 OrderedDict:     107.37 micro sec/call (100 elements, 3 keys)
 OrderedDict:     318.98 micro sec/call (100 elements, 100 keys)

 defaultdict:     714.70 micro sec/call (5,000 elements, 3 keys)
 defaultdict:    3892.92 micro sec/call (5,000 elements, 5,000 keys)
  setdefault:    1502.91 micro sec/call (5,000 elements, 3 keys)
  setdefault:    2888.08 micro sec/call (5,000 elements, 5,000 keys)
 OrderedDict:    3912.95 micro sec/call (5,000 elements, 3 keys)
 OrderedDict:   14863.02 micro sec/call (5,000 elements, 5,000 keys)

 defaultdict:    3649.02 micro sec/call (25,000 elements, 3 keys)
 defaultdict:   22313.17 micro sec/call (25,000 elements, 25,000 keys)
  setdefault:    7447.28 micro sec/call (25,000 elements, 3 keys)
  setdefault:   18426.88 micro sec/call (25,000 elements, 25,000 keys)
 OrderedDict:   19202.17 micro sec/call (25,000 elements, 3 keys)
 OrderedDict:   85946.45 micro sec/call (25,000 elements, 25,000 keys)

Answer 2

Siento que su suposición, solo una forma preferible , no es válida. Veo al menos dos casos con diferentes requisitos:

En el código de mantenimiento intensivo (por ejemplo, un analizador de opciones de una clase de utilidad en evolución), siempre buscaría un código más limpio , para que otros y yo podamos implementar nuevas características más fácilmente. El rendimiento no es crítico, ya que solo se procesan pequeñas cantidades (por ejemplo, un dict de la configuración del usuario).

mientras en

la implementación de un algoritmo de rendimiento crítico en una tarea de procesamiento de datos, no me importaría escribir un código más detallado para una ejecución mucho más rápida . Si es poco probable que el aloritmo cambie, el código poco menos legible no se convertirá en un problema.