Problemas en la implementación del método de Horner en Python

function loops

Question

Así que he escrito los códigos para evaluar el polinomio usando tres métodos diferentes. El método de Horner debería ser el más rápido, mientras que el método ingenuo debería ser el más lento, ¿verdad? Pero, ¿cómo ha llegado el momento de la informática, no es lo que espero? Y el tiempo de cálculo a veces resulta ser exactamente el mismo para el método iter e ingenuo. ¿Qué tiene de malo?

import numpy.random as npr
import time

def Horner(c,x):
    p=0
    for i in c[-1::-1]:
        p = p*x+i
    return p

def naive(c,x):
    n = len(c)
    p = 0
    for i in range(len(c)):
        p += c[i]*x**i 
    return p

def itera(c,x):
    p = 0
    xi = 1
    for i in range(len(c)):
        p += c[i]*xi
        xi *= x 
    return p

c=npr.uniform(size=(500,1))
x=-1.34

start_time=time.time()
print Horner(c,x)
print time.time()-start_time

start_time=time.time()
print itera(c,x)
print time.time()-start_time

start_time=time.time()
print naive(c,x)
print time.time()-start_time

Aquí están algunos de los resultados:

[  2.58646959e+69]
0.00699996948242
[  2.58646959e+69]
0.00600004196167
[  2.58646959e+69]
0.00600004196167

[ -3.30717922e+69]
0.00899982452393
[ -3.30717922e+69]
0.00600004196167
[ -3.30717922e+69]
0.00600004196167

[ -2.83469309e+69]
0.00999999046326
[ -2.83469309e+69]
0.00999999046326
[ -2.83469309e+69]
0.0120000839233

Answer 1

No puedes obtener un resultado preciso midiendo cosas como esas:

start_time=time.time()
print Horner(c,x)
print time.time()-start_time

Presumiblemente, la mayor parte del tiempo se gasta en la función IO involucrada por la función de print . Además, para tener algo importante, debe realizar la medida en un gran número de iteraciones para suavizar los errores. En el caso general, es posible que desee realizar su prueba en varios datos de entrada también, ya que dependiendo de su algoritmo, algunos casos podrían resolverse de manera más eficiente que otros.

Definitivamente deberías echar un vistazo al módulo timeit . Algo así, tal vez:

import timeit
print ''Horner'',timeit.timeit(stmt=''Horner(c,x)'', 
                  setup=''from __main__ import Horner, c, x'',
                  number = 10000)
#                          ^^^^^
#                probably not enough. Increase that once you will
#                be confident

print ''naive'',timeit.timeit(stmt=''naive(c,x)'', 
                  setup=''from __main__ import naive, c, x'',
                  number = 10000)
print ''itera'',timeit.timeit(stmt=''itera(c,x)'', 
                  setup=''from __main__ import itera, c, x'',
                  number = 10000)

Produciendo esto en mi sistema:

Horner 23.3317809105
naive 28.305519104
itera 24.385917902

Pero aún con resultados variables de en ejecución a la otra:

Horner 21.1151690483
naive 23.4374330044
itera 21.305426836

Como dije antes, para obtener resultados más significativos, debe aumentar definitivamente el número de pruebas y ejecutarlas en varios casos de prueba para suavizar los resultados.

Answer 2

Si está haciendo una gran cantidad de evaluaciones comparativas, computación científica, trabajo relacionado con muchos y muchos más, usar ipython será una herramienta extremadamente útil.

Para comparar, puede programar el código con timeit usando ipython magic, donde obtendrá resultados más consistentes en cada ejecución, es simplemente una cuestión de usar timeit luego la función o el código para timeit :

In [28]: timeit Horner(c,x)
1000 loops, best of 3: 670 µs per loop

In [29]: timeit naive(c,x)
1000 loops, best of 3: 983 µs per loop

In [30]: timeit itera(c,x)
1000 loops, best of 3: 804 µs per loop

Para codificar el tiempo que abarca más de una línea, simplemente use %%timeit :

In [35]: %%timeit
   ....: for i in range(100):
   ....:     i ** i
   ....: 
10000 loops, best of 3: 110 µs per loop

ipython puede compilar código cython , código f2py y hacer muchas otras tareas muy útiles utilizando diferentes complementos y comandos mágicos ipython.

comandos de magia incorporados

Utilizando cython y algunas mejoras muy básicas, podemos mejorar la eficiencia de Horner en aproximadamente un 25 por ciento:

In [166]: %%cython
import numpy as np
cimport numpy as np
cimport cython
ctypedef np.float_t DTYPE_t
def C_Horner(c, DTYPE_t x):
    cdef DTYPE_t p
    for i in reversed(c):
        p = p * x + i
    return p   

In [28]: c=npr.uniform(size=(2000,1))

In [29]: timeit Horner(c,-1.34)
100 loops, best of 3: 3.93 ms per loop
In [30]: timeit C_Horner(c,-1.34)
100 loops, best of 3: 2.21 ms per loop

In [31]: timeit itera(c,x)
100 loops, best of 3: 4.10 ms per loop
In [32]: timeit naive(c,x)
100 loops, best of 3: 4.95 ms per loop

El uso de la lista en @Paul drapers responde a nuestra versión citonizada que se ejecuta dos veces más rápido que la función original y mucho más rápido que ietra e ingenuo:

