java - 为什么与 Java 或 C# 中的相同算法相比，Python 中的素数筛如此慢？

Question

我正在尝试为欧拉项目解决方案构建一个筛子。 我需要高达大约 100M 的素数，最好可以选择更高的值。

我的这个实现工作正常，但非常慢:

class Primes:
__size = None
__sieve = []
__primes = []

def __init__(self, size):
    self.__size = size
    self.__sieve = [True] * size
    for x in range(2, size):
        if self.__sieve[x]:
            self.foundPrime(x);

def foundPrime(self, x):
    self.__primes.append(x)
    for duplicate in range(2 * x, self.__size, x):
        self.__sieve[duplicate] = False

对于大小为 100M 的筛子，在我相当高端的计算机上，此初始化大约需要 70 秒。有谁知道为什么？因为在 Java 和 C# 中，这花了我大约 1 秒...

所以，这篇文章与其他文章不同的是，我不想知道如何实现算法，我想了解为什么它在 Python 中这么慢。

一些打印给我的信息是，大约 50% 的时间花在寻找前 100K 个素数上。

Answer 1

在各种基准测试中，无论其值(value)如何，Python 的速度与 Java 的速度相同，甚至慢 50 倍，具体取决于问题。这主要是由于 Python 被解释，Java 被编译(即使不是 native )。 Ruby 的得分与 Python 相似。

语言设计也给 Java 和 C# 带来了一些优势。

除了更高效的 Python 方法之外，还有两种加快速度的好方法:使用 pypy，它本质上是对 Python 进行字节编译，类似于 Java，或者用更快的语言(例如 C)编写关键部分，然后从 Python 调用这些例程，如果您擅长快速语言，那么这项任务实际上非常简单。