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

Не путать с оптимизацией, которая обсуждается в разделах «Оптимизация программ» , «Оптимизация компилятора» , «Оптимизация цикла» , «Оптимизатор объектного кода» и т. д.

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

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

Например, пузырьковая сортировка и временная сортировка — это алгоритмы сортировки списка элементов от меньшего к большему. Пузырьковая сортировка сортирует список за время, пропорциональное количеству элементов в квадрате ( ${\textstyle O(n^{2})}$, см. обозначение Big O ), но требует лишь небольшого объема дополнительной памяти , которая постоянна относительно длины списка ( ${\textstyle O(1)}$). Timsort сортирует список линейно по времени (пропорционально количеству, умноженному на его логарифм) по длине списка ( ${\textstyle O(n\log n)}$), но требует пространства, линейно зависящего от длины списка ( ${\textstyle O(n)}$). Если для данного приложения необходимо сортировать большие списки с высокой скоростью, лучшим выбором будет timsort; однако, если минимизация потребления памяти при сортировке более важна, лучшим выбором будет пузырьковая сортировка.

Предыстория

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

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

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

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

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

Обзор

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

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

Существует множество способов измерения ресурсов, используемых алгоритмом: двумя наиболее распространенными показателями являются скорость и использование памяти; другие меры могут включать скорость передачи, временное использование диска, долгосрочное использование диска, энергопотребление, общую стоимость владения , время реакции на внешние воздействия и т. д. Многие из этих показателей зависят от размера входных данных для алгоритма, т. е. объем данных, подлежащих обработке. Они также могут зависеть от способа организации данных; например, некоторые алгоритмы сортировки плохо работают с данными, которые уже отсортированы или отсортированы в обратном порядке.

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

анализ

При теоретическом анализе алгоритмов обычной практикой является оценка их сложности в асимптотическом смысле. Наиболее часто используемой нотацией для описания потребления ресурсов или «сложности» является Кнута Дональда нотация Big O , представляющая сложность алгоритма как функцию размера входных данных. ${\textstyle n}$. Обозначение Big O — это асимптотическая мера сложности функции, где ${\textstyle f(n)=O{\bigl (}g(n){\bigr )}}$ грубо означает, что время, необходимое для алгоритма, пропорционально $g(n)$, опуская члены низшего порядка , вклад которых меньше $g(n)$ к росту функции как ${\textstyle n}$ вырастает сколь угодно большим . Эта оценка может ввести в заблуждение, если ${\textstyle n}$ мала, но, как правило, достаточно точна, когда ${\textstyle n}$велико, поскольку обозначения асимптотические. Например, пузырьковая сортировка может быть быстрее сортировки слиянием , если необходимо отсортировать только несколько элементов; однако любая реализация, скорее всего, будет соответствовать требованиям к производительности для небольшого списка. Обычно программисты заинтересованы в алгоритмах, которые эффективно масштабируются для больших размеров входных данных, и сортировка слиянием предпочтительнее пузырьковой сортировки для списков длины, встречающихся в большинстве программ с интенсивным использованием данных.

Некоторые примеры нотации Big O, применяемой к асимптотической временной сложности алгоритмов, включают:

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

:

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

Некоторые тесты предоставляют возможности для проведения анализа, сравнивающего относительную скорость различных компилируемых и интерпретируемых языков, например и The Computer Language Benchmarks Game сравнивает производительность реализаций типичных задач программирования на нескольких языках программирования.

Даже создание тестов « сделай сам » может продемонстрировать относительную производительность различных языков программирования, используя множество критериев, заданных пользователем. Это довольно просто, как показывает на примере «Обзор производительности девяти языков» Кристофера Коуэлла-Шаха.

Проблемы

Проблемы реализации также могут влиять на эффективность, например, выбор языка программирования или способа фактического кодирования алгоритма. или выбор компилятора для определенного языка, или используемые параметры компиляции , или даже операционную систему используемую . Во многих случаях язык, реализованный интерпретатором, может быть намного медленнее, чем язык, реализованный компилятором. См. статьи о JIT-компиляции и интерпретируемых языках .

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

Некоторые процессоры имеют возможности векторной обработки , которые позволяют одной инструкции работать с несколькими операндами ; Программисту или компилятору может быть легко, а может и нелегко использовать эти возможности. Алгоритмы, разработанные для последовательной обработки, возможно, придется полностью перепроектировать для использования параллельной обработки , или их можно легко переконфигурировать. Поскольку в конце 2010-х годов важность параллельных и распределенных вычислений возрастает, все больше инвестиций делается в эффективные высокоуровневые API для параллельных и распределенных вычислительных систем, таких как CUDA , TensorFlow , Hadoop , OpenMP и MPI .

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

Меры использования ресурсов

Меры обычно выражаются как функция размера входных данных. $\scriptstyle {n}$.

Двумя наиболее распространенными мерами являются:

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

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

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

По состоянию на 2018 год Энергопотребление растет как важный показатель для вычислительных задач всех типов и всех масштабов — от встроенных Интернета вещей устройств до системных устройств и серверных ферм . Эту тенденцию часто называют « зелеными вычислениями» .

Менее распространенные меры вычислительной эффективности также могут быть актуальны в некоторых случаях:

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

Время

Теория

Проанализируйте алгоритм, обычно используя анализ временной сложности , чтобы получить оценку времени работы в зависимости от размера входных данных. Результат обычно выражается с использованием нотации Big O. Это полезно для сравнения алгоритмов, особенно когда необходимо обработать большой объем данных. Для сравнения производительности алгоритма при небольшом объеме данных необходимы более подробные оценки, хотя это, вероятно, будет иметь меньшее значение. Алгоритмы, включающие параллельную обработку, могут оказаться более трудными для анализа .

