python: generación de particiones enteras

Question

Necesito generar todos los partitions de un número entero dado.
me encontré con este algoritmo por Jerome Kelleher para el que se dice que es el más eficiente uno:

def accelAsc(n): 
    a = [0 for i in range(n + 1)] 
    k = 1 
    a[0] = 0 
    y = n - 1 
    while k != 0: 
     x = a[k - 1] + 1 
     k -= 1 
     while 2*x <= y: 
      a[k] = x 
      y -= x 
      k += 1 
     l = k + 1 
     while x <= y: 
      a[k] = x 
      a[l] = y 
      yield a[:k + 2] 
      x += 1 
      y -= 1 
     a[k] = x + y 
     y = x + y - 1 
     yield a[:k + 1] 

referencia: http://homepages.ed.ac.uk/jkellehe/partitions.php

Por cierto, no es muy eficiente. Para una entrada como 40, congela casi todo el sistema durante unos segundos antes de dar su salida.

Si fuera un algoritmo recursivo, trataría de decorarlo con una función de almacenamiento en caché o algo para mejorar su eficacia, pero siendo así no puedo imaginar qué hacer.

¿Tiene alguna sugerencia sobre cómo acelerar este algoritmo? ¿O puede sugerirme otro, o un enfoque diferente para hacer otro desde cero?

Answer 1

Si va a utilizar esta función en repetidas ocasiones por el mismo entradas, aún podría valer la caché de los valores de retorno (si va a utilizarlo en distintas ejecuciones, puede almacenar los resultados en un archivo).

Si no puede encontrar un algoritmo significativamente más rápido, entonces debería ser posible acelerarlo en un orden de magnitud o dos moviendo el código a una extensión C (probablemente sea más fácil usando cython), o alternativamente usando PyPy en lugar de CPython (PyPy tiene sus inconvenientes: todavía no es compatible con Python 3, o algunas bibliotecas de uso común como numpy y scipy).

La razón de esto es que, dado que python se tipea dinámicamente, el intérprete probablemente esté pasando la mayor parte del tiempo comprobando los tipos de variables; para todo el intérprete, una de las operaciones podría convertir x en una cadena, en qué expresiones de casos como x + y tendrían de repente significados muy diferentes. Cython soluciona este problema permitiéndole declarar estáticamente las variables como enteros, mientras que PyPy tiene un just-in-time compiler que minimiza las comprobaciones de tipos redundantes.

Answer 2

Diría que su problema de rendimiento está en otro lugar.

no me comparo con otros enfoques, pero parece eficiente para mí:

import time 

start = time.time() 
partitions = list(accelAsc(40)) 
print('time: {:.5f} sec'.format(time.time() - start)) 
print('length:', len(partitions)) 

Gave:

time: 0.03636 sec 
length: 37338 

Answer 3

Testing con n = 75 consigo:

PyPy 1,8:

w:\>c:\pypy-1.8\pypy.exe pstst.py 
1.04800009727 secs. 

CPython 2,6:

w:\>python pstst.py 
5.86199998856 secs. 

Cython + MinGW + gcc 4.6.2:

w:\pstst> python -c "import pstst;pstst.run()" 
4.06399989128 

No vi ninguna diferencia con Psyco (?)

La función de ejecución:

def run(): 
    import time 
    start = time.time() 
    for p in accelAsc(75): 
     pass 
    print time.time() - start, 'secs.' 

Si cambio de la definición de accelAsc para Cython a comenzar con:

def accelAsc(int n): 
    cdef int x, y, k 
    # no more changes.. 

llegue el momento Cython a 2,27 segundos.

Answer 4

Para generar composiciones directamente se puede utilizar el siguiente algoritmo:

def ruleGen(n, m, sigma): 
    """ 
    Generates all interpart restricted compositions of n with first part 
    >= m using restriction function sigma. See Kelleher 2006, 'Encoding 
    partitions as ascending compositions' chapters 3 and 4 for details. 
    """ 
    a = [0 for i in range(n + 1)] 
    k = 1 
    a[0] = m - 1 
    a[1] = n - m + 1 
    while k != 0: 
     x = a[k - 1] + 1 
     y = a[k] - 1 
     k -= 1 
     while sigma(x) <= y: 
      a[k] = x 
      x = sigma(x) 
      y -= x 
      k += 1 
     a[k] = x + y 
     yield a[:k + 1] 

Este algoritmo es muy general, y puede generar particiones y composiciones de muchos tipos diferentes. Para su caso, use

ruleGen(n, 1, lambda x: 1) 

para generar todas las composiciones no restringidas. El tercer argumento se conoce como la función de restricción y describe el tipo de composición/partición que necesita. El método es eficiente, ya que la cantidad de esfuerzo requerido para generar cada composición es constante, cuando se promedian todas las composiciones generadas. Si desea hacerlo un poco más rápido en python, entonces es fácil reemplazar la función sigma por 1.

Vale la pena señalar aquí también que para cualquier algoritmo de tiempo constante amortizado, lo que realmente hace con los objetos generados será casi ciertamente domina el costo de generarlos. Por ejemplo, si almacena todas las particiones en una lista, el tiempo dedicado a administrar la memoria para esta gran lista será mucho mayor que el tiempo dedicado a generar las particiones.

Diga, por alguna razón, desea tomar el producto de cada partición. Si se toma una aproximación ingenua a esto, entonces el procesamiento involucrado es lineal en la cantidad de partes, mientras que el costo de generación es constante. Es bastante difícil pensar en una aplicación de un algoritmo de generación combinatoria en el cual el procesamiento no domina el costo de generación. Entonces, en la práctica, no habrá una diferencia medible entre el uso de la regla más simple y más general, Gen con sigma (x) = x y la aceleración especializada.