Мера сложности времени методов класса JDK

Question

Существует ли установленный способ измерения (или получения существующей меры) сложности метода класса JDK? Является ли javap временной сложностью и в какой степени. В частности, меня интересует сложность Arrays.sort(), а также некоторые другие методы манипуляции с коллекциями.

E.g. Я пытаюсь сравнить две реализации для производительности, один использует Arrays.sort(), а другой нет. Разборка javap для этого не возвращает намного больше шагов (в два раза больше), но я не уверен, что тот, который делает, исключает шаги Arrays.sort(). IOW, javap одного метода включает рекурсивную меру методов, вызванных внутри или только для этого метода?

Кроме того, существует ли способ, без изменения и перекомпиляции самого Java-кода, чтобы найти, сколько циклов было выполнено, когда определенный базовый метод Java был вызван по определенным параметрам? Например. измерять количество итераций Arrays.sort('A', 'r', 'T', 'f')?

Answer 1

Я бы не ожидал, что javap будет даже немного отличаться от фактической скорости.

Javadoc определяет алгоритмическую сложность, но если вы заботитесь о постоянных факторах, то нет абсолютно никакого способа реалистично сравнивать постоянные факторы, кроме как с фактическим benchmarks.

Вы не можете получить любую информацию о том, что было сделано, когда Arrays.sort вызываются примитивным массив, но, передавая обычай Comparator, который подсчитывает количество вызовов, вы можете подсчитать количество сравнений при сортировке массива объектов , (Тем не менее, массивы объектов сортируются с использованием другого алгоритма сортировки, в частности стабильного, и примитивные массивы сортируются по варианту Quicksort.)

Answer 2

Вы можете использовать вывод из javap, чтобы определить, где происходят петли, которые вы хотите найти в инструкции goto. Это post дает исчерпывающее объяснение этой идентификации.

От поста:

Прежде чем рассматривать любые начало цикла/выход приборы, вы должны смотреть в определение того, что вход, выход и преемники. Хотя в цикле будет только одна точка входа, она может иметь несколько точек выхода и/или несколько преемников, как правило, вызванных перерывами (иногда с метками), операторами возврата и/или исключениями (явно пойманными или нет). Пока вы не указали детали относительно вида приборов, которые вы изучаете, это , конечно же, стоит подумать о том, где вы хотите вставить код (если это , что вы хотите сделать). Как правило, некоторые приборы могут быть сделаны перед каждым оператором выхода или вместо каждого заявления-преемника (в этом случае вам придется переместить исходный оператор).

Answer 3

Arrays.sort() для примитивов использует настроенную быстродействующую сортировку. Для Object использует mergesort (но это зависит от реализации).

От: Arrays

К примеру, алгоритм, используемый рода (Object []) не должны быть слиянием, но она должна быть стабильной