一个lin中的Python主生成器

2024-03-29 04:37:08 发布

您现在位置:Python中文网/ 问答频道 /正文

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


Tags: lambda代码inforifnotmathsqrt
3条回答

那不是埃拉托舍内斯的筛子,尽管看起来是。事实上更糟。筛是寻找素数的最佳算法。

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

编辑:我已将https://stackoverflow.com/a/9302299/711085修改为一行(最初它不是真正的筛子,但现在它是。。。可能……:

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__进行内联变异,使用... and foo在返回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)))

在我的机器上,这一行变异版本在大约108时放弃,而原始变异版本在大约109时放弃,内存不足(奇怪)。

最初的reduce版本在107时放弃。因此,也许并不是效率低下(至少对于您可以在计算机上处理的数字而言)。

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

它在大约108时放弃,与一行变异版本相同。

edit3:这个runs atO(N)empirical complexity,而没有difference_update,它在O(n^2.2) complexity运行。

将缩小的范围限制在上限的sqrt内,并且工作with odds only,这两种情况都会导致额外的速度增加(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)))

你不能只检查平方根以内的数的乘积来测试素数。看8,8的平方根是2.8,所以它永远不会尝试4*2。(事实上,不会被视为素数的唯一数字是平方数)。

ETA:与其尝试j和k的所有可能组合,不如检查i是否可以被每个j整除(使用i % j == 0)直到j的平方根?这两种方法都需要更少的代码,而且效率更高(尽管它仍然没有像Eratosthenes筛那样有效)。

你想要的是:

def primes (q) :
 # return (i for i in xrange(2,q) if i not in [j*k for j in xrange(1,i) for k in xrange(1,i)])
 # return (i for i in xrange(2,q) if i not in [j*k for j in xrange(1,i) for k in xrange(1,j+1)])
 # return (i for i in xrange(2,q) if i not in [j*k for j in xrange(1,i/2+1) for k in xrange(1,j+1)])

 return (i for i in xrange(2,q) if i not in [j*k for j in xrange(1,i/2+1) for k in xrange(1,min(j+1,i/j+1))])

在Haskell中,范围是包含的,因此primes(542)

[n | n<-[2..541], not $ elem n [j*k | j<-[1..n-1],     k<-[1..n-1]]]  --  25.66s
[n | n<-[2..541], not $ elem n [j*k | j<-[1..n-1],     k<-[1..j]]]    --  15.30s
[n | n<-[2..541], not $ elem n [j*k | j<-[1..n`div`2], k<-[1..j]]]    --   6.00s
                                                                      --   0.79s
[n | n<-[2..541], not $ elem n [j*k | j<-[1..n`div`2], k<-[1..min j (n`div`j)]]] 

实际上,1*x == x所以1不需要作为乘数,因此应该是

[n | n<-[2..541], not $ elem n [j*k | j<-[2..n`div`2], k<-[2..min j (n`div`j)]]] 

只需要0.59秒。或者,在Python中

def primes (q) :
 return (i for i in xrange(2,q) if i not in [j*k for j in xrange(2,i/2+1) for k in xrange(2,min(j+1,i/j+1))])

更新:出于某种原因,min j ...没有多大区别,至少在Haskell中是这样。所以表达变得简单

[n | n<-[2..541], not $ elem n [j*k | j<-[2..n`div`2], k<-[2..n`div`j]]] 

相关问题 更多 >