Определение числа для эффективности алгоритма

Во-первых, некоторые придирки. Вы называете этот вопрос ...

Присвоение числа эффективности алгоритма

• Для алгоритма не существует практической количественной меры "эффективности". Эффективность (как обычно понимается) - это мера "чего-то" по отношению к идеалу / совершенству; например, гипотетическая 100% эффективная паровая машина преобразует всю энергию в сжигаемом угле в полезную "работу". Но для программного обеспечения нет идеала, чтобы мера против. (А если и есть, то мы не можем быть уверены, что это идеал.) Следовательно, "эффективность" - неправильный термин.

  То, что вы на самом деле имеете в виду, является мерой "производительности"...
• Алгоритмы-это абстрактное понятие,и их производительность нельзя измерить. То, что вы на самом деле хотите, - это мера производительности конкретной реализации алгоритма, то есть некоторого фактического кода.

---

Итак, как вы оцениваете спектакль?

Что ж, в конечном счете есть только один надежный способ количественной оценки производительности. Вы измеряете его эмпирически. (Как вы это делаете ... и ограничения ... это вопрос, к которому я приду.) Но как насчет теоретических подходов? Общий теоретический подход заключается в анализе алгоритма, чтобы дать вам меру вычислительной сложности . Классическая мера-это большая сложность. Это очень полезная мера, но, к сожалению, большая сложность делает на самом деле не измеряют производительность вообще. Скорее, это способ характеризовать поведение алгоритма по мере увеличения размера задачи. Для иллюстрации рассмотрим следующие алгоритмы сложения чисел B:

    int sum(int[] input) {
        int sum = 0;
        for (int i = 0; i < input.size(); i++) {
            sum += input[i];
        }
        return i;
    }

    int sum(int[] input) {
        int tmp = p(1000);  // calculates the 1000th prime number
        int sum = 0;
        for (int i = 0; i < input.size(); i++) {
            sum += input[i];
        }
        return i;
    }

Мы можем доказать, что обе версии sum имеют сложность O(N), согласно принятым математическим определениям. Но очевидно, что первый будет быстрее второго ... потому что второй делает большой (и бессмысленный) расчет тоже.

Короче говоря: сложность Big-O не является мерой производительности.

Как насчет теоретических показателей эффективности?

Ну, насколько мне известно, ни один из них не работает по-настоящему. Проблема заключается в том, что реальная производительность (как и время, необходимое для завершения) зависит от различных сложных вещей при компиляции кода в исполняемые файлы и от того, как ведут себя реальные исполнительные платформы (аппаратные средства). Это слишком сложно сделать теоретически. анализ, который позволит надежно прогнозировать фактические показатели.

---

Так как же вы измеряете производительность?

Наивный ответ заключается в следующем:

• возьмите измерение часов
• запустите код
• возьмите второе измерение часов
• вычтите первое измерение из второго ... и это ваш ответ.

Но это не работает. или, точнее, ответ, который вы получите, может сильно отличаться от производительность, которую демонстрирует код, когда вы используете его в реальном контексте.

Почему?

• На машине могут происходить и другие вещи ... или уже случилось ... это влияет на время выполнения кода. Возможно, работает другая программа. Файлы могут быть предварительно загружены в кэш файловой системы. Вы можете получить удар по масштабированию часов процессора ... или всплеск сетевого трафика.

• Компиляторы и флаги компилятора часто могут создавать много разница в том, как быстро выполняется фрагмент кода.

• Выбор входных данных часто может иметь большое значение.

• Если компилятор умен, он может сделать вывод, что часть или весь ваш бенчмаркированный код не делает ничего "полезного" (в контексте) ... и оптимизируйте его полностью.

А для таких языков, как Java и C#, есть и другие важные вопросы:

• Реализации этих языков обычно делают много работы во время запуска, чтобы загрузите и свяжите код.

• Реализации этих языков, как правило, скомпилированы JIT. Это означает, что языковая среда выполнения выполняет окончательный перевод кода (например, байт-кодов) в машинный код во время выполнения. Характеристики производительности вашего кода после компиляции JIT резко меняются, и время, затраченное на компиляцию, может быть значительным ... и может исказить ваши измерения времени.

• Реализации этих языков обычно для управления памятью полагайтесь на собранную кучу мусора. Производительность кучи часто неравномерна, особенно при запуске.

Эти вещи (и, возможно, другие) способствуют тому, что мы называем (в Java) JVM warmup overheads; в частности, компиляция JIT. Если вы не учитываете эти накладные расходы в своей методологии, то ваши результаты могут быть искажены.

Итак, как правильно измерить производительность Java-кода?

Это сложно, но общий принцип заключается в том, чтобы запускать тестовый код много раз в одном и том же экземпляре JVM, измеряя каждую итерацию. Первые несколько измерений (во время прогрева СПМ) должны быть отброшены, а остальные измерения должны быть усреднены.

В наши дни, рекомендуемый способ сделать Java бенчмаркинг-это использовать авторитетный бенчмаркинг фреймворк. Двумя основными кандидатами являютсясуппорт и инструмент Oraclejmh .

И каковы ограничения производительности измерения, о которых вы упомянули?

Я уже упоминал о них выше.

• Измерения производительности могут быть искажены в зависимости от различных факторов окружающей среды на платформе исполнения.

• Производительность может зависеть от входных данных ... и это не может быть обнаружено простым измерением.

• Производительность (например, кода C / C++) может зависеть от компилятора и коммутаторов компилятора.

• Производительность может зависеть от оборудования; например, скорость процессоров, количество ядер, архитектура памяти и так далее.

Эти факторы могут затруднить составление общих утверждений о производительности конкретного фрагмента кода и проведение общих сравнений между альтернативными версиями одного и того же кода. Как правило, мы можем делать только ограниченные утверждения типа "в системе X, с компилятором Y и входным набором Z показатели производительности равны P, Q, R".

Вообще говоря, скорость по сравнению со строками кода не является наиболее эффективным показателем производительности, поскольку она сильно зависит от вашего оборудования и вашего компилятора. Существует так называемая большая Oh нотация, которая дает представление о том, как быстро алгоритм будет работать по мере увеличения числа входных данных.

Например, если скорость вашего алгоритма равна O (n), то время, которое потребуется для выполнения кода, будет линейным по времени. Если скорость вашего алгоритма равна O(1), то время, которое он займет ваш код для запуска будет постоянным.

Я нашел этот конкретный способ измерения производительности полезным, потому что вы узнаете, что на самом деле это не строки кода, которые будут влиять на скорость, это ваш дизайн кодов, который будет влиять на скорость. Код с более эффективным способом решения проблемы может быть быстрее, чем код с менее эффективным методом с 1/10 строками кода.