为什么这个 'optimized' 素数检查器运行与普通版本的速度相同？

Question

给定这个简单的 is_prime1 函数，它通过一些位播放来检查从 1 到 sqrt(p) 的所有除数，以避免偶数当然不是素数。

import time
def is_prime1(p):
    if p & 1 == 0:
        return False
    # if the LSD is 5 then it is divisible by 5 (i.e. not a prime)
    elif p % 10 == 5:
        return False

    for k in range(2, int(p ** 0.5) + 1):
        if p % k == 0:
            return False
    return True

与这个“优化”版本相比。这个想法是将我们找到的所有素数保存到某个数字 p，然后我们对素数进行迭代（使用这个基本算术规则，即每个数字都是素数的乘积）所以我们不会迭代数字直到 sqrt( p) 但在质数上，我们发现与 sqrt(p) 相比应该很小一点。我们也只迭代一半的元素，因为最大的素数肯定不会“适合”数字 p.

import time
global mem
global lenMem
mem = [2]
lenMem = 1

def is_prime2(p):
    global mem
    global lenMem
    # if p is even then the LSD is off

    if p & 1 == 0:
        return False
    # if the LSD is 5 then it is divisible by 5 (i.e. not a prime)
    elif p % 10 == 5:
        return False

    for div in mem[0: int(p ** 0.5) + 1]:
        if p % div == 0:
            return False
    mem.append(p)
    lenMem += 1
    return True

我唯一的想法是“全局变量既昂贵又耗时”，但我不知道是否有另一种方法，如果有，真的有用吗？

平均而言，当运行同一程序时：

start = time.perf_counter()
for p in range(2, 100000):
    print(f'{p} is a prime? {is_prime2(p)}') # change to is_prime1 or is_prime2
end = time.perf_counter()

我知道 is_prime1 检查数字 1-100K 的平均时间是 ~0.99 seconds，所以 is_prime2（可能平均相差 +0.01s，也许正如我所说，使用全局变量会破坏一些性能？）

Answer 1

不同之处在于三件事的结合：

你只是没有少做那么多工作。您的测试用例包括测试大量小数字，其中测试“从 2 到平方根的所有数字”和测试“从 2 到平方根的所有素数”之间的区别并没有太大区别。你的“平均情况”大致是范围的中点，50,000，223.6 的平方根，这意味着测试 48 个素数，或者如果数字是素数则测试 222 个数字，但是 most 数字不是't prime，并且 most 数字至少有一个小因子（证明作为练习），所以你短路并且实际上不测试任何一组中的大多数数字（如果有一个低于 8 的因数，它适用于所有数字的 ~77%，您通过将自己限制为质数来节省了也许两个测试）
你每次都在切片 mem，这是急切而完整地执行的，即使你没有使用所有的值（并且如前所述，你几乎从不为非素数）。这不是一个巨大的成本，但是，你并没有从跳过非质数中获得巨大的节省，所以它可能会吃掉你从其他优化中获得的少量节省。
（你找到了这个，好戏）你的素数片用了 number 个素数来测试等于要测试的数的平方根，并非所有素数都小于要测试的数字的平方根。因此，您实际上执行了相同数量的测试，只是使用了不同的数字（其中许多素数大于绝对不需要测试的平方根）。

旁注：

您的前期测试实际上并没有为您节省很多工作；你在循环中重做这两个测试，所以当数字是素数时，它们是浪费精力（你对它们都进行了两次测试）。你对被五整除的测试毫无意义； % 10 并不比 % 5 快（计算机不以 base-10 运行），而 if not p % 5: 稍微快一点，更直接，更完整（你的测试不识别 10 的倍数，只是不是 10 的倍数的 5 的倍数）测试整除性的方法。

测试也是错误的，因为它们不排除基本情况（他们说 2 和 5 不是质数，因为它们分别可以被 2 和 5 整除).

Answer 2

首先，您应该删除打印调用，它非常耗时。你应该只为你的函数计时，而不是打印函数，所以你可以这样做：

start = time.perf_counter()
for p in range(2, 100000):
##    print(f'{p} is a prime? {is_prime2(p)}') # change to is_prime1 or is_prime2
    is_prime1(p)
end = time.perf_counter()

print ("prime1", end-start)


start = time.perf_counter()
for p in range(2, 100000):
##    print(f'{p} is a prime? {is_prime2(p)}') # change to is_prime1 or is_prime2
    is_prime2(p)
end = time.perf_counter()

print ("prime2", end-start)

is_prime1 对我来说还是更快。

Answer 3

如果您想在全局内存中保存素数以加速多次调用，您需要确保正确填充素数列表，即使函数以随机顺序调用数字也是如此。 is_prime2() 存储和使用素数的方式假设，例如，它在用 343 调用之前用 7 调用。如果不是，343 将被视为素数，因为 7 还不在素数列表中.

因此该函数必须计算并存储最大为 √49 的所有素数，然后才能响应 is_prime(343) 调用。

为了快速建立素数列表，埃拉托色尼筛法是最快的方法之一。但是，由于事先不知道需要多少素数，因此无法提前分配筛子的位标志。您可以做的是使用筛子的滚动 window 逐块向前移动（假设一次 1000000 位）。当请求的数字超出最大素数时，您只需生成更多素数块逐块直到你有足够的回应。

另外，既然你要建立一个质数列表，你不妨把它做成一个集合，然后检查请求的数字是否在其中以响应函数调用。这将需要生成比除法所需更多的素数，但本着加速后续调用的精神，这应该不是问题。

下面是一个使用该方法的 isPrime() 函数示例：

primes      = {3}
sieveMax    = 3
sieveChunk  = 1000000 # must be an even number
def isPrime(n):
    if not n&1: return n==2
    global primes,sieveMax, sieveChunk
    while n>sieveMax:
        base,sieveMax = sieveMax, sieveMax + sieveChunk
        sieve = [True]* sieveChunk
        for p in primes:
            i = (p - base%p)%p
            sieve[i::p]=[False]*len(sieve[i::p])
        for i in range(0, sieveChunk,2):
            if not sieve[i]: continue
            p = i + base
            primes.add(p)
            sieve[i::p] = [False]*len(sieve[i::p])
    return n in primes

在第一次调用未知素数时，它的执行速度会比除法方法慢，但随着素数列表的增加，它会提供更好的响应时间。

为什么这个 'optimized' 素数检查器运行与普通版本的速度相同？

Why does this 'optimized' prime checker run at the same speed as the regular version?

python

algorithm

performance

primes

python-3.x

为什么这个 'optimized' 素数检查器 运行 与普通版本的速度相同？

Why does this 'optimized' prime checker run at the same speed as the regular version?

python

algorithm

performance

primes

python-3.x

为什么这个 'optimized' 素数检查器运行与普通版本的速度相同？