Скорость реализации Java и Python

Question

У меня есть проблема, которую я уже решил как в python, так и в java. Проблема заключается в том, для таблицы умножения 8000 * 8000 элементов, найти все уникальные номера:

Python:

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) 

Java:

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); 
    } 
} 

Я нашел, что это удивительно, что реализация Java занял второе место, и версия Python заняла минуту. Есть ли способ повысить производительность python, чтобы он стал ближе к скорости реализации Java?

Answer 1

Ваш код Python не является оптимальным, вы бы не решить проблему так же, как и в Java:

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 на моем компьютере. Но ясно, что python занимает больше времени для математических задач, потому что у Python нет встроенного 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.8s. В отличие от версии C, для которой требуется всего 0,6 с.

Answer 2

Python может быть медленнее, но рассмотреть следующие два фрагмента, как все больше вещий:

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))) 

Python не предназначен, чтобы быть быстрый. Преимущество питона является то, что вы можете написать

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

в основном однострочник, который четко решает основную математическую задачу, а именно: определение набора и печать его мощности.

Answer 3

Проблема заключается в том, как вы создаете свой массив в python.

Рассмотрим следующий пример:

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, упомянутое в комментариях).