Mejor técnica de optimización usando if/else o el diccionario

Question

¿Cuál es la mejor optimización?

• Una serie de instrucción if/else que recibe la 'cadena' devuelve la función apropiada para ella. (Alrededor de 40-50 declaraciones if/else).
• Un diccionario que mantiene el par clave-valor. clave como cadenas, y valores como objetos de función, y una función principal para buscar y devolver el objeto de función.

La función principal que realmente devuelve el objeto de función utilizando el método anterior se llamaría millones o miles de millones de veces, por lo que debe hacerlo de forma inteligente. ¿Cuál podría ser la mejor manera?

Por ej.

dict['str1'] = func1 
dict['str2'] = func2 
and so on.. 

def main_func(str): 
    return dict[str] 

O

def main_func(str): 
    if 'str1': 
     return func1 
    elif 'str2': 
     return func2 

Lo que sería mejor ..? si tenemos 50-60 de estas cadenas, y este proceso debe ser miles de millones de veces.

Almacenamiento objeto de función dentro de diccionario, en función de sí mismo: -

def func1(): 
    if dict.has_key('str1'): 
     dict['str1'] = func1 
    -- do something -- 

¿Qué es mejor, si esto o la de arriba. Esto se ve mucho más limpio. Pero recuerde, estas funciones se llamarían muchas veces, por lo que la función has_key también se llamaría muchas veces.

Gracias

Answer 1

Elija el diccionario.

El diccionario ...

• está incorporado en
• es Pythonic
• requiere código menos repetitivo
• ha O (1) la complejidad, comparado con el lineal o Si-else (n) la complejidad
• no es culpable de pesimismo prematuro (no tenemos razones suficientes para creer sin un perfil que es un método menos eficiente por un amplio margen)

Sugeriría escribir el solución usando primero un diccionario y viendo si la solución es lo suficientemente rápida para sus necesidades. Si es así, genial, ya terminaste. Si no, compárelo en la otra dirección.

Considérese una solución de este tipo (que devolverá None si no se encuentra la cadena):

func_dict = {} 
func_dict['str1'] = fun1 
func_dict['str2'] = fun2 
... 
def function_lookup(func_string): 
    return func_dict.get(func_string) 

Luego, en su principal, sólo tiene que escribir function_lookup(whatever_string_variable) para intentar una búsqueda para su función. Esto evita que se reconstruya el diccionario cada vez que se llama al function_lookup.

Answer 2

Técnicamente, depende del rendimiento de hash de colisión, pero me imagino que el almacenamiento de todos los datos en un hash y la recuperación sería ligeramente más rápido.

En cualquier caso, la diferencia probablemente no sea enorme de ninguna manera. Ciertamente, la solución hashtable es más limpia, así que lo recomendaría.

La mejor manera de saberlo con certeza es escribir ambas versiones y probarlas con una gran cantidad de datos y medir su rendimiento.

Answer 3

Diccionario es mejor. El diccionario debe estar respaldado por un árbol/hashmap y tiene una mejor complejidad de tiempo que la instrucción if-else (que es aproximadamente lineal). Incluso si el tiempo de ejecución real no es mejor, el código estará más limpio con el diccionario.

Answer 4

Los diccionarios son una de las partes muy afinadas de python. Ellos producen un código más legible. Deben tener un mejor rendimiento que sus bucles if. Sin embargo, teniendo en cuenta la inserción y otros gastos generales, le sugiero que utilice el módulo timeit y verifique el rendimiento.

Answer 5

El diccionario será más rápido: es aproximadamente O (1), mientras que la cadena de enunciados if es O (n). Para demostrarlo, esta secuencia de comandos (make_test.py) es la salida de un script en Python que ejecuta algunas pruebas peformance:

dict: 0.706176042557 
if: 1.67383503914 

Es decir, la versión if es más que:

ifs = [] 
dict = [] 
for i in range(60): 
    string = 'str%d' % i 
    ifs.append(' %sif str == "%s": return %d' % ('el' if i else '', string, i)) 
    dict.append('"%s": %d' % (string, i)) 

print 'dict = {', ','.join(dict), '}' 
print 'def with_dict(str):' 
print ' return dict[str]' 

print 'def with_if(str):' 
print '\n'.join(ifs) 

print ''' 
import timeit 

def test_dict(): 
    for i in range(60): 
     with_dict("str%d" % i) 

def test_if(): 
    for i in range(60): 
     with_if("str%d" %i) 

print 'dict:', timeit.timeit(test_dict, number=10000) 
print 'if: ', timeit.timeit(test_if, number=10000)''' 

ejecutándolo como python make_test.py | python, me da 2 veces más lento que la versión dict.

Answer 6

La complejidad de tiempo promedio para dict lookup es O (1). El peor caso es O (n). Hay optimizaciones para diccionarios con solo teclas str (su caso de uso).

Suponiendo que el orden de las pruebas en la escala if/else no puede optimizarse en función de la frecuencia de la entrada (por ejemplo, 60 posibilidades, 2 de las cuales ocurren el 95% del tiempo), la complejidad de una serie de las sentencias if/else son O (n).

Por lo tanto, un diccionario ofrecerá un mejor rendimiento y una mejor legibilidad del código.

Answer 7

Que cada solución se ve más elegante y más fácil de mantener.

Es más importante, en la mayoría de los programas de aplicaciones, optimizar el tiempo humano y el mantenimiento, entonces es para optimizar el tiempo de la computadora. El tiempo de la computadora es barato. El tiempo humano es caro

Ambas soluciones tienen sus ventajas.

La solución if/elif puede proporcionar más flexibilidad si necesita agregar flujo de control más tarde, como if/else anidado.

Si los datos provienen directamente de una fuente de datos como yaml o una base de datos, entonces claramente la solución dict es más elegante.