Моя программа python выполняется быстрее, чем моя java-версия одной и той же программы. Что дает?

Вы на самом деле не тестируете Java vs. Python, вы тестируете java.util.HashSet используя встроенные в autoboxed целые числа и собственный набор Python и целочисленную обработку.

По-видимому, сторона Python в этом конкретном микрообъекте действительно быстрее.

Я попытался заменить HashSet на TIntHashSet из GNU TIntHashSet и получил коэффициент ускорения между 3 и 4, что привело Java немного впереди Python.

Реальный вопрос: действительно ли ваш примерный код как представитель вашего кода приложения, как вы думаете. Запустили ли вы профилировщик и определили, что большая часть времени процессора тратится на то, чтобы разместить огромное количество ints в HashSet? Если нет, то пример не имеет значения. Даже если только разница в том, что ваш производственный код хранит другие объекты, кроме int, их создание и вычисление их хэш-кода могут легко доминировать над установленной установкой (и полностью уничтожить преимущество Python при обработке ints специально), что делает весь этот вопрос бессмысленным.

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

Это не обязательно плохо! Напротив, в таблице размера 2 ** i, принимая младшие биты i, поскольку индекс начальной таблицы является чрезвычайно быстрым, и никаких столкновений вообще нет для индексов, проиндексированных непрерывным диапазоном int. То же самое примерно верно, когда клавиши являются «последовательными» строками. Таким образом, это дает лучшее, чем случайное поведение в обычных случаях, и это очень желательно.

Этот микрообъект является одним из лучших для Python, потому что он приводит к точно нулевым хэш-коллизиям. Принимая во внимание, что если Javas HashSet переигрывает ключи, он должен выполнить дополнительную работу, а также столкнется с худшим поведением с коллизиями.

Если вы храните диапазон (итерации) во временной переменной и выполняете random.shuffle на нем перед циклом, время выполнения более чем на 2 раза медленнее, даже если перемещение и создание списка выполняется вне цикла.

Другим возможным объяснением является то, что наборы в Python реализованы изначально в коде C, а HashSet в Java реализованы в самой Java. Таким образом, наборы в Python должны быть существенно быстрее.

Как правило, мой опыт заключался в том, что программы python работают быстрее, чем java-программы, несмотря на то, что java – это немного более низкий уровень. Случайно, оба языка скомпилированы в байтовый код (вот что такое .pyc-файл – вы можете думать о них как о подобных файлах .class). Оба языка – это байт-код, интерпретируемый на виртуальной машине стека.

Вы ожидаете, что python будет медленнее в таких вещах, как, например, ab . В java это ab решится на разыменование. С другой стороны, Python должен делать один или несколько запросов хеш-таблицы: проверять локальную область, проверять область модуля, проверять глобальную область, проверять встроенные функции.

С другой стороны, java, как известно, плохо работает при определенных операциях, таких как создание объектов (что, вероятно, является виновником в вашем примере) и сериализации.

Таким образом, нет простого ответа. Я бы не ожидал, что любой язык будет быстрее для всех примеров кода.

Исправление: несколько человек указали, что java не так уж плох при создании объекта. Итак, в вашем примере это что-то еще. Возможно, это autoboxing, что дорого, возможно, алгоритм хэширования по умолчанию для python лучше в этом случае. В моем практическом опыте, когда я переписываю java-код на python, я всегда вижу увеличение производительности, но это может быть так же, как из-за языка, так как это связано с переписыванием в целом, что приводит к повышению производительности.

Я хотел бы развеять пару мифов, которые я видел в ответах:

Java компилируется, да, в байт-код, но, в конечном счете, в собственный код в большинстве сред выполнения. Люди, которые говорят, что C по своей природе быстрее, не рассказывают всю историю, я мог бы сделать случай, когда байт-скомпилированные языки по своей природе быстрее, потому что компилятор JIT может создавать оптимизацию, зависящую от машины, которая недоступна компиляторам с опережением времени.

