Java와 Python 구현의 속도

Question

그래서 파이썬과 자바에서 이미 해결 한 문제가 있습니다.

파이썬 : 문제는 모든 고유 번호를 찾을 수 8000 개 * 8000 개 요소의 곱셈 테이블입니다

table = 8000 
unique_prods = [] 
start = 1 

for i in range(table*table + 1): 
    unique_prods.append(0) 

for x in range(1, table + 1): 
    for y in range(start, table + 1): 
     # print '{:4}'.format(x * y), 
     if not unique_prods[x * y] == x * y: 
      unique_prods[x * y] = x * y 
    start += 1 
    # print 

# print unique_prods 
print len(unique_prods) 

자바 : 나는 놀라운 것을 발견

public class Test { 
    public static void main(String[] args) { 
     int table = 8000; 
     int [] myArray = new int[table*table + 1]; 
     int count = 1; 

     for (int i = 0; i < table*table + 1; i++) { 
      myArray[i] = 0; 
     } 

     for (int x = 1; x < table + 1; x++) { 
      for (int y = count; y < table + 1; y++) { 
       if (! (myArray[x * y] == x * y)) { 
        myArray[x * y] = x * y; 
       } 
      } 
      count += 1; 
//   System.out.println(count); 
     } 

     count = 0; 
     for (int i = 0; i < table*table + 1; i++) { 
      if(myArray[i] != 0) { 
       count += 1; 
      } 
     } 

     System.out.println(count); 
    } 
} 

자바 구현 잠깐, 파이썬 버전은 1 분 이상 걸렸다. 파이썬 성능을 향상시켜 Java 구현 속도에 더 가깝게 할 수있는 방법이 있습니까?

Answer 1

귀하의 파이썬 코드가 최적이 아닌, 당신은 자바로 문제 같은 방법으로 해결할 수없는 것 :

table = 8000 
unique_prods = set() 

for x in range(1, table + 1): 
    for y in range(x, table + 1): 
     unique_prods.add(x * y) 
print len(unique_prods) 

내 컴퓨터에 14S 걸립니다. 파이썬은 단순한 수학적 문제에 더 오래 걸립니다. 파이썬에는 통합 된 JIT 컴파일러가 없기 때문입니다. 계산을 위해 numpy라고하는 패키지가 있습니다.

import numpy 
x = numpy.arange(1,8001) 
unique_prods = numpy.zeros(8000*8000+1,dtype='b') 
for k in x: 
    unique_prods[k*x[k-1:]]=1 
print unique_prods.sum() 

그리고 결과는 0.8 초입니다. 0.6 버전 만 필요로하는 C 버전과는 대조적입니다.

Answer 2

파이썬 속도가 느려질 수 있지만, 더 파이썬으로 다음과 같은 두 조각 고려할 수 : 반드시 빠른

import time 
starttime = time.time() 
table = 8000 
unique_prods = [0] * (table*table + 1) 
for x in range(1, table+1): 
    for y in range(1, table+1): 
     unique_prods[x*y] = 1 

elapsed = time.time() - starttime 
print((elapsed, sum(unique_prods))) 

및 간단한,하지만을 :

starttime = time.time() 
table = 8000 
unique = set(x*y for x in range(1, table+1) for y in range(1,table+1)) 
elapsed = time.time() - starttime 
print((elapsed, len(unique))) 

파이썬이 될하도록 설계되지 않았습니다 가장 빠른. 파이썬의 장점은 명확하게, 즉 세트를 정의하고 그 카디 나리 인쇄, 기본 수학 문제를 해결 기본적으로 한 - 라이너로

unique = set(x*y for x in range(1, table+1) for y in range(1,table+1)) 
print(len(unique)) 

를 쓸 수 있다는 것입니다.

Answer 3

문제는 파이썬에서 배열을 만드는 방법과 같습니다.

는 다음과 같은 고려 :

array = [] 

for i in range(8000*8000 + 1): 
    array.append(0) 

이것은 우리가 처음 하늘의 배열을 만들 수 있기 때문에 (나를 위해 14S)를 실행 한 다음 그것을 64000001 배의 총 크기를 조정하는 데 오랜 시간이 걸렸습니다. 대신이 일을 하나의 메모리 할당이 필요 있도록 올바른 크기의 배열을 만들어야합니다

array = [0] * (8000*8000 + 1) // Creates an array filled with zeros of size (8000*8000 + 1) 

이 코드는 나를 위해 거의 즉시 달렸다.

Answer 4

다른 사람들도 알다시피, 목록을 확장하는 방법은 Java 알고리즘 구현에 유리한 점입니다.이 간단한 수정 :

unique_prods = [0] * (table*table + 1) 

는 (그렇지 않으면 정확히 당신 같은 게시 한 구현) 알고리즘의 다음과 같은 결과를 얻을 수 :

python -m timeit -n 10 -r 1 "import test" "test.testWithFix()" 
64000001 
64000001 
64000001 
64000001 
64000001 
64000001 
64000001 
64000001 
64000001 
64000001 
10 loops, best of 1: 31.6 sec per loop 

---

python -m timeit -n 10 -r 1 "import test" "test.testWithoutFix()" 
64000001 
64000001 
64000001 
64000001 
64000001 
64000001 
64000001 
64000001 
64000001 
64000001 
10 loops, best of 1: 62.9 sec per loop 

을 또한, 모두 당신의 구현 틀렸거나 (세트를 사용해야 함) 다른 부정확 한 부정확성이 있습니다 (예 : 설명에 중복 된 if 문이 언급 됨).