我试图在一行Python中创建质数生成器,作为一个有趣的练习。
以下代码按预期工作,但速度太慢:
primes = lambda q: (i for i in xrange(1,q) if i not in [j*k for j in xrange(1,i) for k in xrange(1,i)])
for i in primes(10):
print i,
所以我试着只检查j和k的平方根:
primes = lambda q: (i for i in xrange(1,q) if i not in [j*k for j in xrange(1,int(round(math.sqrt(i)+1))) for k in xrange(1,int(round(math.sqrt(i)+1)))])
for i in primes(10):
print i,
但它输出:2 3 5 6 7 8
所以我的指数j和k肯定有问题,但我一点线索也没有。
那不是埃拉托舍内斯的筛子,尽管看起来是。事实上更糟。筛是寻找素数的最佳算法。
见http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
编辑:我已将https://stackoverflow.com/a/9302299/711085修改为一行(最初它不是真正的筛子,但现在它是。。。可能……:
演示:
遗憾的是,我认为虽然这在函数式编程语言中是有效的,但在python中由于非持久(共享状态和不可变)的数据结构,它可能没有那么有效,python中的任何筛子都需要使用变异来获得可比的性能。如果我们非常想的话,我们还可以把它塞进一个一行程序中。但首先。。。
普通筛:
我们现在可以在同一行上定义和调用匿名函数,还可以使用
[...].__setitem__
进行内联变异,使用... and foo
在返回foo
时计算...
:继续在恐惧中畏缩,一行代码扩展了(奇怪的美丽,因为你几乎可以直接翻译控制流,但却严重滥用了所有东西):
在我的机器上,这一行变异版本在大约108时放弃,而原始变异版本在大约109时放弃,内存不足(奇怪)。
最初的
reduce
版本在107时放弃。因此,也许并不是效率低下(至少对于您可以在计算机上处理的数字而言)。edit2似乎可以更简洁地滥用副作用:
它在大约108时放弃,与一行变异版本相同。
edit3:这个runs atO(N)empirical complexity,而没有
difference_update
,它在O(n^2.2) complexity运行。将缩小的范围限制在上限的sqrt内,并且工作with odds only,这两种情况都会导致额外的速度增加(2x并且相应地1.6x):
你不能只检查平方根以内的数的乘积来测试素数。看8,8的平方根是2.8,所以它永远不会尝试4*2。(事实上,不会被视为素数的唯一数字是平方数)。
ETA:与其尝试j和k的所有可能组合,不如检查i是否可以被每个j整除(使用
i % j == 0
)直到j的平方根?这两种方法都需要更少的代码,而且效率更高(尽管它仍然没有像Eratosthenes筛那样有效)。你想要的是:
在Haskell中,范围是包含的,因此
primes(542)
实际上,
1*x == x
所以1不需要作为乘数,因此应该是只需要0.59秒。或者,在Python中
更新:出于某种原因,
min j ...
没有多大区别,至少在Haskell中是这样。所以表达变得简单相关问题 更多 >
编程相关推荐