Эффективность алгоритма

Важность эффективности с упором на время исполнения подчёркивала Ада Лавлейс в 1843 по поводу механической аналитической машины Чарлза Бэббиджа:

«Почти во всех вычислениях возможен большой выбор конфигураций для успешного завершения процесса и различные соглашения должны влиять на выбор с целью выполнения вычислений. Существенная вещь — выбор конфигурации, которая приведёт к минимизации времени, необходимого для выполнения вычисления»[1].

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

Современные компьютеры намного быстрее тех ранних компьютеров и имеют много больше памяти (гигабайты вместо килобайт). Тем не менее, Дональд Кнут подчёркивает, что эффективность остаётся важным фактором:

«В установившихся технических дисциплинах улучшение на 12 % легко достижимо, никогда не считалось запредельным и я верю, что то же самое должно быть в программировании» [2]

Алгоритм считается эффективным, если потребляемый им ресурс (или стоимость ресурса) на уровне или ниже некоторого приемлемого уровня. Грубо говоря, «приемлемый» здесь означает «алгоритм будет работать умеренное время на доступном компьютере». Поскольку с 1950-х годов наблюдалось значительное увеличение вычислительной мощности и доступной памяти компьютеров, существующий «приемлемый уровень» не был приемлемым даже 10 лет назад.

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

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

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

Теоретический анализ

В теоретическом анализе алгоритмов обычной практикой является оценка сложности алгоритма в его асимптотическом поведении, то есть для отражения сложности алгоритма как функции от размера входа n используется нотация «O» большое. Эта оценка, в основном, достаточно точна при большом n, но может привести к неправильным выводам при малых значениях n (так, сортировка пузырьком, считающаяся медленной, может оказаться быстрее «быстрой сортировки», если нужно отсортировать лишь несколько элементов).

Некоторые примеры нотации «O» большое:

Обозначение	Название	Примеры
${\displaystyle O(1)\,}$	постоянное	Определение, чётно или нечётно число. Использование таблицы поиска постоянного размера. Использование подходящей хеш-функции для выбора элемента.
${\displaystyle O(\log n)\,}$	логарифмическое	Нахождение элемента в отсортированном массиве с помощью двоичного поиска или сбалансированного дерева, как и операции в биномиальной куче.
${\displaystyle O(n)\,}$	линейное	Поиск элемента в несортированном списке или несбалансированном дереве (худший случай). Сложение двух n-битных чисел с использованием сквозного переноса.
${\displaystyle O(n\log n)\,}$	квазилинейное, логарифмически линейное	Вычисление быстрого преобразования Фурье, пирамидальная сортировка, быстрая сортировка (лучший и средний случай), сортировка слиянием
${\displaystyle O(n^{2})\,}$	квадратное	Умножение двух n-значных чисел с помощью простого алгоритма, сортировка пузырьком (худший случай), сортировка Шелла, быстрая сортировка (худший случай), сортировка выбором, сортировка вставками
${\displaystyle O(c^{n}),\;c>1}$	экспоненциальное	Нахождение (точного) решения задачи коммивояжёра с помощью динамического программирования. Определение, не являются ли два логических утверждения эквивалентными с помощью полного перебора

Измерения обычно выражаются как функция от размера входа n.

Два наиболее важных измерения:

• Время: как долго алгоритм занимает процессор.
• Память: как много рабочей памяти (обычно RAM) нужно для алгоритма. Здесь есть два аспекта: количество памяти для кода и количество памяти для данных, с которыми код работает.

Для компьютеров, питающихся от батарей (например, лэптопов) или для очень длинных/больших вычислений (например, на суперкомпьютерах), представляют интерес измерения другого рода:

• Прямое потребление энергии: энергия, необходимая для работы компьютера.
• Косвенное потребление энергии: энергия, необходимая для охлаждения, освещения, и т. п.

В некоторых случаях нужны другие, менее распространённые измерения:

• Размер передачи: пропускная способность канала может оказаться ограничивающим фактором. Для уменьшения количества передаваемых данных можно использовать сжатие. Отображение рисунка или изображения (как, например, Google logo) может привести к передаче десятков тысяч байт (48K в данном случае). Сравните это с передачей шести байт в слове «Google».
• Внешняя память: память, необходимая на диске или другом устройстве внешней памяти. Эта память может использоваться для временного хранения или для будущего использования.
• Время отклика: параметр особенно важен для приложений, работающих в реальном времени, когда компьютер должен отвечать быстро на внешние события.
• Общая стоимость владения: параметр важен, когда предназначен для выполнения одного алгоритма.

• Быстрая сортировка, первый известный алгоритм со скоростью порядка ${\displaystyle O(n\log n)}$
• Пирамидальная сортировка, другой быстрый алгоритм сортировки
• Двоичный поиск для поиска в сортированной таблице
• Алгоритм Бойера — Мура для поиска строки внутри другой строки

