java - Python 列表与 Java 数组效率

Question

这个问题已经有答案了:

Fastest way to list all primes below N (40 个回答)

已关闭 8 年前。

我从 Java 开始尝试学习 Python。我实现了Sieve of Eratosthenes首先用Java 编写算法，然后用Python 编写。我的 Java 实现运行得相当快，我可以在大约 25 秒内找到十亿以下的所有素数。我的 Python 实现可能需要大约 2 个小时才能完成同样的事情。

我在这里包含了这两种实现。我的问题是:

1. 为什么 Python 的执行速度这么慢？ (我知道我做错了)
2. Python 是否可以像 Java 一样快地执行此操作？

我认为缓慢的原因是在 Python 实现中使用列表，但我对 Python 太陌生，不知道如何解决这个问题。

JAVA:

/**
 * Creates a boolean array of a specified size with true values at prime indices and
 * false values at composite indices.
 */
private static boolean[] sieve(int size){
    boolean[] array = new boolean[size];

    //Assume all numbers greater than 1 are prime//
    for(int i = 2; i < array.length; i++){ 
        array[i] = true;
    }

    //Execute Sieve of Eratosthenes algorithm//
    for(int p = 2; p < size; p = nextPrimeInArray(array, p)){ 
        for(int i = p + p; i < size; i += p){
            array[i] = false; // i.e., mark as composite
        }
    }

    return array;
}

/**
 * Finds the next index in the array that is not marked composite
 */
public static int nextPrimeInArray(boolean[] array, int p){

    do{
        p++;
    }while(p < array.length && !array[p]);
    return p;
}

Python:

def getPrimeList(limit):
    """returns a list of True/False values, where list[i] is True if i is prime and False otherwise"""
    primes = []

    # Initially assume all numbers in the list are prime
    for i in range(limit):
        primes.append(True)

    # Set 0 and 1 to False
    primes[0] = False
    primes[1] = False

    for p in range(2, limit):
        for i in range(p + p, limit, p):
            primes[i] = False
        p = nextPrimeInList(primes, p)
    return primes

def nextPrimeInList(list, p):
    """Helper method for getPrimeList that finds the next index in list not marked composite"""
    p += 1
    while p < len(list) and not list[p]:
        p += 1
    return p

Answer 1

我不是Python专家，但我会尽力给你一个像样的答案。

首先，Python 是一种脚本语言，这使得它比任何编译语言(例如 Java)都要慢。例如，无法对循环执行许多优化，并且对于非常大的循环，它可能会减慢代码速度。然而，我知道 Python 的某些实现中也存在预编译，并且执行的实际上是像 Java 中的字节码，所以也许差异并不那么显着。

然后，我认为你可以通过从一开始就为列表分配正确的大小来加速你的 Python 版本(我相信 Python 列表实际上是数组):

 primes = [True] * limit