Python очень медленный по сравнению с Java для этого алгоритма

Я изучаю алгоритмы и решил перенести Java-программы из учебника на Python, так как мне не нравятся накладные расходы Java, особенно для небольших программ, и как упражнение.

Сам алгоритм очень прост, он просто берет все триплеты из массива с помощью грубой силы и подсчитывает, сколько триплетов суммируется до нуля (например: [-2,7, -5])

public static int count(int[] a) { int N = a.length; int cnt = 0; for (int i = 0; i < N; i++) { for (int j = i+1; j < N; j++) { for (int k = j+1; k < N; k++) { if (a[i] + a[j] + a[k] == 0) { cnt++; } } } } return cnt; } 

Я поместил его в:

 def count(a): cnt = 0 ln = len(a) for i in xrange(0,ln): for j in xrange(i + 1,ln): for k in xrange(j + 1,ln): if a[i] + a[j] + a[k] == 0: cnt+=1 return cnt 

Теперь, измеряя только эти функции, берут:

 java : array of 2000 elements --> 3 seconds python : array of 2000 elements --> 2 minutes, 19 seconds UPDATE python (pypy) : array of 2000 elements --> 4 seconds ( :-) ) 

Конечно, это не очень хороший алгоритм, он просто показывает, как здесь, так и в учебнике. Раньше я программировал как на Java, так и на Python, но не знал об этой огромной разнице.

Вопрос сводится к следующему: как преподносить это? Более конкретно:

  1. Является ли этот код хорошим портом, или я пропускаю что-то тривиальное?
  2. Переключение на другое исполняемое Jython, например, решение? Легко ли сохранить мою кодовую базу в eclipse и просто добавить интерпретатор (компилятор?)? Или переключение на другой интерпретатор / компилятор только улучшит ситуацию?

Прямо сейчас я использую python 2.7.3 и Java 1.7 32bts в Windows 7.

Я знаю, что там есть похожие вопросы о SO о производительности java / python, но ответы, как есть, в среде python для разных приложений, для меня сейчас не очень полезны.

То, что я хочу знать, – это то, что некоторые из этих промежутков времени могут закрыть этот огромный разрыв и заслуживают внимания?

ОБНОВИТЬ :

Я установил pypy, и теперь различия огромны …

ОБНОВЛЕНИЕ 2:

Некоторые очень интересные вещи, которые я заметил: метод islice в ответе здесь быстрее на «регулярном» питоне, но намного медленнее на pypy. Несмотря на это, pypy все еще остается намного быстрее, используя независимо от того, использует ли он обычные петли или стихи в этом алгоритме

Поскольку Bakuriu замечает, что среда исполнения во время выполнения может иметь большое значение, но среда выполнения быстрее для этого алгоритма не обязательно быстрее для любого алгоритма …

3 Solutions collect form web for “Python очень медленный по сравнению с Java для этого алгоритма”

Попробуйте запустить его с PyPy вместо CPython. Скорее всего, это произойдет гораздо быстрее.

Я также реализовал функцию в C и PHP. Вот результат:

PHP : 23.977946043015 сек.
Python : 19.31 сек.

C : 0,4 с
Java : 0,42 секунды

Мы изучаем язык с системой различного типа. PHP и Python динамически типизируются, тогда как C и Java статически типизируются.

Таким образом, интерпретатор PHP и Python много времени угадывает тип используемых переменных и, следовательно, работает очень медленно. В то время как в C и Java тип переменных (и элементов массива) является статическим, т.е. целочисленным, и, следовательно, время угадывания сохраняется. И, судя по всему, это время угадывания слишком велико, как вы можете видеть из приведенных выше цифр.

С PyPY время угадывания значительно сокращается, потому что PyPY использует компиляцию Just In Time (JIT). Этот метод очень хорош в том, чтобы угадывать тип используемой переменной и, следовательно, вы получаете балл производительности.

Как уже было сказано в комментариях вашего стартового сообщения, нет хорошего способа сделать это намного быстрее (помимо PyPy). Вы можете попробовать islice, который будет перебирать «a», а не создавать новые списки или диапазоны, это должно быть быстрее.

 from itertools import islice def count(a): cnt = 0 for x, i in enumerate(islice(a,0, None)): for y, j in enumerate(islice(a, x + 1, None)): for k in islice(a, y + x + 2, None): if i + j + k == 0: cnt+=1 return cnt 
  • Хорошая книга для ученика 12 лет?
  • Au revoir, Python?
  • Иррациональное представление чисел на любом языке программирования?
  • Почему нам не нужны интерфейсы в динамических языках?
  • Создает ли Python весь связанный метод для каждого нового экземпляра?
  • Python, PyTables, Java - связывание всех
  • Python / Java-скрипт для загрузки всех файлов .pdf с веб-сайта
  • Какой язык проще всего и быстрее работает с XML-контентом?
  • как перевернуть бит в определенной позиции в целое число на любом языке
  • Эмуляторная платформа
  • Как представить файл jar в виде сетевого графика?
  • Python - лучший язык программирования в мире.