Какой из этих кусков кода быстрее в Java? - PullRequest
11 голосов
/ 01 ноября 2009

а) for(int i = 100000; i > 0; i--) {}

б) for(int i = 1; i < 100001; i++) {}

Ответ есть на этом сайте (вопрос 3). Я просто не могу понять почему? С сайта:

Ответы [ 16 ]

68 голосов
/ 01 ноября 2009

Когда вы опускаетесь до самого низкого уровня (машинный код, но я буду использовать ассемблер, поскольку он в основном отображает один-к-одному), разница между пустым циклом, уменьшающимся до 0, и одним, увеличивающимся до 50 (например), равна часто в соответствии с:

      ld  a,50                ld  a,0
loop: dec a             loop: inc a
      jnz loop                cmp a,50
                              jnz loop

Это потому, что флаг нуля в большинстве здравомыслящих процессоров устанавливается инструкцией уменьшения при достижении нуля. То же самое обычно нельзя сказать о инструкции приращения, когда она достигает 50 (поскольку в этом значении нет ничего особенного, в отличие от нуля). Таким образом, вам нужно сравнить регистр с 50, чтобы установить нулевой флаг.


Однако, спрашивая, какой из двух циклов:

for(int i = 100000; i > 0; i--) {}
for(int i = 1; i < 100001; i++) {}

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

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

Например, если вам нужно для подсчета от 1 до 100 000, вы должны использовать второй цикл. Это потому, что преимущество обратного отсчета (если оно есть), вероятно, будет сведено на нет тем фактом, что вы должны оценивать 100000-i внутри цикла каждый раз, когда вам нужно его использовать. С точки зрения сборки, это будет разница между:

     ld  b,100000             dsw a
     sub b,a
     dsw b

(dsw - это, конечно, печально известный do something with мнемоник ассемблера).

Поскольку вы будете получать попадание для увеличивающегося цикла только один раз за итерацию, и вы будете принимать попадание для вычитания как минимум один раз за итерацию (при условии, что вы будете использовать i, в противном случае цикл вообще не нужен), вам просто нужно перейти на более естественную версию.

Если вам нужно подсчитать, подсчитайте. Если вам нужно вести обратный отсчет, начните обратный отсчет.

23 голосов
/ 01 ноября 2009

На многих компиляторах машинные инструкции, генерируемые для цикла, идущего в обратном направлении, более эффективны, потому что проверка на ноль (и, следовательно, обнуление регистра) быстрее, чем немедленная загрузка постоянного значения.

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

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

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

17 голосов
/ 01 ноября 2009

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

Позвольте компилятору сделать то, для чего он нужен, и сделайте ваше намерение понятным (как для компилятора, так и для читателя). Другая распространенная пессимизация Java:

public final static String BLAH = new StringBuilder().append("This is ").append(3).append(' text").toString();

потому что чрезмерная конкатенация приводит к фрагментации памяти, но для константы компилятор может (и будет) оптимизировать это:

public final static String BLAH = "This is a " + 3 + " test";

, где первое не оптимизируется, а второе легче читать.

А как насчет (a>b)?a:b против Math.max(a,b)? Я знаю, что предпочел бы прочесть второе, поэтому мне все равно, что первое не повлечет за собой вызов функции.

В этом списке есть несколько полезных вещей, таких как знание, что блок finally не вызывается на System.exit(), потенциально полезный. Знание того, что деление числа с плавающей точкой на 0,0 не вызывает исключения, полезно.

Но не стоит угадывать компилятор, если только он действительно имеет значение (и держу пари, что в 99,99% случаев это не так).

13 голосов
/ 01 ноября 2009

лучше вопрос;

С чем легче разобраться / работать?

Это гораздо важнее, чем условная разница в производительности. Лично я хотел бы отметить, что производительность не должна быть критерием для определения различий здесь. Если бы им не нравилось, что я оспариваю их предположения по этому поводу, я не был бы недоволен тем, что не получил работу. ;)

10 голосов
/ 01 ноября 2009

В современной реализации Java это не так. Суммируя цифры до одного миллиарда в качестве ориентира:

