Мера временной сложности методов класса JDK
Существует ли установленный способ измерения (или получения существующего показателя) сложности метода класса JDK? Является javap представитель сложности времени и в какой степени. В частности меня интересует сложность Arrays.sort() но также некоторые другие методы манипуляции коллекциями.
Например, я пытаюсь сравнить две реализации по производительности, одна использует Arrays.sort() а один нет. javap Разборка для этого не возвращает намного больше шагов (вдвое больше), но я не уверен, что тот, который делает, исключает Arrays.sort() шаги. IOW, делает javap одного метода включить рекурсивную меру методов, вызванных внутри или только для этого метода?
Кроме того, есть ли способ, без изменения и перекомпиляции самого кода Java, найти, сколько итераций цикла было выполнено, когда определенный конкретный метод Java был вызван для определенных параметров? Например, измерить количество итераций Arrays.sort('A', 'r', 'T', 'f')?
3 ответа
Я бы не ожидал javap чтобы быть даже немного представителем фактической скорости.
Javadoc определяет алгоритмическую сложность, но если вы заботитесь о постоянных факторах, абсолютно невозможно реально сравнить постоянные факторы, кроме как с реальными тестами.
Вы не можете получить информацию о том, что было сделано, когда Arrays.sort вызывается в примитивном массиве, но путем передачи пользовательского Comparator что подсчитывает количество вызовов, вы можете посчитать количество сравнений, сделанных при сортировке массива объектов. (Тем не менее, объектные массивы сортируются с помощью другого алгоритма сортировки, в частности, стабильного, а примитивные массивы сортируются с помощью варианта быстрой сортировки.)
Вы можете использовать вывод из javap чтобы определить, где происходят петли, вы хотите найти goto инструкция. Этот пост дает исчерпывающее объяснение этой идентификации.
Из поста:
Прежде чем рассматривать любые инструменты запуска / выхода из цикла, вы должны посмотреть определения того, что такое вход, выход и преемники. Хотя цикл будет иметь только одну точку входа, он может иметь несколько точек выхода и / или нескольких преемников, как правило, вызванных операторами прерывания (иногда с метками), операторами возврата и / или исключениями (явно перехваченными или нет). Несмотря на то, что вы не предоставили подробных сведений о типе инструментария, который вы исследуете, безусловно, стоит подумать, куда вы хотите вставить код (если это то, что вы хотите сделать). Как правило, некоторые инструментарии, возможно, придется выполнять перед каждым оператором выхода или вместо каждого оператора-преемника (в этом случае вам придется переместить исходный оператор).
Arrays.sort() для примитивов используется настроенная быстрая сортировка. За Object использует сортировку слиянием (но это зависит от реализации).
От: Массивы
Например, алгоритм, используемый sort(Object[]), не обязательно должен быть сортировкой слиянием, но он должен быть стабильным