单行Python素发生器

Question

我试图在一行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肯定有问题,但我没有线索.

Answer 1

这不是Eratosthenes的筛子,尽管它看起来像是.实际上情况要糟糕得多.Sieve是寻找质数的最佳算法.

见http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

编辑:我已经修改/sf/answers/651160961/成为一个单行(原来它不是真正的Sieve,但现在它......可能......):

reduce( (lambda r,x: r-set(range(x**2,N,x)) if (x in r) else r), 
        range(2,N), set(range(2,N)))

演示:

>>> primesUpTo(N): lambda N: reduce(...)
>>> primesUpTo(30)
{2, 3, 5, 7, 11, 13, 17, 19}

遗憾的是,我认为虽然这在函数式编程语言中会很有效,但由于非持久性(共享状态和不可变)数据结构,它在python中可能不那么高效,并且python中的任何筛选器都需要使用突变来实现相似的表现.如果我们迫切希望,我们仍然可以将它塞进一个单行程中.但首先...

普通筛:

>>> N = 100
>>> table = list(range(N))
>>> for i in range(2,int(N**0.5)+1):
...     if table[i]:
...         for mult in range(i**2,N,i):
...             table[mult] = False
... 
>>> primes = [p for p in table if p][1:]
>>> primes
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

我们现在可以在同一行上定义和调用匿名函数,以及[...].__setitem__进行内联变异的hack,以及返回时... and foo评估的hack :...foo

>>> primesUpTo = lambda N: (lambda table: [[table.__setitem__(mult,False) for mult in range(i**2,N,i)] for i in range(2,int(N**0.5)+1) if table[i]] and [p for p in table if p][1:])(list(range(N)))
>>> primesUpTo(30)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

恐惧地继续畏缩,单线扩大(奇怪的美丽,因为你几乎可以直接翻译控制流,但是滥用一切可怕):

lambda N:
    (lambda table: 
        [[table.__setitem__(mult,False) for mult in range(i**2,N,i)] 
            for i in range(2,int(N**0.5)+1) if table[i]] 
        and [p for p in table if p][1:]
    )(list(range(N)))

这个单行变异版本在我的机器上放弃了大约10 ⁸,而最初的变异版本放弃了大约10 ⁹,内存耗尽(奇怪).

原reduce版本于10 ⁷放弃.所以也许它毕竟不是那么低效(至少对于你可以在你的计算机上处​​理的数字而言).

edit2看起来你可以更简洁地滥用副作用:

reduce( (lambda r,x: (r.difference_update(range(x**2,N,x)) or r)
                     if (x in r) else r), 
        range(2,N), set(range(2,N)))

它放弃了大约10 ⁸,与单线变异版本相同.

edit3:这是以 O(N)经验复杂度运行,而没有difference_update它以 O(n ^ 2.2)复杂度运行.

将减小的范围限制为上限的sqrt,仅使用赔率,两者都会导致额外的加速(相应地为2x和1.6x):

reduce( (lambda r,x: (r.difference_update(range(x*x,N,2*x)) or r)
                     if (x in r) else r), 
        range(3, int((N+1)**0.5+1), 2),
        set([2] + range(3,N,2)))