파이썬리스트 대 자바 어레이 효율성

Question

나는 파이썬을 배우려고 자바에서왔다. 나는 먼저 Sieve of Eratosthenes 알고리즘을 Java로 구현 한 다음 Python으로 구현했습니다. 내 Java 구현은 매우 빠르게 실행되며 약 25 초 만에 10 억 미만의 모든 소수를 찾을 수 있습니다. 내 Python 구현은 아마도 같은 일을하는 데 약 2 시간이 걸릴 것이다.

여기에 두 가지 구현을 모두 포함 시켰습니다. 제 질문은 다음과 같습니다 :

1. 왜 파이썬 구현은 왜 그렇게 느립니다? (내가 뭔가 잘못하고있다는 것을 알고있다.)
2. 파이썬이 자바처럼 빨리 이것을 할 수 있는가?

나는 파이썬 된 구현에 목록을 사용하여 주위의 속도 저하 센터를 가정하지만, 나는이 문제를 얻는 방법을 알고 파이썬에 너무 새로운입니다.

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

내가 파이썬에서 전문가가 아니에요하지만 난 당신에게 알맞은 대답을하려고합니다.

먼저 파이썬은 스크립팅 언어이므로 컴파일 된 언어 (예 : Java)보다 느려집니다. 예를 들어 루프에 대한 많은 최적화 작업을 수행 할 수 없으며 매우 큰 루프의 경우 코드 속도가 느려질 수 있습니다. 그러나 파이썬의 특정 구현에 사전 컴파일이 존재하며 실행되는 것은 실제로 자바와 같은 바이트 코드이므로 실제로 그 차이는 그리 중요하지 않다는 것을 알고 있습니다. 그런 다음

, 나는 (내가 파이썬 목록이 실제로 배열 인 생각) 당신이 시작을 다시 한번 확인 목록에 적합한 크기를 할당하여 파이썬 버전을 속도를 수 있다고 생각 :

primes = [True] * limit