Несколько вещей, которые могут сделать различия:

• Хэш-таблицы и наборы Python являются наиболее сильно оптимизированными объектами в Python, а хэш-функция Python предназначена для возврата аналогичных результатов для аналогичных входов: хеширование целого числа возвращает целое число, гарантируя, что вы НИКОГДА не увидите столкновение в хеш-таблице последовательных целые числа в Python.
• Второе влияние вышеизложенного заключается в том, что код Python будет иметь высокую локальность ссылки, поскольку вы будете последовательно обращаться к хеш-таблице.
• Java привносит некоторые причудливые бокс и распаковку целых чисел, когда вы добавляете их в коллекции. На стороне бонуса это делает арифметический путь быстрее в Java, чем Python (пока вы держитесь подальше от bignums), но с другой стороны это означает больше распределений, чем вы привыкли.

Изменить: TreeSet может быть быстрее для реального использования, в зависимости от шаблонов распределения. Мои комментарии ниже относятся только к этому упрощенному сценарию. Однако я не считаю, что это будет иметь очень важное значение. Реальная проблема лежит в другом месте.

Несколько человек здесь рекомендовали заменить HashSet на TreeSet. Это звучит для меня очень странным советом, поскольку структура данных с временем ввода O (log n) быстрее, чем структура O (1), которая предопределяет достаточное количество ведер для хранения всех элементов.

Вот некоторый код для сравнения:

 import java.util.*; class SpeedTest { public static void main(String[] args) { long startTime; long totalTime; int iterations = 10000000; Set counts; System.out.println("HashSet:"); counts = new HashSet((2*iterations), 0.75f); startTime = System.currentTimeMillis(); for(int i=0; i<iterations; i++) { counts.add(i); } totalTime = System.currentTimeMillis() - startTime; System.out.println("TOTAL TIME = "+( totalTime/1000f) ); System.out.println(counts.size()); counts.clear(); System.out.println("TreeSet:"); counts = new TreeSet(); startTime = System.currentTimeMillis(); for(int i=0; i<iterations; i++) { counts.add(i); } totalTime = System.currentTimeMillis() - startTime; System.out.println("TOTAL TIME = "+( totalTime/1000f) ); System.out.println(counts.size()); } } 

И вот результат на моей машине:

 $ java -Xmx1024M SpeedTest HashSet: TOTAL TIME = 4.436 10000000 TreeSet: TOTAL TIME = 8.163 10000000 

Несколько человек также утверждали, что бокс – это не проблема производительности, и создание объекта является недорогим. Хотя верно, что создание объектов происходит быстро, это определенно не так быстро, как примитивы:

 import java.util.*; class SpeedTest2 { public static void main(String[] args) { long startTime; long totalTime; int iterations = 10000000; System.out.println("primitives:"); startTime = System.currentTimeMillis(); int[] primitive = new int[iterations]; for (int i = 0; i < iterations; i++) { primitive[i] = i; } totalTime = System.currentTimeMillis() - startTime; System.out.println("TOTAL TIME = "+( totalTime/1000f) ); System.out.println("primitives:"); startTime = System.currentTimeMillis(); Integer[] boxed = new Integer[iterations]; for (int i = 0; i < iterations; i++) { boxed[i] = i; } totalTime = System.currentTimeMillis() - startTime; System.out.println("TOTAL TIME = "+( totalTime/1000f) ); } } 

Результат:

 $ java -Xmx1024M SpeedTest2 primitives: TOTAL TIME = 0.058 primitives: TOTAL TIME = 1.402 

Более того, создание множества объектов приводит к дополнительным накладным расходам от сборщика мусора. Это становится значительным, когда вы начинаете хранить десятки миллионов живых объектов в памяти.

Я считаю, что такие тесты не имеют смысла. Я не решу проблемы, похожие на тестовые. Это не очень интересно.

Я бы скорее увидел решение для значимого решения линейной алгебры с использованием NumPy и JAMA. Может быть, я попробую и отчитаю результаты.

