Tối ưu hóa một chức năng phân vùng

Question

Đây là mã, trong 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 

Nó sử dụng phương pháp này để tính toán phân vùng:

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

(nguồn: Wikipedia)

Tuy nhiên, mã mất khá nhiều thời gian khi nói đến số lượng lớn (trên p (10^3)). Tôi muốn hỏi bạn liệu tôi có thể tối ưu hóa mã của mình hay gợi ý cho tôi một thuật toán hoặc cách tiếp cận khác nhanh hơn nhưng không. Bất kỳ đề xuất tối ưu hóa đều được chào đón.

Và không, trước khi bạn yêu cầu, điều này không dành cho bài tập về nhà hoặc Project Euler, nó cho giá trị kinh nghiệm.

Answer 1

Dưới đây là một số nhận xét. Lưu ý rằng tôi không có chuyên gia về công cụ này, bởi tôi cũng thích rối tung về toán học (và Project Euler).

Tôi đã định nghĩa lại các chức năng số ngũ giác như sau:

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) 

Tôi đã viết cho họ theo cách như vậy mà tôi không giới thiệu các tính toán dấu chấm động - cho lớn n sử dụng phao nổi sẽ giới thiệu lỗi (so sánh kết quả cho n = 100000001).

Bạn có thể sử dụng mô-đun timeit để kiểm tra các đoạn mã nhỏ. Khi tôi kiểm tra tất cả các chức năng ngũ giác (của bạn và của tôi), kết quả cho tôi đã nhanh hơn. Sau đây là ví dụ kiểm tra chức năng gen_pent của bạn.

# 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() 

Đây là một sửa đổi nhỏ về chức năng partition của bạn. Một lần nữa, thử nghiệm với timeit cho thấy rằng nó nhanh hơn hàm partition của bạn. Tuy nhiên, điều này có thể là do các cải tiến được thực hiện cho các hàm số ngũ giác.

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 

Trong chức năng phân vùng, bạn tính tổng số ngũ giác chung hai lần cho mỗi vòng lặp. Một lần để kiểm tra trong khi điều kiện, và một để cập nhật total. Tôi lưu trữ kết quả trong một biến, do đó, chỉ thực hiện phép tính một lần cho mỗi vòng lặp.

Sử dụng mô-đun cProfile (đối với python> = 2.5, nếu không mô-đun hồ sơ) bạn có thể thấy mã của bạn dành phần lớn thời gian ở đâu. Đây là một ví dụ dựa trên chức năng phân vùng của bạn.

import cProfile 
import pstats 

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

này được sản xuất đầu ra sau đây trong cửa sổ giao diện điều khiển:

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) 

Bây giờ profiling phân vùng chức năng của tôi:

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) 

Bạn có thể nhìn thấy trong kết quả của tôi không có cuộc gọi đến các len và round chức năng dựng sẵn.Và tôi đã giảm gần một nửa số cuộc gọi đến các chức năng ngũ giác (gen_pent_new và pent_new)

Có thể có các thủ thuật khác để cải thiện tốc độ mã python. Tôi sẽ tìm kiếm ở đây để 'tối ưu hóa python' để xem những gì bạn có thể tìm thấy.

Cuối cùng, một trong các liên kết ở cuối trang wikipedia mà bạn đã đề cập là một academic paper về thuật toán nhanh để tính số phân vùng. Một cái nhìn nhanh chóng cho thấy nó chứa mã giả cho các thuật toán. Những thuật toán này có lẽ sẽ nhanh hơn bất cứ thứ gì bạn hoặc tôi có thể sản xuất.