それで、私は最近、階乗を非常に高速に計算することに興味を持ち、インターネットから1つを書き、他のいくつかをテストしました。コードは次のとおりです（Python 2.7）：
def prime_sieve(n):
"""A prime sieve, takes an int n, and returns all the primes < n"""
odds = range(3,n+1,2) #make a list of odd numbers starting at 3
i = 0 #an index counter
sqrt_n = int(n**0.5) #upper limit for sieving is isqrt(n)
d = len(odds) #the length of the list
while odds[i]<=sqrt_n:
if odds[i]: #odds[i]!=0
step = odds[i] #the ith odd which is nonzero is the next prime
start = (i+1)*step + i #this is the location of odds[i]^2
while start<d: #zero out stepth odd from start.
odds[start]=0
start+=step
i+=1
return [2]+filter(None, odds) #return a list of primes
#This one I wrote, and the stuff above
def factorial(n):
"""A factorial function which computes n! using it's prime factors"""
factors = [[i, 0] for i in prime_sieve(n)] #a list holding factor-exp pairs
for i in xrange(len(factors)): #find the exponents
m=float(n)
while factors[i][0]<m:
m/=factors[i][0]
factors[i][1]+=int(m)
result = 1 << factors[0][1] #start off by shifting result, instead of x 2^m
for i in factors[1:]: #multiply result by every prime factor^exp
result*=i[0]**i[1]
return result
#the next two are the obvious ones
def naive_factorial(n):
"""Calculates n! with a simple while loop"""
result = n
while (n-1)>1: #n! = n*(n-1)*(n-2)...*2*1
result*=(n-1)
n-=1
return result
def recursive_fact(n):
"""Calculates n! recursively"""
if n<=1: return 1 #n! = n*(n-1)!
return n*recursive_fact(n-1)
def factorial2(n):
"""Another factorial claiming to be fast, pulled from the internet
I have no idea how this works"""
result = 1
buf = 1
power2 = 0
stack = []
while n > 1:
stack.append(n)
n /= 2
power2 += n
for n1 in stack[::-1]:
while n <= n1:
buf *= n
n += 2
result *= buf
result <<= power2
return result
def multiply_range(n, m):
if n == m:
return n
if m < n:
return 1
else:
return multiply_range(n, (n+m)/2) * multiply_range((n+m)/2+1, m)
def factorial3(n):
""""Also from the internet, the logic seems reasonable, 'divide and conquer'. """
return multiply_range(1, n)
if __name__=="__main__":
import math
import cProfile
print "Calculating 70000! using naive_factorial."
cProfile.run("naive_factorial(70000)")
print "\nCalculating 70000! using math.factorial."
cProfile.run("math.factorial(70000)")
print "\nCalculating 70000! using factorial."
cProfile.run("factorial(70000)")
print "\nCalculating 70000! using factorial2."
cProfile.run("factorial2(70000)")
print "\nCalculating 70000! using factorial3."
cProfile.run("factorial3(70000)")
私はPythonを初めて使用するわけではありません。メイン言語として数年間使用していますが、結果は少し予想外でした...
Calculating 70000! using naive_factorial.
3 function calls in 19.842 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 19.842 19.842 <string>:1(<module>)
1 19.842 19.842 19.842 19.842 factorial.py:30(naive_factorial)
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
Calculating 70000! using math.factorial.
3 function calls in 22.372 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 22.372 22.372 <string>:1(<module>)
1 22.372 22.372 22.372 22.372 {math.factorial}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
Calculating 70000! using factorial.
8 function calls in 9.092 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.003 0.003 9.092 9.092 <string>:1(<module>)
1 0.020 0.020 0.024 0.024 factorial.py:1(prime_sieve)
1 9.066 9.066 9.090 9.090 factorial.py:17(factorial)
1 0.002 0.002 0.002 0.002 {filter}
2 0.000 0.000 0.000 0.000 {len}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1 0.002 0.002 0.002 0.002 {range}
Calculating 70000! using factorial2.
19 function calls in 5.791 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 5.791 5.791 <string>:1(<module>)
1 5.791 5.791 5.791 5.791 factorial.py:43(factorial2)
16 0.000 0.000 0.000 0.000 {method 'append' of 'list' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
Calculating 70000! using factorial3.
140002 function calls (4 primitive calls) in 1.147 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 1.147 1.147 <string>:1(<module>)
139999/1 1.147 0.000 1.147 1.147 factorial.py:65(multiply_range)
1 0.000 0.000 1.147 1.147 factorial.py:73(factorial3)
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
私の質問は、どうすれば最後のものをもっと速くできるのでしょうか?! すべての再帰を見てください！Python は再帰が好きではないと思っていました。では、なぜこれほど高速になったのでしょうか。factorial2 はどのように機能しますか? また、誰もが知っているように、これらすべてがいくつかの異なる値に対して正しい出力を生成していることを確認したので、これらすべてが正しく機能すると確信しています。