Я не слишком хорошо знаком с python, но я знаю, что HashSet не может содержать примитивы, поэтому, когда вы говорите, что counts.add(i) i получаю autoboxed в new Integer(i) вызов new Integer(i) . Вероятно, это ваша проблема.

Если по какой-то причине вам действительно нужен «набор» целых чисел между 0 и некоторым большим n, его, вероятно, лучше всего объявить как «boolean [] set = new boolean [n]». Затем вы можете пройти через массив и пометить элементы, которые находятся в наборе как «истина», не налагая накладные расходы на создание n объектов-оболочек Integer. Если вы хотите пойти дальше, вы можете использовать байт [] размера n / 8 и напрямую использовать отдельные биты. Или, может быть, BigInteger.

РЕДАКТИРОВАТЬ

Прекратите голосовать за мой ответ. Это не правильно.

РЕДАКТИРОВАТЬ

Нет, это неправильно. Я получаю сопоставимую производительность, если я делаю то, что предлагает этот вопрос, заполняя набор с помощью N целых чисел. если я заменил содержимое цикла for следующим:

  Integer[] ints = new Integer[N]; for (int i = 0; i < N; ++i) { ints[i] = i; } 

Затем это занимает всего 2 секунды. Если вы вообще не храните Integer, это занимает менее 200 миллисов. Принудительное выделение объектов 10000000 Integer занимает некоторое время, но похоже, что большую часть времени тратится на операцию ввода HashSet.

Здесь есть несколько вопросов, которые я хотел бы объединить.

Во-первых, если это программа, которую вы собираетесь запускать только один раз, имеет ли значение, что требуется несколько секунд?

Во-вторых, это всего лишь один микроцентриф. Microbenchmarks бессмысленны для сравнения производительности.

У автозапуска имеется ряд проблем.

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

Если вы не установили -Xms вы можете запускать GC только для изменения размера кучи. Возможно также, что куча должным образом рассчитана с самого начала.

Это правда, что Java начинает интерпретировать и компилирует. Около 1500 итераций для Sun client [C1] Точка доступа и 10 000 для сервера [C2]. Сервер Hotspot даст вам лучшую производительность в конечном итоге, но возьмет больше памяти. Мы можем видеть сервер использования Hotspot клиента для очень часто исполняемого кода для лучшего из обоих миров. Однако обычно это не вопрос секунд.

Самое главное, вы можете создавать два объекта на итерацию. Для большинства кода вы не будете создавать эти крошечные объекты для такой части исполнения. TreeSet может быть лучше по количеству объектов, с 6u14 и Harmony становится еще лучше.

Возможно, Python может выиграть, сохранив мелкие целые объекты в ссылках вместо фактического наличия объекта. Это, несомненно, хорошая оптимизация.

Проблема с множеством эталонных тестов заключается в том, что вы смешиваете множество разных кодов одним способом. Вы не будете писать код, о котором вы так беспокоились, не так ли? Итак, почему вы пытаетесь выполнить тест производительности, который отличается от кода, который вы действительно хотели бы запустить быстро?

Лучшая структура данных: что-то вроде BitSet , казалось бы, имеет смысл (хотя на нем есть синхронизация, что может или не может повлиять на производительность).

Вам нужно запустить его несколько раз, чтобы получить реальную идею о том, «как быстро» каждый работает. Время запуска JVM [для одного] добавляет к единому времени выполнения версии Java.

Вы также создаете HashSet с большой начальной пропускной способностью, что означает, что HashMap будет создан с таким количеством доступных слотов, в отличие от Python, где вы создаете базовый Set. Трудно сказать, будет ли это мешать, поскольку, когда ваш HashSet растет, ему придется перераспределять сохраненные объекты.

Вы используете флаг -server с jvm? Вы не можете проверить производительность без него. (Вы также должны разогреть jvm перед тем, как пройти тест.)

