優化分區函數

下面是代碼，在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

它使用此方法來計算分區：

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

（來源：Wikipedia）

但是，代碼當涉及到大量數據時（p（10^3）），需要相當長的時間。我想問你是否可以優化我的代碼，或者提示我採用不同但更快的算法或方法。歡迎任何優化建議。

不，我可以告訴大家，這不是家庭作業或項目歐拉，其經驗值。

來源

2010-07-02 Khaled

這裏有一些意見。請注意，我並不是這方面的專家，我也喜歡用數學（和歐拉項目）搞亂。

我已經重新定義了五角數功能如下：

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)

我在這樣的，我不會引入浮點計算的方式寫他們 - 爲大型用正花車將引入誤差（比較結果爲n = 100000001）。

可以使用timeit模塊測試代碼片段。當我測試所有五角函數（你的和我的）時，我的結果更快。以下是測試您的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()

這是您的partition函數的輕微修改。同樣，使用timeit進行測試表明它比您的partition函數更快。但是，這可能是由於對五角數函數的改進所致。

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

在你的分區函數中，你計算每個循環兩次的一般五邊形數。一次在while條件下測試，另一次更新total。我將結果存儲在一個變量中，因此每個循環只進行一次計算。

使用cProfile模塊（對於Python> = 2.5，否則該形象模塊），你可以看到你的代碼花費大量的時間。這裏是一個基於你的分區函數的例子。

import cProfile 
import pstats 

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

這產生在控制檯窗口中下面的輸出：

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)

現在剖析我的分區功能：

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)

你可以在我的結果看到有到len沒有呼叫和內建函數。我幾乎減半了五角函數的調用次數（gen_pent_new和pent_new）

提高python代碼的速度可能還有其他技巧。我會在這裏搜索'python優化'，看看你能找到什麼。

最後，您提到的維基百科頁面底部的鏈接之一是用於計算分區號的快速算法的academic paper。快速瀏覽顯示它包含算法的僞代碼。這些算法可能比我們能夠生成的任何東西都快。

來源

2010-07-02 12:00:56

優化分區函數

回答

相關問題