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

Возможно, вы захотите посмотреть, сможете ли вы «подготовить» JIT-компилятор к компиляции интересующего вас участка кода, возможно, запустив его как функцию один раз заранее и ненадолго засыпав после слов. Это может позволить JVM скомпилировать функцию до собственного кода.

Вы можете сделать 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; }
    };

простым, быстрым и дает тот же результат.

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

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

Just a stab in the dark here, but some optimizations that Python is making that Java probably isn't:

• The range() call in Python is creating all 10000000 integer objects at once, in optimized C code. Java must create an Integer object each iteration, which may be slower.
• In Python, ints are immutable, so you can just store a reference to a global "42", for example, rather than allocating a slot for the object. I'm not sure how Java boxed Integer objects compare.
• Many of the built-in Python algorithms and data structures are rather heavily optimized for special cases. For instance, the hash function for integers is, simply the identity function. If Java is using a more "clever" hash function, this could slow things down quite a bit. If most of your time is spent in data structure code, I wouldn't be surprised at all to see Python beat Java given the amount of effort that has been spent over the years hand-tuning the Python C implementation.

Сколько памяти вы использовали при запуске 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, а не с компилятором.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Изменить: 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

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

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

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

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

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

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

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

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

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

You need to run it multiple times to get a real idea of "how fast" each runs. The JVM startup time [for one] is adding to the single running time of the Java version.

You're also creating a HashSet with a large initial capacity, which means the backing HashMap will be created with that many available slots, unlike the Python where you create a basic Set. Hard to tell if that would hinder though, as when your HashSet grows it will have to reallocate the stored objects.

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

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

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

Java

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

Python

#!/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"?

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

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

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

Реальный вопрос заключается в том, действительно ли ваш примерный код настолько репрезентативен для кода вашего приложения, как вы думаете. Вы запустили профилировщик и определили, что большая часть времени ЦП тратится на размещение огромного количества int в HashSet? В противном случае пример неуместен. Даже если единственная разница в том, что ваш производственный код хранит другие объекты, кроме целых,

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

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

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

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

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

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

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

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

A few changes for faster 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)

Before

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

After

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

Now some good old cheating and ...

#!/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

Что ж, если вы собираетесь настроить программу Java, вы можете также настроить программу Python.

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

Простое использование xrange делает ее примерно на 8% быстрее на моей машине. А выражение set (xrange (10000000)) строит точно такой же набор, но в 2,5 раза быстрее (с 1,87 секунды до 0,74).

Мне нравится, как настраивать программу Python делает его короче. :) Но Java может сделать то же самое. Как всем известно, если вам нужен плотный набор небольших целых чисел в Java, вы не используете хеш-таблицу. Вы используете 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());

Это должно быть довольно быстро.