Кроме того, вы, вероятно, захотите использовать TreeSet<Integer> . В конечном итоге HashSet будет медленнее.

И какой jvm вы используете? Надеюсь, самое новое.

РЕДАКТИРОВАТЬ

Когда я говорю использовать TreeSet, я имею в виду, в общем, не для этого теста. TreeSet обрабатывает проблему реального мира без четкого хэширования объектов. Если вы получаете слишком много объектов в одном ящике в HashSet, вы будете выполнять около O (n).

Если вы действительно хотите хранить примитивные типы в наборе и выполнять тяжелую работу над этим, сверните свой собственный набор в Java. Родовые классы недостаточно быстры для научных вычислений.

Как упоминает Ants Aasma, Python обходит хеширование и использует целое число напрямую. Java создает объект Integer ( autoboxing ), а затем передает его объекту (в вашей реализации). Этот объект также должен быть хэширован для использования в хэш-наборе.

Для веселого сравнения попробуйте следующее:

Ява

 import java.util.HashSet; class SpeedTest { public static class Element { private int m_i; public Element(int i) { m_i = i; } } public static void main(String[] args) { long startTime; long totalTime; int iterations = 1000000; HashSet<Element> counts = new HashSet<Element>((int)(2*iterations), 0.75f); startTime = System.currentTimeMillis(); for(int i=0; i<iterations; ++i) { counts.add(new Element(i)); } totalTime = System.currentTimeMillis() - startTime; System.out.println("TOTAL TIME = "+( totalTime/1000f) ); System.out.println(counts.size()); } } 

Результаты:

 $java SpeedTest TOTAL TIME = 3.028 1000000 $java -Xmx1G -Xms1G SpeedTest TOTAL TIME = 0.578 1000000 

питон

 #!/usr/bin/python import time import sys class Element(object): def __init__(self, i): self.num = i def main(args): iterations = 1000000 counts = set() startTime = time.time(); for i in range(0, iterations): counts.add(Element(i)) totalTime = time.time() - startTime print 'total time =',totalTime print len(counts) if __name__ == "__main__": main(sys.argv) 

Результаты:

 $./speedtest.py total time = 20.6943161488 1000000 

Как это для «python быстрее, чем java»?

Сколько памяти вы начали с JVM? Это зависит? Когда я запускаю JVM с вашей программой с 1 гигабайтом оперативной памяти:

 $ java -Xmx1024M -Xms1024M -classpath . SpeedTest TOTAL TIME = 5.682 10000000 $ python speedtest.py total time = 4.48310899734 10000000 

Если я запускаю JVM с меньшим объемом памяти, это занимает больше времени … значительно дольше:

 $ java -Xmx768M -Xms768M -classpath . SpeedTest TOTAL TIME = 6.706 10000000 $ java -Xmx600M -Xms600M -classpath . SpeedTest TOTAL TIME = 14.086 10000000 

Я думаю, что HashSet является узким местом производительности в этом конкретном случае. Если я заменил HashSet на LinkedList , программа будет значительно быстрее.

Наконец – обратите внимание, что Java-программы изначально интерпретируются, и компилируются только те методы, которые вызывают много раз. Таким образом, вы, вероятно, сравниваете Python с интерпретатором Java, а не с компилятором.

Просто удар в темноте здесь, но некоторые оптимизации, которые Python делает для этой Java, вероятно, не таковы:

• Вызов range () в Python создает все 10000000 целых объектов одновременно, в оптимизированном C-коде. Java должна создавать объект Integer на каждой итерации, что может быть медленнее.
• В Python ints неизменяемы, поэтому вы можете просто сохранить ссылку на глобальную «42», например, вместо выделения слота для объекта. Я не уверен, как сравниваются объекты Java Integer с ядром.
• Многие из встроенных алгоритмов Python и структуры данных довольно сильно оптимизированы для особых случаев. Например, хеш-функция для целых чисел – это просто функция тождества. Если Java использует более «умную» хеш-функцию, это может немного замедлить работу. Если большая часть вашего времени будет потрачена на код структуры данных, я бы не удивился, увидев Python beat Java, учитывая объем усилий, потраченных на протяжении многих лет на настройку Python C.

