Производительность алгоритма резко возрастает в ~10 раз.

Исходная информация

Недавно я сдал задание для своего класса по алгоритмам и структурам данных. Задача состояла в том, чтобы реализовать решение для нахождения максимального-подмассива случайно сгенерированных массивов. Нас попросили реализовать как алгоритм грубой силы, так и рекурсивный алгоритм «разделяй-и-властвуй».

Затем нас попросили проанализировать время выполнения, чтобы увидеть, при каком размере задачи алгоритм грубой силы будет быстрее, чем рекурсивное решение. Это было сделано путем измерения времени работы (с использованием System.nanoTime ()измерений )обоих алгоритмов для увеличения размеров задач.

Однако определение этого оказалось немного сложнее, чем я ожидал.

Любопытство

Если я начну с запуска обоих алгоритмов с размерами задач 5000 более 10 раз, время выполнения рекурсивного алгоритма упадет от одного запуска к другому примерно в 10 раз. (от ~1800 мкс для выполнения до ~200 мкс для выполнения), и это остается намного быстрее для остальных итераций. См. пример на рисунке ниже.

2-й и 3-й столбцы предназначены только для проверки того, что оба алгоритма возвращают правильный максимальный подмассив.

Это было протестировано на OS X 10.7.3 с Java 1.6.0_29 -результаты были такими же при выполнении на ПК под управлением Windows 7 и Java 1.6 (точный номер версии неизвестен).

Исходный код программы можно найти здесь.:https://gist.github.com/2274983

У меня такой вопрос.:Что заставляет алгоритм работать намного лучше после «прогрева»?