Python大整数性能

Question

我想在 python 中编写一个质数生成器 - 我只用 C 和 Java 完成了这个。我做了以下事情。我使用整数位图作为数组。算法的性能应该会提高，nlog(log(n))但随着问题规模的n增加，我看到成本/时间呈指数增长。当整数变得大于实际时，这是我没有看到或不知道 python 的明显问题吗？我正在使用 python-3.8.3。

def countPrimes(n):
    if n < 3:
        return []

    arr = (1 << (n-1)) - 2

    for i in range(2, n):
        selector = 1 << (i - 1)
        if (selector & arr) == 0:
            continue

        # We have a prime
        composite = selector
        while (composite := composite << i) < arr:
            arr = arr & (~composite)

    primes = []
    for i in range(n):
        if (arr >> i) & 1 == 1:
            primes.append(i+1)

    return primes

对我的运行时的一些分析：

的曲线y = nlog(log(n))（红线这是更陡）和y = x（蓝线这是较不陡峭的）：

我通常不会使用大小超过 uint64 的整数，因为 python 允许无限大小的整数，而我只是在测试，我使用了上述方法。正如我所说，我试图理解为什么算法时间会随着问题大小呈指数增长n。

Answer 1

我使用整数位图作为数组

那是极其昂贵的。Python int 是不可变的。每次您想要切换一点时，您都​​在构建一个全新的巨大 int。

您还需要建立其他巨头整数刚刚访问您感兴趣的单位-例如，composite和~composite是巨大的arr = arr & (~composite)，即使你只在1位感兴趣。

使用实际的可变序列类型。也许是一个列表，也许是一个 NumPy 数组，也许是 PyPI 中的某种位向量类型，但不要使用int.