• Дэвид Мэй , британский учёный в области информатики, профессор информатики Бристольского университета, основатель и главный инженер XMOS Semiconductor полагает, что одна из проблем заключается в существовании веры, что закон Мура решает вопрос неэффективности. Он предложил «альтернативный» закон Мура (Закон Вирта)[7]:

Программы становятся медленнее более стремительно, чем компьютеры становятся быстрее.

Мэй утверждает:

В широко распространённых системах уменьшение вдвое выполнение команд может удвоить жизнь батареи, а большие данные дают возможность для лучших алгоритмов: Уменьшение числа операций с N x N до N x log(N) имеет сильный эффект при больших N … Для N=30 миллиарда, эти изменения аналогичны 50 годам технологических улучшений.

• Программист Адам Н. Розербург в своём блоге «The failure of the Digital computer », описал текущее состояние программирования как близкое к «Software event horizon» (уровню программной катастрофы, намек на фантастический «shoe event horizon» (уровень обувной катастрофы), описанный Дугласом Адамсом в его книге «Hitchhiker’s Guide to the Galaxy» (Автостопом по галактике)[8]). Он оценил падение производительности на 70 dB, или на «99.99999 % от возможного», по сравнению с 1980-ми годами — «когда Артур Кларк сравнил вычислительные способности компьютеров 2001 с компьютером HAL в книге 2001: A Space Odyssey, он указал, что удивительно малы и мощны были компьютеры, но программы стали печально разочаровывающими».

Следующие соревнования приглашают принять участие в разработке лучших алгоритмов, критерий качества которых определяют судьи:

• Wired[9]

• Анализ алгоритмов
• Арифметическое кодирование — вид энтропийного кодирования с переменной длиной кода для эффективного сжатия данных
• Ассоциативный массив — структура данных, которую можно сделать более эффективной при применении деревьев PATRICIA или массивов Джуди
• Тест производительности — метод измерения сравнительного времени исполнения в определённых случаях
• Наилучший, наихудший и средний случай — соглашения по оценке времени выполнения по трём сценариям
• Двоичный поиск — простая и эффективная техника поиска в отсортированном списке
• Таблица ветвления — техника сокращения длины команд, размера машинного кода, и зачастую, памяти
• Оптимизирующий компилятор — компилятор, использующий различные методы получения более оптимального программного кода при сохранении функциональных возможностей
• Вычислительная сложность математических операций
• Вычислительная сложность — понятие в информатике, обозначающее зависимости объёма работы от размера входных данных
• Вычислительная мощность компьютера — количественная характеристика скорости выполнения операций на компьютере
• Сжатие данных — сокращение объёма передачи данных и занимаемого дискового пространства
• Индекс — данные, увеличивающие скорость выборки данных из таблиц
• Энтропийное кодирование — кодирование последовательности значений с возможностью однозначного восстановления с целью уменьшения объёма данных (длины последовательности) с помощью усреднения вероятностей появления элементов в закодированной последовательности
• Сборка мусора — автоматическое освобождение памяти после использования
• Зелёные информационные технологии — движение за внедрение «зелёных» технологий, потребляющих меньше ресурсов
• Код Хаффмана — алгоритм эффективного кодирования данных
• Improving Managed code Performance — Microsoft MSDN Library
• Локальность ссылок — во избежание задержек, вызванных кэшированием из-за нелокального доступа к памяти
• Оптимизация циклов
• Управление паматью
• Оптимизация (информатика)
• Анализ производительности — методы измерения фактической производительности алгоритма в реальном времени
• Вычисления в реальном времени — пример критичных по времени приложений
• Динамический анализ — оценка ожидаемого времени работы и расщепляемость алгоритма
• Одновременная многопоточность
• Упреждающее исполнение, когда вычисления проводятся, даже если ещё неизвестно, понадобятся ли их результаты, или немедленное вычисление как противоположность ленивым вычислениям
• Временна́я многопоточность
• Шитый код — один из способов реализации промежуточной виртуальной машины при интерпретации языков программирования (наряду с байт-кодом)
• Таблица виртуальных методов — механизм поддержки динамического соответствия (или метода позднего связывания)

• Christopher Green. Classics in the History of Psychology (неопр.) (2013). Дата обращения: 19 мая 2013.
• Knuth D. Structured Programming with go-to Statements // Computing Surveys. — ACM, 1974. — Т. 6, вып. 4. Архивировано 24 августа 2009 года.
• Whetstone Benchmark History (неопр.). Roylongbottom.org.uk. Дата обращения: 14 декабря 2011.
• Floating Point Benchmark: Comparing Languages (Fourmilog: None Dare Call It Reason) (неопр.). Fourmilab.ch (4 August 2005). Дата обращения: 14 декабря 2011.
• Guy Lewis Steele, Jr. Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO // MIT AI Lab. AI Lab Memo AIM-443.. — 1977. — Октябрь.

• Анимация алгоритма Boyer-Moore (Java-апплет)
• «How algorithms shape our world». Выступление Кельвина Славина на TED-конференции.
• Misconceptions about algorithmic efficiency in high-schools