In [214]: import random

In [215]: c = [random.random() for _ in range(500)]

In [44]: timeit C_Horner(c, -1.34)
10000 loops, best of 3: 18.9 µs per loop    
In [45]: timeit Horner(c, -1.34)
10000 loops, best of 3: 44.6 µs per loop
In [46]: timeit naive(c, -1.34)
10000 loops, best of 3: 167 µs per loop
In [47]: timeit itera(c,-1.34)
10000 loops, best of 3: 75.8 µs per loop

Answer 3

Su perfil puede ser mejorado mucho. Además, podemos hacer que su código se ejecute 200-500x más rápido.

(1) Enjuague y repita

No puede ejecutar solo una iteración de una prueba de rendimiento, por dos razones.

1. Su resolución de tiempo podría no ser lo suficientemente buena. Esta es la razón por la que a veces obtuviste el mismo tiempo para dos implementaciones: el tiempo para una ejecución estuvo cerca de la resolución de tu mecanismo de tiempo, por lo que solo registraste una "marca".
2. Hay todo tipo de factores que afectan el rendimiento. Tu mejor apuesta para una comparación significativa serán muchas iteraciones.

No necesita millones de carreras (aunque, por supuesto, eso no duele), pero estima y ajusta el número de iteraciones hasta que la variación esté dentro de un nivel aceptable para su propósito.

timeit es un pequeño módulo para perfilar el código Python.

Agregué esto al final de tu guión.

import timeit

n = 1000

print ''Horner'', timeit.timeit(
    number = n,
    setup=''from __main__ import Horner, c, x'',
    stmt=''Horner(c,x)''
)
print ''naive'', timeit.timeit(
    number = n,
    setup=''from __main__ import naive, c, x'',
    stmt=''naive(c,x)'', 
)
print ''itera'', timeit.timeit(
    number = n,
    setup=''from __main__ import itera, c, x'',
    stmt=''itera(c,x)'', 
)

Lo que produce

Horner 1.8656351566314697
naive 2.2408010959625244
itera 1.9751169681549072

Horner es el más rápido, pero no es exactamente volar las puertas de los otros dos.

(2) Mira lo que está pasando ... con mucho cuidado.

Python tiene una sobrecarga de operadores, por lo que es fácil no ver esto.

npr.uniform(size=(500,1)) te da una estructura de números aleatorios de 500 x 1.

¿Y qué?

Bueno, c[i] no es un número. Es una matriz numpy con un elemento. Numpy sobrecarga a los operadores para que puedas hacer cosas como multiplicar una matriz por un escalar.

Eso está bien, pero usar una matriz para cada elemento implica una gran sobrecarga, por lo que es más difícil ver la diferencia entre los algoritmos.

En su lugar, vamos a probar una simple lista de Python:

import random
c = [random.random() for _ in range(500)]

Y ahora,

Horner 0.034661054611206055
naive 0.12771987915039062
itera 0.07331395149230957

Whoa! Todos los tiempos se volvieron más rápidos (de 10 a 60 veces). Proporcionalmente, la implementación de Horner fue incluso más rápida que las otras dos. Eliminamos los gastos generales en los tres, y ahora podemos ver la diferencia de "huesos desnudos".

Horner es 4 veces más rápido que ingenuo y 2 veces más rápido que itera.

(3) tiempos de ejecución alternativos

Estás usando Python 2. Supongo que 2.7.

Veamos cómo le va a Python 3.4. (Ajuste de sintaxis: deberá colocar paréntesis alrededor de la lista de argumentos para print ).

Horner 0.03298933599944576
naive 0.13706714100044337
itera 0.06771054599812487

Sobre lo mismo.

Probemos con PyPy , una implementación JIT de Python. (La implementación "normal" de Python se llama CPython).

Horner 0.006507158279418945
naive 0.07541298866271973
itera 0.005059003829956055

¡Bonito! Cada implementación ahora se ejecuta de 2 a 5 veces más rápido. Horner es ahora 10 veces la velocidad de un ingenuo, pero un poco más lento que itera.

Los tiempos de ejecución JIT son más difíciles de perfilar que los intérpretes. Aumentemos el número de iteraciones a 50000 e intentemos solo para asegurarnos.

Horner 0.12749004364013672
naive 3.2823100090026855
itera 0.06546688079833984

(Tenga en cuenta que tenemos 50 veces las iteraciones, pero solo 20 veces el tiempo ... el JIT no había tenido pleno efecto en muchas de las primeras 1000 ejecuciones). Las mismas conclusiones, pero las diferencias son aún más pronunciadas.

Por supuesto, la idea de JIT es crear un perfil, analizar y reescribir el programa en tiempo de ejecución, por lo que si su objetivo es comparar algoritmos, esto agregará muchos detalles de implementación no obvios.

No obstante, la comparación de tiempos de ejecución puede ser útil para dar una perspectiva más amplia.

Hay algunas cosas más. Por ejemplo, su implementación ingenua calcula una variable que nunca usa. xrange range lugar de xrange . Puede intentar iterando hacia atrás con un índice en lugar de un sector inverso. Etc.

Ninguno de estos cambió mucho los resultados para mí, pero valió la pena considerarlos.