单行Python素发生器 [英] Python prime generator in one-line

问题描述

我正在尝试在一行Python中创建素数生成器，这只是一个有趣的练习。

I'm trying to create prime number generator in one-line of Python just as a fun exercise.

以下代码按预期工作，但它也是如此慢：

The following code works as expected, but it is too slow:

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,

所以II试图只检查j和k的平方根：

So I I tried to do it by only checking up to the square-root of j and 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肯定有问题，但我没有线索。

So there must be something wrong with my indices j and k, but I haven't got a clue.

推荐答案

这不是Eratosthenes的筛子，即使它看起来像是。实际上情况要糟糕得多。 Sieve是查找素数的最佳算法。

That's not the Sieve of Eratosthenes, even though it looks like it is. It is in fact much worse. The Sieve is the best algorithm for finding primes.

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

编辑：我修改了 https://stackoverflow.com/a/9302299/711085 是一个单行（原来它不是真正的Sieve，但是现在它......可能......）：

edit: I've modified https://stackoverflow.com/a/9302299/711085 to be a one-liner (originally it was not the real Sieve, but now it is... probably...):

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中的任何筛子都需要使用变异来实现相当的性能。如果我们迫切想要的话，我们仍然可以把它塞进一个班轮里。但首先...

---

Sadly I think that while this would be efficient in a functional programming language, it might not be as efficient in python due to non-persistent (shared-state and immutable) data structures, and any sieve in python would need to use mutation to achieve comparable performance. We can still cram it into a one-liner if we desperately wanted to. But first...

普通筛子：

>>> 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 ...和foo 评估 ... ，同时返回 foo ：

We can now define and call anonymous functions on the same line, as well as the hack of [...].__setitem__ to do inline mutation, and the hack of ... and foo to evaluate ... while returning 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]

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

Proceed to cringe in horror, the one-liner expanded (oddly beautiful because you could almost directly translate the control flow, yet a terrible abuse of everything):

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 ⁹ ，内存不足（奇怪）。

This one-liner mutating version gave up at around 10⁸ on my machine, while the original mutating version gave up at around 10⁹, running out of memory (oddly).

原来的 reduce 版本放弃了10 ⁷ 。所以也许毕竟 效率低（至少对于你可以在你的电脑上处理的数字而言）。

The original reduce version gave up at 10⁷. So perhaps it is not that inefficient after all (at least for numbers you can deal with on your computer).

edit2 似乎你可以更简洁地滥用副作用：

edit2 It seems you can abuse side-effects more concisely as:

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 ⁸ ，与单行变异版。

It gives up at around 10⁸, the same as the one-liner mutating version.

edit3： 这运行在 O（N）经验复杂性，而没有 difference_update 它运行 O（n ^ 2.2）复杂度。

edit3: This runs at O(N) empirical complexity, whereas without the difference_update it ran at O(n^2.2) complexity.

将减少的范围限制为上限的sqrt，并且工作只有赔率，两者都会导致额外的加速（相应地 2x 和 1.6x ）：

Limiting the range that is reduced over, to the sqrt of the upper limit, and working with odds only, both result in additional speed-ups (2x and 1.6x correspondingly):

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)))

这篇关于单行Python素发生器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！