python: Generowanie partycji liczb całkowitych

Question

Potrzebuję wygenerować wszystkie partitions danej liczby całkowitej.
znalazłem ten algorytm Jerome Kelleher, dla których jest określona jako najskuteczniejszy jeden:

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] 

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

Nawiasem mówiąc, nie jest dość skuteczny. Dla wejścia takiego jak 40 zamarza on prawie cały mój system na kilka sekund przed podaniem jego wyjścia.

Jeśli był to algorytm rekursywny, spróbowałbym udekorować go funkcją buforowania lub czymś, co poprawiłoby jej efektywność, ale w ten sposób nie wiem, co robić.

Czy masz jakieś sugestie, jak przyspieszyć ten algorytm? Czy możesz zaproponować mi inny, lub inne podejście, aby zrobić kolejny od zera?

Answer 1

Jeśli masz zamiar używać wielokrotnie tej funkcji dla tego samego input, nadal warto cachować wartości zwracane (jeśli zamierzasz używać go w osobnych przebiegach, możesz zapisać wyniki w pliku).

Jeśli nie można znaleźć znacznie szybszego algorytmu, powinno być możliwe przyspieszenie go o rząd wielkości lub dwa poprzez przeniesienie kodu do rozszerzenia C (najprawdopodobniej jest to najprostsze użycie cython), lub alternatywnie za pomocą PyPy zamiast CPython (PyPy ma swoje wady - nie obsługuje jeszcze Pythona 3 lub niektórych powszechnie używanych bibliotek, takich jak numpy i scipy).

Powodem tego jest, ponieważ python jest wpisywany dynamicznie, tłumacz prawdopodobnie spędza większość czasu sprawdzając typy zmiennych - dla wszystkich interpreterów wie, że jedna z operacji może przekształcić x w ciąg, w które przypadki takie jak x + y nagle miałyby bardzo różne znaczenia. Cython rozwiązuje ten problem, umożliwiając statyczne zadeklarowanie zmiennych jako liczb całkowitych, natomiast PyPy ma just-in-time compiler, co minimalizuje kontrole nadmiarowe.

Answer 2

Powiedziałbym, że problem z wydajnością jest gdzie indziej.

nie porównać go z innymi metodami, ale wydaje mi się skuteczny:

import time 

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

Dał:

time: 0.03636 sec 
length: 37338 

Answer 3

Testy dla n = 75 uzyskać:

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 

Nie widziałem żadnej różnicy z Psyco (?)

Funkcja Run:

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

Jeśli zmienić definicję accelAsc dla Cython zacząć:

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

mam czas Cython w dół do 2,27 sek.

Answer 4

aby wygenerować kompozycje bezpośrednio można użyć następującego algorytmu:

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] 

Algorytm ten jest bardzo ogólny i może generować partycje i kompozycje z wielu różnych typów. Dla swojego przypadku użyj

ruleGen(n, 1, lambda x: 1) 

, aby wygenerować wszystkie nieograniczone kompozycje. Trzeci argument jest znany jako funkcja ograniczenia i opisuje typ wymaganej kompozycji/partycji. Metoda ta jest skuteczna, ponieważ ilość wysiłku niezbędnego do wygenerowania każdej kompozycji jest stała, gdy średnia jest dla wszystkich wygenerowanych kompozycji. Jeśli chcesz, aby był nieco szybszy w pythonie, łatwo jest zastąpić funkcję sigma wartością 1.

Warto tutaj również zauważyć, że dla każdego algorytmu o stałym amortyzowanym czasie, co faktycznie zrobisz z wygenerowanymi obiektami będzie prawie z pewnością dominują koszty ich generowania. Na przykład jeśli przechowujesz wszystkie partycje na liście, czas spędzony na zarządzaniu pamięcią dla tej dużej listy będzie znacznie większy niż czas potrzebny na wygenerowanie partycji.

Powiedz, z jakiegoś powodu chcesz wziąć produkt z każdej partycji. Jeśli podejmiesz naiwne podejście, przetwarzanie to jest liniowe pod względem liczby części, podczas gdy koszt generowania jest stały. Trudno jest myśleć o zastosowaniu kombinatorycznego algorytmu generowania, w którym przetwarzanie nie zdominuje kosztu generowania. Tak więc w praktyce nie będzie żadnej mierzalnej różnicy między używaniem prostszej i bardziej ogólnej regułyGen z sigma (x) = x a wyspecjalizowanym accelAsc.