Python - ファーストファクトリアル関数

Question

超高速階乗関数のコードを記述しようとしています。私は少し実験してきたし、（離れてmath.factorialから）次の三つの候補者が出ている：私は、これらの機能を計時している

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」は悪いことを認めます）。しかし、この方法では、時間的に利益が得られませんでした。実際には、完了までに約150マイクロ秒かかりました。

f3（）を一般化する方法について助言してください。

Answer 1

私はこれらのどれも良い階乗関数ではないと主張します。なぜなら、誰も関数にパラメータを取らないからです。最後のものがうまくいく理由は、インタープリタステップの数を最小限に抑えるためですが、それでもまだ良い答えではありません。それらはすべて同じ複雑さ（値の大きさに比例します）を持ちます。私たちはもっとうまくいくことができます：O（1）。

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

精度を犠牲にして、この値は常に入力値に比例します。それでもパフォーマンスが重要な場合は、より良い方法です。悪くない50の階乗のため

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) 

30倍の増加：

は、我々は、迅速なベンチマークを行うことができます。

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

Answer 2

f3あなたがそれを呼び出すとき、それは実際には何も計算されていないため、速いだけです。計算全体がコンパイル時に最適化され、最終値に置き換えられるため、関数呼び出しのオーバーヘッドはすべてタイミングになります。

これは、我々がdisモジュールと機能を分解した場合に特に明らかである：

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

引数を取り、その階乗を返す関数には、この高速化を一般化することは不可能です。

Answer 3

F3機能def'edされたときにPythonがちょうど最終結果までの乗算の列及びF3の効果的な定義を（最適化するために（））ケーキを取りになる：

def f3(): 
    return 8222838654177922817725562880000000 

、ないため関数が呼び出されると計算が必要になり、実際には高速に実行されます。

数字のリストの間に*演算子を配置する効果を得る方法の1つは、functoolsモジュールのreduceを使用することです。これはいつかあなたが探しているもののようですか？

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

Answer 4

他の人が述べたように、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))