Практика

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

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

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

Космос

Этот раздел посвящен использованию ресурсов памяти ( регистров , кэша , ОЗУ , виртуальной памяти , вторичной памяти ) во время выполнения алгоритма. Что касается анализа времени, описанного выше, анализируйте алгоритм, обычно используя анализ пространственной сложности , чтобы получить оценку необходимой оперативной памяти в зависимости от размера входных данных. Результат обычно выражается с использованием нотации Big O.

Необходимо учитывать до четырех аспектов использования памяти:

• Объем памяти, необходимый для хранения кода алгоритма.
• Объем памяти, необходимый для входных данных .
• Объем памяти, необходимый для любых выходных данных .
  • Некоторые алгоритмы, такие как сортировка, часто переупорядочивают входные данные и не требуют дополнительного места для выходных данных. Это свойство называется операцией « на месте ».
• Объем памяти, необходимый в качестве рабочего пространства во время вычислений.
  • Сюда входят локальные переменные и любое пространство стека, необходимое для подпрограмм, вызываемых во время вычислений; это пространство стека может быть значительным для алгоритмов, использующих рекурсивные методы.

Ранние электронные компьютеры и первые домашние компьютеры имели относительно небольшой объем рабочей памяти. Например, автоматический калькулятор с электронным запоминанием задержки (EDSAC) 1949 года имел максимальную рабочую память в 1024 17-битных слов, а Sinclair ZX80 1980 года изначально имел 1024 8-битных байта рабочей памяти. характерно В конце 2010-х годов для персональных компьютеров иметь от 4 до 32 ГБ оперативной памяти, что более чем в 300 миллионов раз больше памяти.

Иерархия кэширования и памяти

Дополнительная информация: Иерархия памяти.

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

• Регистры процессора — самая быстрая из компьютерных технологий памяти с наименьшим объемом памяти. Большинство прямых вычислений на современных компьютерах происходит с операндами источника и назначения в регистрах перед их обновлением в кэше, основной памяти и виртуальной памяти, если это необходимо. В ядре процессора обычно имеется порядка сотен байт или меньше доступных регистров, хотя файл регистров может содержать больше физических регистров, чем архитектурных регистров, определенных в архитектуре набора команд.
• Кэш-память — вторая самая быстрая и вторая самая маленькая память, доступная в иерархии памяти. Кэши присутствуют в процессорах, графических процессорах, жестких дисках и внешних периферийных устройствах и обычно реализуются в статической оперативной памяти . Кэши памяти являются многоуровневыми ; более низкие уровни больше, медленнее и обычно распределяются между ядрами процессора в многоядерных процессорах . Чтобы обработать операнды в кэш-памяти, процессор должен извлечь данные из кэша, выполнить операцию в регистрах и записать данные обратно в кэш. ЦП или графического процессора Он работает на скоростях, сопоставимых (примерно в 2–10 раз медленнее) со скоростью арифметико-логического устройства или устройства с плавающей запятой, если он находится в кэше L1 . Это примерно в 10 раз медленнее, если произошел промах в кэше L1 и его необходимо извлечь и записать в кэш L2 , и еще в 10 раз медленнее, если произошел промах в кэше L2 и его необходимо извлечь из кэша L3 , если подарок.
• Основная физическая память чаще всего реализуется в виде динамического ОЗУ (DRAM). Основная память намного больше (обычно гигабайты по сравнению с ≈8 мегабайтами ), чем кэш ЦП L3, при этом задержки чтения и записи обычно в 10–100 раз медленнее. По состоянию на 2018 год ОЗУ все чаще реализуется на кристалле процессора в виде памяти ЦП или графического процессора .
• Виртуальная память чаще всего реализуется в виде вторичного хранилища , такого как жесткий диск , и представляет собой расширение иерархии памяти , которая имеет гораздо больший объем памяти, но гораздо большую задержку, обычно примерно в 1000 раз медленнее, чем промах в кэше для значения в ОЗУ. . Первоначально виртуальная память была призвана создать впечатление, что доступны большие объемы памяти, чем были доступны на самом деле, но в современном использовании виртуальная память более важна из-за ее компромисса во времени и пространстве и обеспечения возможности использования виртуальных машин . Промахи в кэше основной памяти называются страничными ошибками и приводят к огромным потерям производительности программ.

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

На заре электронных вычислений, если алгоритм и его данные не помещались в основную память, алгоритм нельзя было использовать. В настоящее время использование виртуальной памяти обеспечивает больший объем памяти, но за счет производительности. Если алгоритм и его данные поместятся в кэш-память, то можно получить очень высокую скорость; в этом случае минимизация пространства также поможет минимизировать время. Это называется принципом локальности , и его можно подразделить на локальность отсчета , пространственную локальность и временную локальность . Алгоритм, который не полностью помещается в кэш-память, но обеспечивает локальность ссылки, может работать достаточно хорошо.

См. также

• Анализ алгоритмов — как определить ресурсы, необходимые алгоритму.
• Бенчмарк — метод измерения сравнительного времени выполнения в определенных случаях.
• Лучший, худший и средний случай — соображения по оценке времени выполнения в трех сценариях.
• Оптимизация компилятора — оптимизация на основе компилятора.
• Теория сложности вычислений
• Производительность компьютера — показатели компьютерного оборудования.
• Оптимизация (информатика)
• Анализ производительности — методы измерения фактической производительности алгоритма во время выполнения.