Python大整数表现

Question

我想在 python 中编写素数生成器的代码 - 我只在 C 和 Java 中完成过此操作。我做了以下事情。我使用整数位图作为数组。 Performance of the algorithm should increase nlog(log(n)) 但随着问题规模 n 的增加，我看到 cost/time 呈指数增长。当整数变得比实际更大时，我没有看到或不知道 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

I used an integer bitmap as an array

那太贵了。 Python 整数是不可变的。每次您想切换一点时，您都在构建一个全新的巨大整数。

您还需要构建其他巨型整数来访问您感兴趣的单个位 - 例如，composite 和 ~composite 在 arr = arr & (~composite) 中是巨大的，即使您只对1位感兴趣

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

Python大整数表现

Python large integer performance

python

algorithm

primes

time-complexity

python-3.x