Несколько изменений для более быстрого Python.

 #!/usr/bin/python import time import sys import psyco #<<<< psyco.full() class Element(object): __slots__=["num"] #<<<< def __init__(self, i): self.num = i def main(args): iterations = 1000000 counts = set() startTime = time.time(); for i in xrange(0, iterations): counts.add(Element(i)) totalTime = time.time() - startTime print 'total time =',totalTime print len(counts) if __name__ == "__main__": main(sys.argv) 

До

 (env)~$ python speedTest.py total time = 8.82906794548 1000000 

После

 (env)~$ python speedTest.py total time = 2.44039201736 1000000 

Теперь какой-то хороший старый обман и …

 #!/usr/bin/python import time import sys import psyco psyco.full() class Element(object): __slots__=["num"] def __init__(self, i): self.num = i def main(args): iterations = 1000000 counts = set() elements = [Element(i) for i in range(0, iterations)] startTime = time.time(); for e in elements: counts.add(e) totalTime = time.time() - startTime print 'total time =',totalTime print len(counts) if __name__ == "__main__": main(sys.argv) (env)~$ python speedTest.py total time = 0.526521921158 1000000 

Я согласен с Гэндалом относительно времени запуска. Кроме того, вы выделяете огромный HashSet, который совсем не похож на ваш код на Python. Я создаю изображение, если вы положите его под профилировщик, там будет потрачен хороший кусок времени. Кроме того, вставка новых элементов действительно будет медленной с этим размером. Я бы посмотрел на TreeSet, как было предложено.

Самой большой проблемой, вероятно, является то, что данный код измеряет время на стене – то, что ваши часовые меры – но то, что должно быть измерено для сравнения времени выполнения кода, – это время процесса – время, затрачиваемое процессором на выполнение этого конкретного кода, а не другое задания.

Вы можете сделать Java microbenchamrk намного быстрее, добавив просто немного лишнее.

  HashSet counts = new HashSet((2*iterations), 0.75f); 

становится

  HashSet counts = new HashSet((2*iterations), 0.75f) { @Override public boolean add(Object element) { return false; } }; 

Простой, быстрый и получает тот же результат.

You might want to see if you can "prime" the JIT compiler into compiling the section of code you're interested in, by perhaps running it as a function once beforehand and sleeping briefly afterwords. This might allow the JVM to compile the function down to native code.

Well, if you're going to tune the Java program, you might as well tune the Python program too.

 >>> import timeit >>> timeit.Timer('x = set()\nfor i in range(10000000):\n x.add(i)').repeat(3, 1) [2.1174559593200684, 2.0019571781158447, 1.9973630905151367] >>> timeit.Timer('x = set()\nfor i in xrange(10000000):\n x.add(i)').repeat(3, 1) [1.8742368221282959, 1.8714439868927002, 1.869229793548584] >>> timeit.Timer('x = set(xrange(10000000))').repeat(3, 1) [0.74582195281982422, 0.73061800003051758, 0.73396801948547363] 

Just using xrange makes it about 8% faster on my machine. And the expression set(xrange(10000000)) builds exactly the same set, but 2.5x faster (from 1.87 seconds to 0.74).

I like how tuning a Python program makes it shorter. 🙂 But Java can do the same trick. As everyone knows, if you want a dense set of smallish integers in Java, you don't use a hash table. You use a java.util.BitSet !

 BitSet bits = new BitSet(iterations); startTime = System.currentTimeMillis(); bits.set(0, iterations, true); totalTime = System.currentTimeMillis() - startTime; System.out.println("TOTAL TIME = "+( totalTime/1000f) ); System.out.println(bits.cardinality()); 

That should be fairly quick. Unfortunately I don't have the time to test it right now.