Эффективность вложенного цикла
Посмотрите следующий отрывок:
Long first_begin = System.currentTimeMillis();
// first nested loops
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 1000000; j++) {
// do some stuff
}
}
System.out.println(System.currentTimeMillis() - first_begin);
// second nested loops
Long seconde_begin = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) {
for (int j = 0; j < 10; j++) {
// do some stuff
}
}
System.out.println(System.currentTimeMillis() - seconde_begin);
Я задаюсь вопросом, почему первые вложенные циклы работают медленнее, чем второй?
С уважением!
Важное Примечание!: Я сожалею, что сделал переменную j началом 1 случайно, когда этот вопрос сначала задают, я сделал исправление.
Update:there не является никакой определенной логикой в циклах, я просто делаю некоторый тест, на самом деле это - вопрос, который задают во время интервью, и интервьюер подсказывают меня для изменения порядка циклов достигнуть лучшей производительности. BTW, я использую JDK1.5. после некоторого теста я более смущен теперь, потому что результатом программы не является последовательный---когда-то первый цикл, работающий быстрее, чем второй, но большую часть времени это работает медленнее, чем второе.
4 ответа
Этот ответ относится к обновленному вопросу:
- Если вы обращаетесь к двумерному массиву, например
int [] [], то массив с большим значением во внутреннем цикле должен работать медленнее. Не сильно, но все же. Чтобы в некоторой степени понять проблему, прочтите о Шлемиэле, уличном художнике в одном из сообщений блога Джоэла. - Причина, по которой вы получаете противоречивые результаты, заключается в том, что вы не выполняете никакой разминки JVM. JVM постоянно анализирует выполняемый байт-код и оптимизирует его, обычно только после 30–50 итераций он запускается с оптимальной скоростью. Да, это означает, что вам нужно запустить код сначала пару десятков раз, а затем протестировать его в среднем еще пару десятков запусков из-за сборщика мусора, который замедлит пару запусков.
- Общее замечание: использование объекта
Longвместо примитиваlongпросто глупо, JVM, скорее всего, оптимизирует его, заменяя его примитивным, если может, а если нет. , обязательно будет некоторое ( хотя и крайне незначительное ) постоянное замедление от его использования.
Если вы посмотрите на сгенерированный байтовый код, два цикла почти идентичны.ЗА ИСКЛЮЧЕНИЕМ того, что когда она выполняет условие while для цикла 10, Java получает 10 как непосредственное значение из инструкции, но когда она выполняет условие while для цикла 1000000, Java загружает 1000000 из переменной. У меня нет информации о том, сколько времени требуется для выполнения каждой инструкции, но похоже, что немедленная загрузка будет быстрее, чем загрузка из переменной.
Обратите внимание, что в первом цикле сравнение с 1000000 должно выполняться 10 миллионов раз, а во втором цикле - только 1 миллион раз. Конечно, сравнение с 10 выполняется намного чаще во втором цикле, но если загрузка переменной происходит намного медленнее, чем немедленная загрузка, это объясняет наблюдаемые вами результаты.
Вопрос сдвинулся. Это не те дроиды, которых вы ищете...
Потому что в первом примере вы делаете в ~1000000 раз больше работы. ;-)
ПРАВКА: Оригинальный ответ приведен ниже. Теперь, когда вы исправили пример так, что все переменные цикла начинаются с 0, мы вернулись к тому, что просто не хватает информации. Кажется вероятным, что это проблема когерентности кэша / локальности ссылки - но мы просто догадываемся. Если бы вы могли предоставить короткую, но полную программу, которая демонстрирует проблему, это помогло бы... как если бы мы сказали нам, с какого языка / платформы мы говорим начать!
Первый цикл имеет 10 * 999999 = 9999990 итераций. Второй цикл имеет 1000000 * 9 = 9000000 итераций. Поэтому я бы ожидал, (при прочих равных условиях) что первый цикл займет больше времени.
Тем не менее, вы не указали, какую работу вы выполняете или на какой платформе это находится. Есть много вещей, которые могут повлиять на вещи:
- Второй цикл может лучше попасть в кэш
- Если вы используете JIT-скомпилированную платформу, JIT, возможно, решил оптимизировать второй цикл более сильно.
- Операции, которые вы выполняете, могут сами по себе иметь кэширование или что-то в этом роде
- Если вы выполняете небольшой объем работы, но сначала нужно загрузить и инициализировать кучу типов, что может привести к тому, что первый цикл будет медленнее