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

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 和 number.But 的根之间的数字检查时间检查显示反之亦然，检查所有数字工作得更快 - 大约 5 倍。它的性能越来越不同，

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

第二种方法胜过它。这有什么不同？

Answer 1

列表版本比仅对数字的平方根进行更多检查

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

只需添加您进行 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

如果您为列表循环添加一个提前中断，则列表版本会显着加快（1799767 检查 0.24 秒与 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)

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

Performance - why is a prime-generating algorithm with range much faster than using prime list?

python

primes

performance-testing

python-3.x