性能 - 为什么具有范围的主要生成算法比使用素数列表快得多

Question

我写了两个结构几乎相同的代码，

def prime_gen1(Limit = 10000):
    List = [2,]
    for x in range(3,Limit):
        for y in List:
            if not x%y:
                break
        if not x%y:
            continue
        else:
            List.append(x)
            yield x
def prime_gen2(Limit = 10000):
    from math import floor
    for x in range(3,Limit):
        for y in range(2, floor(x**0.5)+2):
            if not x%y:
                break
        if not x%y:
            continue
        else:
            yield x
>>> list(prime_gen1(20000)) == list(prime_gen2(20000))
True
>>> def time1(number):
    st = time()
    list(prime_gen1(number))
    end = time()
    return end - st
>>> def time2(number):
    st = time()
    list(prime_gen2(number))
    end = time()
    return end - st

一个与另一个做相同的工作，但后者实际上工作得更快。我想知道为什么会这样。

从逻辑上讲 - 或非逻辑上，我认为用素数检查会超越另一种方式，在这种情况下 - 通过 3 和数字根之间的数字进行检查。但是时间检查显示反之亦然，检查所有数字的效果要快得多 - 大约 5 次。它的性能越来越不同，

>>> time1(200000)
8.185129404067993
>>> time2(200000)
0.4998643398284912

第二种方法是超越它。这有什么不同？

Answer 1

列表版本比只检查数字平方根的版本要多得多

对于极限 200000，平方根为 ~447有17983个小于200000的质数

只需添加您执行 x%y 检查的次数，例如

def prime_gen1(Limit = 10000):
    List = [2,]
    modulo_checks = 0
    for x in range(3,Limit):
        for y in List:
            modulo_checks += 1
            if not x%y:
                break
        if not x%y:
            continue
        else:
            List.append(x)
            yield x
    print(modulo_checks)
def prime_gen2(Limit = 10000):
    from math import floor
    modulo_checks = 0
    for x in range(3,Limit):
        for y in range(2, floor(x**0.5)+2):
            modulo_checks += 1
            if not x%y:
                break
        if not x%y:
            continue
        else:
            yield x
    print(modulo_checks)

现在对于限制 200000，版本 1 执行162416226检查，第二个7185445

如果为列表循环添加早期中断，则列表版本明显更快（检查 0.24 秒1799767 7185445检查 0.64 秒快 2 倍）

...
    sq_root = floor(x ** 0.5) + 2
    for y in List:
        modulo_checks += 1
        if not x % y or y > sq_root:
            break
...

如果要比较算法速度，请删除数学导入

Answer 2

一些更好的时机

%timeit list(prime_gen1(10**5))
2.77 s ± 204 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit list(prime_gen2(10**5))
219 ms ± 10.5 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

您在第二个算法中采取了许多优化步骤，但在第一个算法中没有：以下是您的第一个算法的一些问题。

def prime_gen1(Limit = 10000):
    List = [2,]
    for x in range(3,Limit):  # we're checking all even numbers too
        for y in List:  # only need to check up to sqrt(x)!!
            if not x%y:
                break
        if not x%y:  # why are we checking again? Use a for-else construct
            continue
        else:
            List.append(x)  # just return the list at the end
            yield x  # when wrapped in list just copies List

这是第一个算法的优化版本（不是生成器，因为列表中的生成器毫无意义）：

def memeff_primelist(n):
    if n <= 2:
        return []
    primes = []  # Add 2 in at the end, don't need to check non-even
    for i in range(3, int(n), 2):
        for p in primes:
            if i % p == 0:  # non-prime
                break
            if p * p > i:  # no factors bigger than sqrt(i)!!!
                primes.append(i)
                break
        else:
            primes.append(i)  # only for i == 3
    primes.insert(0, 2)
    return primes
%timeit memeff_primelist(10**5)
88.9 ms ± 16.5 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)