Какой из этих фрагментов кода работает быстрее на Java?
a) for(int i = 100000; i > 0; i--) {}
b) for(int i = 1; i < 100001; i++) {}
Ответ на этот сайт (вопрос 3). Я просто не могу понять почему? От веб-сайта:
3. a
Ответы
Ответ 1
Когда вы переходите на самый низкий уровень (машинный код, но я буду использовать сборку, поскольку он отображает один-к-одному в основном), разница между пустым циклом, уменьшающимся до 0 и одним приращением до 50 (например), является часто по строкам:
ld a,50 ld a,0
loop: dec a loop: inc a
jnz loop cmp a,50
jnz loop
Это потому, что флаг нуля в большинстве правильных CPU устанавливается командой декремента, когда вы достигаете нуля. То же самое обычно не указывается для инструкции приращения, когда она достигает 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, иначе мало потребность в цикле вообще), вы должны просто пойти с более естественной версией.
Если вам нужно подсчитать, подсчитайте. Если вам нужно отсчет, обратный отсчет.
Ответ 2
Во многих компиляторах машинные инструкции, испускаемые для цикла, идущего назад, более эффективны, потому что тестирование на нуль (и, следовательно, нулевое значение регистра) происходит быстрее, чем нагрузка с постоянным значением.
С другой стороны, хороший оптимизирующий компилятор должен иметь возможность проверять внутренний цикл и определять, что движение назад не вызовет каких-либо побочных эффектов...
Кстати, это ужасный вопрос интервью, на мой взгляд. Если вы не говорите о цикле, который работает 10 миллионов раз И вы убедились, что небольшое усиление не перевешивается многими примерами воссоздания значения прямого цикла (n - i), любое увеличение производительности будет минимальным.
Как всегда, не следует оптимизировать без оптимизации производительности и за счет более сложного понимания кода.
Ответ 3
Эти вопросы в основном не имеют никакого отношения к тому, что некоторые люди одержимы этим. Назовите это культом микро-оптимизации или любым другим, что вам нравится, но быстрее ли оно перебираться вверх или вниз? Шутки в сторону? Вы используете то, что подходит для того, что вы делаете. Вы не пишете свой код, сохраняя два тактовых цикла или что бы это ни было.
Пусть компилятор выполнит все действия и сделает вам цель очистить (как компилятору, так и читателю). Еще одна общая пессимизация 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 vs Math.max(a,b)? Я знаю, что лучше прочитать второй, так что мне все равно, что первый не несет накладных функций.
В этом списке есть несколько полезных вещей, например, знание того, что блок finally не вызывается на System.exit(), потенциально полезен. Знание того, что разделение float на 0.0 не вызывает исключение, полезно.
Но не стоит сомневаться в том, что компилятор предпочтет, если это не будет на самом деле (и я уверен, вы, что 99,99% времени, когда это не так).
Ответ 4
Лучший вопрос:
Что легче понять/работать с?
Это гораздо важнее условной разницы в производительности. Лично я бы отметил, что производительность не должна быть критерием для определения разницы здесь. Если бы они не хотели, чтобы я оспаривал их предположение об этом, я бы не был недоволен тем, что не получил работу.;)
Ответ 5
В современной реализации 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
Обычно реальный код будет работать быстрее, подсчитывая вверх. Для этого есть несколько причин:
- Процессоры оптимизированы для чтения памяти вперед.
- HotSpot (и, предположительно, другие байт-коды- > исходные компиляторы) сильно оптимизируют контуры прямых, но не мешают обратным циклам, потому что они происходят так редко.
- Наверху обычно более очевидно, и более чистый код часто быстрее.
Так что счастливо делать правильные вещи обычно будет быстрее. Ненужная микро-оптимизация - это зло. Я не целенаправленно писал обратные циклы с момента сборки ассемблера 6502.
Ответ 7
На этот вопрос действительно есть только два способа.
-
Чтобы сказать вам, что это действительно, на самом деле не имеет значения, и вы тратите свое время даже на размышления.
-
Чтобы сказать вам, что единственный способ знать - запустить надежный тест на вашем фактическом производственном оборудовании, установке ОС и JRE, о которой вы заботитесь.
Итак, я сделал вам простой пример, который вы можете использовать, чтобы попробовать это здесь:
http://code.google.com/p/caliper/source/browse/trunk/test/examples/LoopingBackwardsBenchmark.java
Эта платформа Caliper на самом деле не готова к прайм-тайм, так что может быть не совсем очевидно, что с этим делать, но если вы действительно заботитесь, вы можете понять это. Вот результаты, которые он дал в моем linux box:
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
Завершается ли обратная связь в обратном порядке, чтобы выиграть кого-нибудь?
Ответ 8
Вы уверены, что интервьюер, который задает такой вопрос, ожидает прямой ответ ( "номер один быстрее" или "номер два быстрее" ), или если этот вопрос предлагается спровоцировать обсуждение, как это происходит в ответы люди дают здесь?
В общем, невозможно сказать, какой из них быстрее, потому что он сильно зависит от компилятора Java, JRE, CPU и других факторов. Используя ту или иную в своей программе только потому, что вы считаете, что один из двух быстрее, не понимая детали на самом низком уровне, суеверное программирование, И даже если одна версия быстрее другой в вашей конкретной среде, то разница, скорее всего, настолько мала, что она не имеет значения.
Напишите чистый код вместо того, чтобы пытаться быть умным.
Ответ 9
Такие вопросы основываются на старых рекомендациях по лучшей практике.
Все о сравнении: по сравнению с 0, как известно, быстрее. Много лет назад это, возможно, считалось весьма важным. В настоящее время, особенно с Java, я бы предпочел, чтобы компилятор и виртуальная машина выполняли свою работу, и я бы сосредоточился на написании кода, который облегчает поддержку и понимание.
Если нет причин для этого в противном случае. Помните, что Java-приложения не всегда работают на HotSpot и/или быстро аппаратном обеспечении.
Ответ 10
Что касается тестирования на ноль в JVM: по-видимому, это можно сделать с помощью ifeq, тогда как для тестирования чего-либо еще требуется if_icmpeq, который также включает добавление дополнительного значения в стек.
Тестирование для > 0, как и в вопросе, может быть выполнено с помощью ifgt, тогда как тестирование для < 100001 if_icmplt.
Ответ 11
Это о самом тупом вопросе, который я когда-либо видел. Тело цикла пусто. Если компилятор хорош, он просто не испустит никакого кода. Он ничего не делает, не может генерировать исключение и не изменять ничего вне его сферы действия.
Предполагая, что ваш компилятор не настолько умный или у вас на самом деле нет пустого тела цикла:
Аргумент "счетчик обратного цикла" имеет смысл для некоторых языков ассемблера (это может иметь смысл и для байтового кода java, я не знаю его конкретно). Однако у компилятора очень часто есть возможность преобразовать ваш цикл, чтобы использовать декрементирующие счетчики. Если у вас нет тела цикла, в котором значение я явно используется, компилятор может сделать это преобразование. Поэтому снова вы не видите разницы.
Ответ 12
Я решил укусить и окутать назад нитку.
оба цикла игнорируются JVM как no-ops. так что по существу даже одна из петель была до 10, а другая до 10000000, не было никакой разницы.
Возвращение к нулю - это еще одна вещь (для команды jne, но опять же, она не скомпилирована), связанный сайт выглядит странно (и неправильно).
Этот тип вопроса не подходит ни одному JVM (никому другому компилятору, который может оптимизировать).
Ответ 13
Петли идентичны, за исключением одной важной части:
i > 0;
а также
i < 100001;
Проверка больше нуля выполняется путем проверки бит NZP (обычно известный как код условия или отрицательный нуль или положительный бит) компьютера.
Бит NZP устанавливается всякий раз, когда выполняется операция, такая как load, AND, дополнительный ect. выполняются.
Больше, чем проверка, не может напрямую использовать этот бит (и поэтому занимает немного больше времени). Общее решение состоит в том, чтобы сделать одно из значений отрицательным (сделав побитовое NOT, а затем добавив 1), а затем добавив его к сравниваемое значение. Если результат равен нулю, то они равны. Положительно, тогда второе значение (а не отрицательное) больше. Отрицательно, тогда первое значение (neg) больше. Эта проверка занимает немного больше, чем прямая проверка nzp.
Я не уверен на 100%, что это причина этого, но, похоже, это возможная причина...
Ответ 14
Ответ (как вы, вероятно, узнали на веб-сайте)
Я думаю, причина в том, что условие i > 0 для завершения цикла быстрее проверяется.
Ответ 15
Суть в том, что для любого критически важного приложения, не относящегося к производительности, разница, вероятно, не имеет значения. Как отмечали другие, времена, когда использование ++ я вместо я ++ может быть быстрее, однако, особенно для циклов, любой современный компилятор должен оптимизировать это различие.
Тем не менее, разница, вероятно, связана с базовыми инструкциями, которые генерируются для сравнения. Тестирование, если значение равно 0, - это просто логический элемент NAND NOR. В то время как тестирование, если значение равно произвольной константе, требует загрузки этой константы в регистр, а затем сравнения двух регистров. (Это, вероятно, потребует дополнительной задержки затвора или двух). Тем не менее, с конвейерной обработкой и современными ALU я был бы удивлен, если бы различие было значительным для начала.
Ответ 16
Я делаю тесты уже около 15 минут, и на всякий случай ничего не работает, кроме eclipse, и я видел реальную разницу, вы можете попробовать.
Когда я попытался определить, как долго java берет "ничего" , и потребовалось около 500 наносекунд, чтобы иметь представление.
Затем я проверил, сколько времени требуется для запуска инструкции for, где она увеличивается:
for(i=0;i<100;i++){}
Затем пять минут спустя я попробовал "назад":
for(i=100;i>0;i--)
И у меня есть огромная разница (на жестком крошечном уровне) 16% между первым и вторым операторами for, последние на 16% быстрее.
Среднее время запуска выражения "увеличение" for в течение 2000 тестов: 1838 н/с
Среднее время для запуска "уменьшения" for в течение 2000 тестов: 1555 н/с
Код, используемый для таких тестов:
public static void main(String[] args) {
long time = 0;
for(int j=0; j<100; j++){
long startTime = System.nanoTime();
int i;
/*for(i=0;i<100;i++){
}*/
for(i=100;i>0;i--){
}
long endTime = System.nanoTime();
time += ((endTime-startTime));
}
time = time/100;
System.out.print("Time: "+time);
}
Вывод:
Разница в принципе ничто, она уже занимает значительное количество "ничего" , чтобы делать "ничего" по отношению к тестам утверждения for, делая разницу между ними незначительной, просто время, затраченное на импорт библиотеки, такой как java. util.Scanner получает больше загрузок, чем работает оператор for, он не будет значительно улучшать производительность вашего приложения, но он все равно очень классно знать.
