Optimización de una función de partición

Question

Aquí está el código, en python:

# function for pentagonal numbers 
def pent (n):  return int((0.5*n)*((3*n)-1)) 

# function for generalized pentagonal numbers 
def gen_pent (n): return pent(int(((-1)**(n+1))*(round((n+1)/2)))) 

# array for storing partitions - first ten already stored 
partitions = [1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42] 

# function to generate partitions 
def partition (k): 
if (k < len(partitions)): return partitions[k] 

total, sign, i = 0, 1, 1 

while (k - gen_pent(i)) >= 0: 
    sign = (-1)**(int((i-1)/2)) 
    total += sign*(partition(k - gen_pent(i))) 
    i  += 1 

partitions.insert(k,total) 
return total 

Se utiliza este método para calcular las particiones:

p(k) = p(k − 1) + p(k − 2) − p(k − 5) − p(k − 7) + p(k − 12) + p(k − 15) ... 

(fuente: Wikipedia)

Sin embargo, el código toma bastante tiempo cuando se trata de números grandes (sobre p (10^3)). Quiero preguntarte si puedo optimizar mi código o darme pistas sobre un algoritmo o enfoque diferente pero más rápido. Cualquier sugerencia de optimización es bienvenida.

Y no, antes de preguntar, esto no es para tareas o Proyecto Euler, es por el valor de la experiencia.

Answer 1

Aquí hay algunos comentarios. Tenga en cuenta que no soy un experto en esto, por lo que también me gusta jugar con las matemáticas (y Project Euler).

que han redefinido las funciones de números pentagonales de la siguiente manera:

def pent_new(n): 
    return (n*(3*n - 1))/2 

def gen_pent_new(n): 
    if n%2: 
     i = (n + 1)/2 
    else: 
     i = -n/2 
    return pent_new(i) 

las he escrito de tal manera que no me presento cálculos de punto flotante - n para grandes usando flotadores introducirán errores (comparar la resultados para n = 100000001).

Puede usar el módulo timeit para probar pequeños fragmentos de código. Cuando probé todas las funciones pentagonales (la tuya y la mía), los resultados de la mía fueron más rápidos. El siguiente es un ejemplo que prueba la función gen_pent.

# Add this code to your script 
t = Timer("for i in xrange(1, 100): gen_pent(i)", "from __main__ import gen_pent") 
print t.timeit() 

Aquí hay una ligera modificación de la función partition. Una vez más, probar con timeit muestra que es más rápido que su función partition. Sin embargo, esto puede deberse a las mejoras realizadas en las funciones numéricas pentagonales.

def partition_new(n): 
    try: 
     return partitions_new[n] 
    except IndexError: 
     total, sign, i = 0, 1, 1 
     k = gen_pent_new(i) 
     while n - k >= 0: 
      total += sign*partition_new(n - k) 

      i += 1 
      if i%2: sign *= -1 
      k = gen_pent_new(i) 

     partitions_new.insert(n, total) 
     return total 

En su función de partición, calcula el número pentagonal general dos veces para cada ciclo. Una vez para probar en el estado de tiempo, y la otra para actualizar total. Guardo el resultado en una variable, así que solo haga el cálculo una vez por ciclo.

Usando el módulo cProfile (para python> = 2.5, de lo contrario, el módulo de perfil) puede ver dónde gasta su código la mayor parte del tiempo. Aquí hay un ejemplo basado en su función de partición.

import cProfile 
import pstats 

cProfile.run('partition(70)', 'partition.test') 
p = pstats.Stats('partition.test') 
p.sort_stats('name') 
p.print_stats() 

Esto produce la siguiente salida en la ventana de la consola:

C:\Documents and Settings\ags97128\Desktop>test.py 
Fri Jul 02 12:42:15 2010 partition.test 

     4652 function calls (4101 primitive calls) in 0.015 CPU seconds 

    Ordered by: function name 

    ncalls tottime percall cumtime percall filename:lineno(function) 
     552 0.001 0.000 0.001 0.000 {len} 
     1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 
     60 0.000 0.000 0.000 0.000 {method 'insert' of 'list' objects} 
     1 0.000 0.000 0.015 0.015 <string>:1(<module>) 
    1162 0.002 0.000 0.002 0.000 {round} 
    1162 0.006 0.000 0.009 0.000 C:\Documents and Settings\ags97128\Desktop\test.py:11(gen_pent) 
    552/1 0.005 0.000 0.015 0.015 C:\Documents and Settings\ags97128\Desktop\test.py:26(partition) 
    1162 0.002 0.000 0.002 0.000 C:\Documents and Settings\ags97128\Desktop\test.py:5(pent) 

Ahora perfiles mi función de partición:

Fri Jul 02 12:50:10 2010 partition.test 

     1836 function calls (1285 primitive calls) in 0.006 CPU seconds 

    Ordered by: function name 

    ncalls tottime percall cumtime percall filename:lineno(function) 
     1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 
     60 0.000 0.000 0.000 0.000 {method 'insert' of 'list' objects} 
     1 0.000 0.000 0.006 0.006 <string>:1(<module>) 
     611 0.002 0.000 0.003 0.000 C:\Documents and Settings\ags97128\Desktop\test.py:14(gen_pent_new) 
    552/1 0.003 0.000 0.006 0.006 C:\Documents and Settings\ags97128\Desktop\test.py:40(partition_new) 
     611 0.001 0.000 0.001 0.000 C:\Documents and Settings\ags97128\Desktop\test.py:8(pent_new) 

se puede ver en los resultados de mi no hay llamadas a la len y round funciones integradas.Y casi he reducido a la mitad el número de llamadas a las funciones pentagonales (gen_pent_new y pent_new)

Probablemente haya otros trucos para mejorar la velocidad del código python. Buscaría aquí 'optimización de Python' para ver lo que puede encontrar.

Finalmente, uno de los enlaces en la parte inferior de la página de wikipedia que mencionó es academic paper en algoritmos rápidos para calcular números de partición. Un vistazo rápido muestra que contiene pseudocódigo para los algoritmos. Estos algoritmos probablemente serán más rápidos que cualquier cosa que usted o yo pudiéramos producir.