Python - 快速析因函數

我正在嘗試編寫超快速析因函數的代碼。我已經嘗試了一點，已經提出了以下三個候選人（除了math.factorial）：Python - 快速析因函數

def f1(): 
    return reduce(lambda x,y : x * y, xrange(1,31)) 

def f2(): 
    result = 1 
    result *= 2 
    result *= 3 
    result *= 4 
    result *= 5 
    result *= 6 
    result *= 7 
    result *= 8 
    #and so-on... 
    result *= 28 
    result *= 29 
    result *= 30 
    return result 

def f3(): 
    return 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20*21*22*23*24*25*26*27*28*29*30

我已超時這些功能。這些是結果：

In [109]: timeit f1() 
100000 loops, best of 3: 11.9 µs per loop 

In [110]: timeit f2() 
100000 loops, best of 3: 5.05 µs per loop 

In [111]: timeit f3() 
10000000 loops, best of 3: 143 ns per loop 

In [112]: timeit math.factorial(30) 
1000000 loops, best of 3: 2.11 µs per loop

很明顯，f3（）取了蛋糕。我試圖實現這一點。詳細地說，我試過寫代碼來產生這樣的字符串：「1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 ..... ...「然後使用eval來評估這個字符串。（承認'eval'是邪惡的）。但是，這種方法在時間上並沒有給我帶來任何收益。事實上，我花了近150微秒才完成。

請教如何推廣f3（）。

來源

2017-06-30 Nagesh Eranki

我不認爲你可以概括F3。這個練習展示的是，如果你想找到最快的方法來做某件事，你需要測試實際的事情。僅適用於n = 30的測試功能無濟於事。無論如何，最後，嘗試使用'reduce'與'operator.mul'。或者，如果您可以保證參數不會超過〜1000，只需將結果緩存在列表中。 –

@AlexHall我實際上已經嘗試減少（運算符.__ mul__，....）但是，結果不是納秒範圍，這正是我所希望的。 –

我會爭辯說，這些都不是很好的因子函數，因爲沒有一個參數給函數。之所以最後一個工作正常，是因爲它最小化了解釋步驟的數量，但這仍然不是一個好答案：它們都具有相同的複雜性（與值的大小成線性關係）。我們可以做得更好：O（1）。

import math 
def factorial(x): 
    return math.gamma(x+1)

這不斷縮放輸入值，犧牲一些準確性。當性能很重要時，仍然會更好。

我們可以做一個快速的基準：

import math 
def factorial_gamma(x): 
    return math.gamma(x+1) 

def factorial_linear(x): 
    if x == 0 or x == 1: 
     return 1 
    return x * factorial_linear(x-1) 


In [10]: factorial_linear(50) 
Out[10]: 30414093201713378043612608166064768844377641568960512000000000000 

In [11]: factorial_gamma(50) 
Out[11]: 3.0414093201713376e+64 

In [12]: %timeit factorial_gamma(50) 
537 ns ± 6.84 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 

In [13]: %timeit factorial_linear(50) 
17.2 µs ± 120 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

爲50.不壞因子A 30倍的增長。

https://docs.scipy.org/doc/scipy-0.19.0/reference/generated/scipy.misc.factorial.html

來源

2017-06-30 06:08:30

我想，OP想要做eval的原因，是有一個在爭論中，但。 – JohanL

啊，但準確性對於我正在做的事很重要。那你建議我做什麼？ –

實際上，準確度幾乎可以忽略不計。你不可能注意到任何區別。 –

f3僅僅是快的，因爲它實際上沒有任何的計算，當你調用它。整個計算在編譯時得到優化，並用最終值取代，所以你的計時是函數調用開銷。

>>> import dis 
>>> dis.dis(f3) 
    2   0 LOAD_CONST    59 (265252859812191058636308480000000L) 
       3 RETURN_VALUE

這是不可能的這種加速推廣到一個需要參數，並返回其階乘的函數：

如果我們拆解與dis模塊的功能，這一點尤其明顯。

來源

2017-06-30 06:11:19 user2357112

你能解釋一下爲什麼不可能嗎？ –

@NageshEranki：'f3'只有很快，因爲結果已經被計算出來了。你不能預先計算每個可能的輸出，如果你嘗試了，它不一定會更快，有什麼增加了初始化時間。根據您的使用情況，可能有一些方法可以從預計算或保存輸出中獲得一些好處，但您看到的「timeit」結果是一個夢想。 – user2357112

根本沒有辦法概括「我已經知道答案」爲每個可能的答案。 – user2357112

F3（）需要的蛋糕，因爲當該函數def'ed的Python只是優化乘法的字符串下降到最終的結果和f3的有效定義（）變爲：

def f3(): 
    return 8222838654177922817725562880000000

其中，因爲沒計算需要在調用函數時發生，運行真快！

產生在數字列表之間放置*運算符的所有效果的一種方法是使用來自functools模塊的reduce。這有時候就像你在找什麼？

from functools import reduce 
def fact(x): 
    return reduce((lambda x, y: x * y), range(1, x+1))

來源

2017-06-30 06:16:57 quizdog

正如其他人所指出f3()實際上沒有任何的計算，這就是爲什麼你這麼快的結果。通過將它提供給一個函數，你不能達到同樣的效果。

另外你也許想知道爲什麼math.factorial()是如此之快，那是因爲的math module's functions是用C語言實現：

這個模塊是始終可用。它提供對由C標準定義的數學函數的訪問

通過在C中使用高效算法，您可以獲得如此快速的結果。

這裏您最好的選擇將使用下面的功能，但使用math.factorial是是我喜歡，如果你需要性能是純粹

def f3(x): 
    ans=1 
    for i in range(1,x+1): 
     ans=ans*i 
    return ans 
print(f3(30))

來源

2017-06-30 06:20:28 void

仍然不比您的幼稚實施更快。 Python可以保證更快的時間，使用分而治之的方法，這裏解釋： http://www.luschny.de/math/factorial/binarysplitfact.html –

Python - 快速析因函數

回答

相關問題