python - 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。

标签： pythonpython-3.xalgorithmtime-complexityprimes

Answer 1

我使用整数位图作为数组

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

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

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