Optymalizacja funkcji partycji

Question

Oto kod w Pythonie:

# 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 

wykorzystuje tę metodę do obliczania partycje:

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

(źródło: Wikipedia)

Jednak kod zajmuje dużo czasu, jeśli chodzi o duże liczby (ponad p (10^3)). Chciałbym zapytać, czy mogę zoptymalizować mój kod, lub wskazać mi inny, ale szybszy algorytm lub podejście. Wszelkie sugestie optymalizacji są mile widziane.

I nie, zanim zapytasz, to nie jest praca domowa ani projekt Euler, jego wartość dla doświadczenia.

Answer 1

Oto kilka komentarzy. Zauważ, że nie jestem ekspertem od tych rzeczy, przez ja też lubię bawić się z matematyką (i Project Eulerem).

Mam nowo pięciobocznej funkcji numerycznych w następujący sposób:

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) 

Pisałem je w taki sposób, że nie wprowadzi pływający obliczenia punktów - dla dużych N Używanie pływaków wprowadzi błędów (porównaj wyniki dla n = 100000001).

Możesz użyć modułu timeit, aby przetestować małe fragmenty kodu. Kiedy przetestowałem wszystkie funkcje pięciokątne (twoje i moje), moje wyniki były szybsze. Poniżej znajduje się przykład testujący twoją funkcję 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() 

Oto niewielka modyfikacja swojej funkcji partition. Ponownie, testowanie z timeit pokazuje, że jest ono szybsze niż twoja funkcja partition. Może to być spowodowane usprawnieniami wprowadzonymi do pięciokątnych funkcji liczbowych.

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 

W swojej funkcji podziału, obliczasz ogólną pięciokątną liczbę dwukrotnie dla każdej pętli. Raz przetestować w stanie while, a drugi zaktualizować total. Przechowuję wynik w zmiennej, więc wykonuję obliczenia tylko raz w każdej pętli.

Moduł cProfile (dla python> = 2.5, w przeciwnym razie moduł profilu) można zobaczyć, gdzie twój kod spędza większość swojego czasu. Oto przykład oparty na twojej funkcji partycji.

import cProfile 
import pstats 

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

Ten produkowany następujący wynik w oknie konsoli:

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) 

Teraz profilowania mojej funkcji partycji:

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) 

widać w moich wynikach nie ma połączenia do len i round wbudowane funkcje.I zmniejszyłem o prawie połowę liczbę wywołań funkcji pięciokątnych (gen_pent_new i pent_new)

Istnieją prawdopodobnie inne sztuczki poprawiające szybkość kodu Pythona. Szukałbym tutaj "optymalizacji pythona", aby zobaczyć, co możesz znaleźć.

Wreszcie jednym z linków na dole strony wikipedii, o której wspomniałeś, jest academic paper o szybkich algorytmach do obliczania numerów partycji. Szybkie spojrzenie pokazuje, że zawiera pseudokod dla algorytmów. Te algorytmy będą prawdopodobnie szybsze niż wszystko, co ty lub ja moglibyśmy wyprodukować.