文章/答案/技术大牛

发布

社区首页 >问答首页 >在Python中递归实现埃斯平素筛子的效率

问在Python中递归实现埃斯平素筛子的效率
EN

Code Review用户

提问于 2019-05-04 12:01:45

回答 1查看 250关注 0票数 3

我使用filter递归地实现了recursive筛子，我想知道这个实现的效率有多高，是否有一个非递归的实现或者没有filter的东西会更好。如果有人想进入微优化等领域，那也会很有趣，我想:)

这是我的密码：

def sieve (iterable, container):
    if len(iterable) != 1:
        container.append(iterable [0])
        iterable = [item for item in iterable if item % iterable [0] != 0]
        print("Filter call:", iterable, container, '\n')
        return sieve(iterable, container)
    else: 
        container.append(iterable[0])
        print("Return container:", container)
        return container

例如I/O (带有打印语句)将是：

#Input
lst = list(range(2, 20))
primes = []

print(sieve(lst, primes)

#Output
Filter call: [3, 5, 7, 9, 11, 13, 15, 17, 19] [2] 

Filter call: [5, 7, 11, 13, 17, 19] [2, 3] 

Filter call: [7, 11, 13, 17, 19] [2, 3, 5] 

Filter call: [11, 13, 17, 19] [2, 3, 5, 7] 

Filter call: [13, 17, 19] [2, 3, 5, 7, 11] 

Filter call: [17, 19] [2, 3, 5, 7, 11, 13] 

Filter call: [19] [2, 3, 5, 7, 11, 13, 17] 

Return container: [2, 3, 5, 7, 11, 13, 17, 19]

#Return
Out: [2, 3, 5, 7, 11, 13, 17, 19]

python

recursion

sieve-of-eratosthenes

回答 1

Code Review用户

回答已采纳

发布于 2019-05-04 18:19:53

算法

这不是埃拉托斯提尼的筛子。真正的筛子只触及每个素数的倍数，因此它具有复杂性n \log \log n。过滤重复复制整个列表，这相当于一种不同的算法，即尝试除法，具有不同的复杂度(可能是n^2 / (\log n)^2)。这是一个巨大的差异，这导致梅丽莎奥尼尔写了一个略为著名的学术咆哮关于这一点。

但这对一个教育项目来说不是个问题。本审查的其余部分是关于您的实现的。

每个素数上的递归都有深度\pi(n) \approx n / \log n，这将使任何大型n的堆栈溢出。你能用迭代的方式来代替吗？

名称

iterable是一个误导的名称:函数使用len(iterable)，但迭代不一定支持len。所以它并不适用于所有的迭代。

iterable也是一个信息不足的名字:它没有说明参数的含义。它不只是任何可迭代的，它是一个候选素数的列表，所以它可以被称为candidates。

类似地，container不仅仅是任何容器，它是一个素数列表，因此它应该被称为primes。而且，sieve会修改它，这是非常不寻常的，它需要一个注释，它甚至可以出现在名称中:它可以被称为output_primes。

接口

修改论点是令人困惑和容易出错的。为什么不构建一个列表并返回它呢？

为什么打电话的人需要提供一份候选人名单？仅仅通过n并让sieve负责构建候选人不是更简单吗？

如果递归函数需要与调用方不同的接口，则可以使用一个函数执行递归，并将其与向调用方提供干净接口的另一个函数包装。

Innards

重复：container.append(iterable[0])出现在if的两个分支中。它可以在if之前移动。

程序检查len(iterable) != 1，那么如果len(iterable) == 0会发生什么呢？Oops:它尝试使用iterable[0]和崩溃。这通常是最安全的检查0，而不是1。这也将消除重复。

Optimization

对该算法的改进将大大超过微观优化。如果您切换到真正的Eratosthenes筛子，它仍然不够快，有算法上的改进，如Sundaram筛。

在优化之前，测量性能！优化很难，而且很容易出错，所以让度量来指导您。

其他

这个函数应该有一个docstring来表示它所做的事情："Prime number sieve: Given a list of candidates, append the primes to output_primes."

你的问题是程序使用filter，但实际上它使用列表理解来做同样的事情。这不是程序的问题，只是有点混乱。

票数 2

页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://codereview.stackexchange.com/questions/219699

复制

相似问题

问在Python中递归实现埃斯平素筛子的效率
EN

回答 1

Code Review用户

算法

名称

接口

Innards

Optimization

其他

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在Python中递归实现埃斯平素筛子的效率EN

回答 1

Code Review用户

算法

名称

接口

Innards

Optimization

其他

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在Python中递归实现埃斯平素筛子的效率
EN