python – 为什么这个算法更糟？

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python – 为什么这个算法更糟？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3098字，纯文字阅读大概需要5分钟。

内容图文

在Wikipedia中,这是生成素数的给定算法之一：

def eratosthenes_sieve(n):
    # Create a candidate list within which non-primes will be
    # marked as None; only candidates below sqrt(n) need be checked. 
    candidates = [i for i in range(n + 1)]
    fin = int(n ** 0.5)

    # Loop over the candidates, marking out each multiple.
    for i in range(2, fin + 1):
        if not candidates[i]:
            continue

        candidates[i + i::i] = [None] * (n // i - 1)

    # Filter out non-primes and return the list.
    return [i for i in candidates[2:] if i]

我略微改变了算法.

def eratosthenes_sieve(n):
    # Create a candidate list within which non-primes will be
    # marked as None; only candidates below sqrt(n) need be checked. 
    candidates = [i for i in range(n + 1)]
    fin = int(n ** 0.5)

    # Loop over the candidates, marking out each multiple.

    candidates[4::2] = [None] * (n // 2 - 1)

    for i in range(3, fin + 1, 2):
        if not candidates[i]:
            continue

        candidates[i + i::i] = [None] * (n // i - 1)

    # Filter out non-primes and return the list.
    return [i for i in candidates[2:] if i]

我首先标记了2的所有倍数,然后我只考虑了奇数.当我计算两种算法(尝试40.000.000)时,第一种算法总是更好(虽然非常轻微).我不明白为什么.有人可以解释一下吗？

P.S.：当我尝试100.000.000时,我的电脑冻结了.这是为什么？我有Core Duo E8500,4GB RAM,Windows 7 Pro 64 Bit.

更新1：这是Python 3.

更新2：这是我定时的方式：

start = time.time()
a = eratosthenes_sieve(40000000)
end = time.time()
print(end - start)

更新：有价值的评论(尤其是夜间工作者和Winston Ewert)我设法编写了我想要的第一个：

def eratosthenes_sieve(n):
    # Create a candidate list within which non-primes will be
    # marked as None; only c below sqrt(n) need be checked. 
    c = [i for i in range(3, n + 1, 2)]
    fin = int(n ** 0.5) // 2

    # Loop over the c, marking out each multiple.

    for i in range(fin):
        if not c[i]:
            continue

        c[c[i] + i::c[i]] = [None] * ((n // c[i]) - (n // (2 * c[i])) - 1)

    # Filter out non-primes and return the list.
    return [2] + [i for i in c if i]

该算法通过(通常)50％改进原始算法(在顶部提到). (仍然,比夜间人提到的算法更糟糕,自然而然).

Python Masters的一个问题：是否有更多Pythonic方式以更“功能”的方式表达最后一个代码？

更新2：我仍然无法解码nightcracker提到的算法.我想我太傻了.

解决方法:

问题是,为什么它会更快？在这两个例子中,你都是过滤两倍的倍数.无论你是硬编码候选[4 :: 2] = [无] *(n // 2 – 1)还是它在范围(2,fin 1)的i的第一个循环中执行都没关系：

如果您对优化的Eratosthenes筛子感兴趣,请转到：

def primesbelow(N):
    # https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    #""" Input N>=6, Returns a list of primes, 2 <= p < N """
    correction = N % 6 > 1
    N = (N, N-1, N+4, N+3, N+2, N+1)[N%6]
    sieve = [True] * (N // 3)
    sieve[0] = False
    for i in range(int(N ** .5) // 3 + 1):
        if sieve[i]:
            k = (3 * i + 1) | 1
            sieve[k*k // 3::2*k] = [False] * ((N//6 - (k*k)//6 - 1)//k + 1)
            sieve[(k*k + 4*k - 2*k*(i%2)) // 3::2*k] = [False] * ((N // 6 - (k*k + 4*k - 2*k*(i%2))//6 - 1) // k + 1)
    return [2, 3] + [(3 * i + 1) | 1 for i in range(1, N//3 - correction) if sieve[i]]

这里的解释：Porting optimized Sieve of Eratosthenes from Python to C++

原始来源是here,但没有解释.简而言之,这个primesieve跳过2和3的倍数,并使用一些hacks来使用快速Python赋值.

内容总结

以上是互联网集市为您收集整理的python – 为什么这个算法更糟？全部内容，希望文章能够帮你解决python – 为什么这个算法更糟？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---