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 - 快速析因函数

回答

相关问题