Java(TM) SE Runtime Environment 1.6.0_05-b13
Java HotSpot(TM) Server VM 10.0-b19
up 1000000000: 1817ms 1.817ns/iteration (sum 499999999500000000)
up 1000000000: 1786ms 1.786ns/iteration (sum 499999999500000000)
up 1000000000: 1778ms 1.778ns/iteration (sum 499999999500000000)
up 1000000000: 1769ms 1.769ns/iteration (sum 499999999500000000)
up 1000000000: 1769ms 1.769ns/iteration (sum 499999999500000000)
up 1000000000: 1766ms 1.766ns/iteration (sum 499999999500000000)
up 1000000000: 1776ms 1.776ns/iteration (sum 499999999500000000)
up 1000000000: 1768ms 1.768ns/iteration (sum 499999999500000000)
up 1000000000: 1771ms 1.771ns/iteration (sum 499999999500000000)
up 1000000000: 1768ms 1.768ns/iteration (sum 499999999500000000)
down 1000000000: 1847ms 1.847ns/iteration (sum 499999999500000000)
down 1000000000: 1842ms 1.842ns/iteration (sum 499999999500000000)
down 1000000000: 1838ms 1.838ns/iteration (sum 499999999500000000)
down 1000000000: 1832ms 1.832ns/iteration (sum 499999999500000000)
down 1000000000: 1842ms 1.842ns/iteration (sum 499999999500000000)
down 1000000000: 1838ms 1.838ns/iteration (sum 499999999500000000)
down 1000000000: 1838ms 1.838ns/iteration (sum 499999999500000000)
down 1000000000: 1847ms 1.847ns/iteration (sum 499999999500000000)
down 1000000000: 1839ms 1.839ns/iteration (sum 499999999500000000)
down 1000000000: 1838ms 1.838ns/iteration (sum 499999999500000000)

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

Edit: Контрольные циклы

        long sum = 0;
        for (int i = 0; i < limit; i++)
        {
            sum += i;
        }

и

        long sum = 0;
        for (int i = limit - 1; i >= 0; i--)
        {
            sum += i;
        }

Использование суммы типа int примерно в три раза быстрее, но затем сумма переполняется. С BigInteger это более чем в 50 раз медленнее:

BigInteger up 1000000000: 105943ms 105.943ns/iteration (sum 499999999500000000)
6 голосов
/ 06 января 2010

Есть только два способа ответить на этот вопрос.

  1. Чтобы сказать вам, что это действительно, действительно не имеет значения, и вы тратите свое время, даже задаваясь вопросом.

  2. Чтобы сообщить вам, что единственный способ узнать это - запустить надежный эталонный тест на вашем реальном оборудовании, операционной системе и JRE, которые вас интересуют.

Итак, я сделал вам работоспособный тест, который вы можете использовать, чтобы попробовать это здесь:

http://code.google.com/p/caliper/source/browse/trunk/test/examples/LoopingBackwardsBenchmark.java

Эта платформа Caliper пока еще не готова к прайм-тайму, поэтому, возможно, не совсем очевидно, что с этим делать, но если вам действительно все равно, вы можете понять это. Вот результаты, которые он дал на моей Linux-коробке:

     max benchmark        ns
       2  Forwards         4
       2 Backwards         3
      20  Forwards         9
      20 Backwards        20
    2000  Forwards      1007
    2000 Backwards      1011
20000000  Forwards   9757363
20000000 Backwards  10303707

Выглядит ли зацикливание назад как победа?

6 голосов
/ 01 ноября 2009

Обычно реальный код будет работать быстрее, считая вверх. Для этого есть несколько причин:

  • Процессоры оптимизированы для чтения памяти вперед.
  • HotSpot (и, вероятно, другие байт-коды-> нативные компиляторы) сильно оптимизируют прямые циклы, но не обращайте внимания на обратные циклы, потому что они происходят так редко.
  • Вверх обычно более очевиден, а более чистый код часто быстрее.

Так что счастливо делать правильные вещи обычно будет быстрее. Ненужная микрооптимизация - это зло. Я целенаправленно не писал обратной петли с момента программирования на ассемблере 6502.

3 голосов
/ 01 ноября 2009

Такие вопросы основаны на старых рекомендациях передовой практики. Все дело в сравнении: известно, что сравнение с 0 быстрее. Несколько лет назад это могло показаться очень важным. В настоящее время, особенно с Java, я бы предпочел, чтобы компилятор и виртуальная машина выполняли свою работу, и я бы сосредоточился на написании кода, который легко поддерживать и понимать.

Если нет причин делать это иначе. Помните, что Java-приложения не всегда работают на HotSpot и / или быстром оборудовании.

3 голосов
/ 01 ноября 2009

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

В общем, невозможно сказать, какой из них быстрее, потому что он сильно зависит от компилятора Java, JRE, CPU и других факторов. Использование одного или другого в вашей программе только потому, что вы думаете, что один из двух быстрее, без понимания деталей до самого низкого уровня, это суеверное программирование . И даже если одна версия быстрее, чем другая, в вашей конкретной среде, разница, скорее всего, настолько мала, что не имеет значения.

Пишите чистый код вместо того, чтобы пытаться быть умным.

2 голосов
/ 18 января 2011

Я решил откусить нить назад.

оба цикла игнорируются JVM как no-ops. по сути, даже один из циклов был до 10, а другой до 10000000, разницы не было бы.

Возвращение к нулю - это еще одна вещь (для инструкции jne, но опять-таки, она не скомпилирована так), связанный сайт выглядит странно (и неправильно).

Этот тип вопроса не подходит ни для какой JVM (ни для любого другого компилятора, который может оптимизировать).

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...