Поэтому замеры с помощью утилит, типа nanoTime, дают вроде бы согласованное время, но оно не учитывает времени, на которое были остановки виртуальной машины.
Выделенное жирным в ваших словах я не понял. Вы имели в виду, что временная дельта, полученное по разности двух вызовов
System .nanoTime (), включает в себя только время затрачиваемое виртуальной машиной, но не время, тратящееся процессором на выполнение других задач (в том числе системных процессов)? Это утверждение не верно. Или же вы понимаете, что это просто разность двух моментов времени, между которыми процессор выполнял как JVM, так и другие задачи, и недовольны этим фактом?
Поэтому при повышенной загрузке компьютера у вас будут совсем другие цифры задержек, т.к. системная часть времени обслуживания увеличивается.
Тут проблема гораздо глубже, чем вы себе представляете. Если система слишком загружена, и процесс с тестируемым на быстродействие алгоритмом часто прерывается для выполнения каких-либо других процессов (не важно, системных или же пользовательских), то тестируемый алгоритм получает задержки не только в связи временем выполнения прерывающих процессов, но так же задержки, связанные с необходимостью заново подгружать кэш памяти, используемой алгоритмом, так как эти области памяти будут вытеснены из кэша другими процессами. Поэтому подобная ситуация напрочь сломает все попытки оптимизировать использование алгоритмом кэша процессора.
Логично, что тестирование быстродействия надо производить на системе без других активных программ и с минимумом фоновых служб. Логично так же, использовать как минимум двухядерный процессор: одно ядро для системый нужд, другое — для исследуемого алгоритма, но процессор с как минимум двумя ядрами давно стал дэфолтным вариантом в ПК.
Разумеется, надо набирать временную статистику по-больше и критически отсеивать как завышенные времена работы, так и заниженные. Последнее, например, может случиться, если алгоритм выделяет и освобождает память, но на каком-то тестовом проходе свободной памяти JVM хватило, чтобы ни разу не вызывать сборщик мусора. Выделение/освобождение памяти в
Java и работа сборщика мусора является частью алгоритма, хоть последнее и не присутствует явно в коде программы, поэтому это время мы просто обязаны учитывать при оценке временной сложности конкретного алгоритма.
Если вы внимательно присмотритесь к моей функции
calculateStats ( ... ), то заметите, что там используется весьма изощрённый подход к расчёту среднего времени работы. Мне давно стоило его пояснить. Сначала функция сортирует собранную статистику в порядке возрастания. Это нужно для удобства отсеивания слишком малых и слишком больших времён работы, которые окажутся, соответственно, в начале и в конце массива с экспериментальными данными. Затем процедура берёт центральную ячейку массива, которая теперь содержит медиану набранной статистики и вычисляет границы отрезка с центром в этой медиане, на котором будет производится вычисление среднего и стандартного отклонения. Для левой (меньшей) границы берётся третье по счёту значение в отсортированном массиве, для правой — величина, не превышающая зеркально симметричное значение левой границы относительно центра. Надо заметить, что после проделанных "обрезаний" медиана является центром искомого отрезка по
величине, но не по
количеству экспериментальных величин: превышающих медиану величин как правило будет меньше, чем величин, меньших медианы. Этот подход ломается, если заниженных значений больше двух, но это случается очень редко (в простых алгоритмах без динамической работы с памятью — никогда); или если завышенных значений оказывается больше половины и сама медиана оказывается завышенной. В последнем случае надо задуматься над тем, чем же таким загружена система.
?
Слишком много разбираться, бросаю пока это дело.
