В информатике эффективность алгоритма — это свойство алгоритма , которое связано с количеством вычислительных ресурсов , используемых алгоритмом. Алгоритм необходимо проанализировать , чтобы определить использование им ресурсов, а эффективность алгоритма можно измерить на основе использования различных ресурсов. Алгоритмическую эффективность можно рассматривать как аналог производительности разработки для повторяющегося или непрерывного процесса.
Для максимальной эффективности желательно минимизировать использование ресурсов. Однако различные ресурсы, такие как временная и пространственная сложность, нельзя сравнивать напрямую, поэтому какой из двух алгоритмов считается более эффективным, часто зависит от того, какой показатель эффективности считается наиболее важным.
Например, пузырьковая сортировка и временная сортировка — это алгоритмы сортировки списка элементов от меньшего к большему. Пузырьковая сортировка сортирует список по времени, пропорциональному количеству элементов в квадрате ( см. обозначение Big O ), но требует лишь небольшого объема дополнительной памяти , которая постоянна по отношению к длине списка ( ). Timsort сортирует список линейно по времени (пропорционально количеству, умноженному на логарифм) по длине списка ( ), но требует пространства, линейно зависящего от длины списка ( ). Если для данного приложения необходимо сортировать большие списки с высокой скоростью, лучшим выбором будет timsort; однако, если минимизация потребления памяти при сортировке более важна, лучшим выбором будет пузырьковая сортировка.
Важность эффективности по отношению ко времени была подчеркнута Адой Лавлейс в 1843 году применительно к механической аналитической машине Чарльза Бэббиджа :
«Почти при каждом вычислении возможно большое разнообразие вариантов последовательности процессов, и на выбор среди них для целей вычислительной машины должны влиять различные соображения. минимум времени, необходимого для завершения расчета» [1]
Ранние электронные компьютеры имели ограниченную скорость и ограниченную оперативную память . Таким образом, произошел компромисс между пространством и временем . Задача может использовать быстрый алгоритм , использующий большой объем памяти, или медленный алгоритм, использующий мало памяти. Тогда инженерным компромиссом было использование самого быстрого алгоритма, который мог поместиться в доступную память.
Современные компьютеры значительно быстрее, чем ранние компьютеры, и имеют гораздо больший объем доступной памяти ( гигабайты вместо килобайтов ). Тем не менее, Дональд Кнут подчеркнул, что эффективность по-прежнему является важным фактором:
«В устоявшихся инженерных дисциплинах легко достижимое улучшение на 12% никогда не считается незначительным, и я считаю, что такая же точка зрения должна преобладать в разработке программного обеспечения» [2]
Алгоритм считается эффективным, если его потребление ресурсов, также известное как вычислительные затраты, находится на некотором приемлемом уровне или ниже. Грубо говоря, «приемлемый» означает: он будет работать в течение разумного периода времени или пространства на доступном компьютере, обычно в зависимости от размера входных данных. С 1950-х годов в компьютерах произошел резкий рост как доступной вычислительной мощности, так и доступного объема памяти, поэтому текущие приемлемые уровни были бы неприемлемы даже 10 лет назад. Фактически, благодаря приблизительному удвоению мощности компьютеров каждые 2 года , задачи, которые приемлемо эффективны на современных смартфонах и встроенных системах , могли быть неприемлемо неэффективны для промышленных серверов 10 лет назад.
Производители компьютеров часто выпускают новые модели, часто с более высокой производительностью . Затраты на программное обеспечение могут быть довольно высокими, поэтому в некоторых случаях самым простым и дешевым способом повышения производительности может быть просто покупка более быстрого компьютера, при условии, что он совместим с существующим компьютером.
Существует множество способов измерения ресурсов, используемых алгоритмом: двумя наиболее распространенными показателями являются скорость и использование памяти; другие меры могут включать скорость передачи, временное использование диска, долгосрочное использование диска, энергопотребление, общую стоимость владения , время реакции на внешние воздействия и т. д. Многие из этих показателей зависят от размера входных данных для алгоритма, т. е. объем данных, подлежащих обработке. Они также могут зависеть от способа организации данных; например, некоторые алгоритмы сортировки плохо работают с данными, которые уже отсортированы или отсортированы в обратном порядке.
На практике существуют и другие факторы, которые могут повлиять на эффективность алгоритма, например требования к точности и/или надежности. Как подробно описано ниже, способ реализации алгоритма также может оказать существенное влияние на фактическую эффективность, хотя многие аспекты этого связаны с проблемами оптимизации .
При теоретическом анализе алгоритмов обычной практикой является оценка их сложности в асимптотическом смысле. Наиболее часто используемая нотация для описания потребления ресурсов или «сложности» — это нотация Big O Дональда Кнута , представляющая сложность алгоритма как функцию размера входных данных . Обозначение Big O — это асимптотическая мера сложности функции, где примерно означает, что требуемое время для алгоритма пропорционально , исключая члены более низкого порядка , которые вносят меньший вклад в рост функции по мере того, как она становится сколь угодно большой . Эта оценка может вводить в заблуждение, когда она мала, но, как правило, достаточно точна, когда она велика, поскольку обозначения асимптотические. Например, пузырьковая сортировка может быть быстрее, чем сортировка слиянием , если необходимо отсортировать только несколько элементов; однако любая реализация, скорее всего, будет соответствовать требованиям к производительности для небольшого списка. Обычно программисты интересуются алгоритмами, которые эффективно масштабируются для больших размеров входных данных, и сортировка слиянием предпочтительнее пузырьковой сортировки для списков длины, встречающихся в большинстве программ с интенсивным использованием данных.
Некоторые примеры нотации Big O, применяемой к асимптотической временной сложности алгоритмов, включают:
Для новых версий программного обеспечения или для сравнения с конкурирующими системами иногда используются тесты , которые помогают оценить относительную производительность алгоритмов. Например, если создан новый алгоритм сортировки , его можно сравнить с его предшественниками, чтобы убедиться, что он, по крайней мере, по-прежнему эффективен с известными данными, принимая во внимание любые функциональные улучшения. Клиенты могут использовать эталонные тесты при сравнении различных продуктов от альтернативных поставщиков, чтобы оценить, какой продукт лучше всего соответствует их конкретным требованиям с точки зрения функциональности и производительности. Например, в мире мэйнфреймов некоторые проприетарные продукты сортировки от независимых компаний-разработчиков программного обеспечения, таких как Syncsort, конкурируют за скорость с продуктами таких крупных поставщиков, как IBM .
Некоторые тесты предоставляют возможности для проведения анализа, сравнивающего относительную скорость различных компилируемых и интерпретируемых языков, например [3] [4] и The Computer Language Benchmarks Game сравнивает производительность реализаций типичных задач программирования на нескольких языках программирования.
Даже создание тестов « сделай сам » может продемонстрировать относительную производительность различных языков программирования, используя множество критериев, заданных пользователем. Это довольно просто, как показывает на примере «Обзор производительности девяти языков» Кристофера Коуэлла-Шаха. [5]
Проблемы реализации также могут влиять на эффективность, например, выбор языка программирования или способа фактического кодирования алгоритма [6] , или выбор компилятора для определенного языка, или используемых параметров компиляции , или даже используемая операционная система . Во многих случаях язык, реализованный интерпретатором, может быть намного медленнее, чем язык, реализованный компилятором. [3] См. статьи о JIT-компиляции и интерпретируемых языках .
Существуют и другие факторы, которые могут влиять на проблемы времени или пространства, но могут находиться вне контроля программиста; к ним относятся выравнивание данных , гранулярность данных , локальность кэша , согласованность кэша , сбор мусора , параллелизм на уровне инструкций , многопоточность (на аппаратном или программном уровне), одновременная многозадачность и вызовы подпрограмм . [7]
Некоторые процессоры имеют возможности векторной обработки , которые позволяют одной инструкции работать с несколькими операндами ; Программисту или компилятору может быть легко, а может и нелегко использовать эти возможности. Алгоритмы, разработанные для последовательной обработки, возможно, придется полностью перепроектировать для использования параллельной обработки , или их можно легко переконфигурировать. Поскольку в конце 2010-х годов важность параллельных и распределенных вычислений возрастает, все больше инвестиций делается в эффективные высокоуровневые API для параллельных и распределенных вычислительных систем, таких как CUDA , TensorFlow , Hadoop , OpenMP и MPI .
Другая проблема, которая может возникнуть при программировании, заключается в том, что процессоры, совместимые с одним и тем же набором команд (например, x86-64 или ARM ), могут реализовывать инструкции по-разному, поэтому инструкции, которые относительно быстры на некоторых моделях, могут быть относительно медленными на других моделях. . Это часто создает проблемы для оптимизации компиляторов , которые должны обладать обширными знаниями о конкретном процессоре и другом оборудовании, доступном в цели компиляции, чтобы наилучшим образом оптимизировать производительность программы. В крайнем случае компилятор может быть вынужден эмулировать инструкции, не поддерживаемые на целевой платформе компиляции, заставляя его генерировать код или связывать вызов внешней библиотеки для получения результата, который в противном случае не поддается вычислению на этой платформе, даже если он поддерживается изначально. и более эффективен в аппаратном обеспечении на других платформах. Это часто имеет место во встроенных системах в отношении арифметики с плавающей запятой , где небольшие и маломощные микроконтроллеры часто не имеют аппаратной поддержки арифметики с плавающей запятой и, следовательно, требуют дорогостоящих в вычислительном отношении программных процедур для выполнения вычислений с плавающей запятой.
Меры обычно выражаются как функция размера входных данных .
Двумя наиболее распространенными мерами являются:
Для компьютеров, питание которых осуществляется от аккумулятора (например, ноутбуков и смартфонов ) или для очень длительных/больших вычислений (например, суперкомпьютеров ), представляют интерес другие меры:
По состоянию на 2018 год [обновлять]энергопотребление становится важным показателем для вычислительных задач всех типов и всех масштабов, начиная от встроенных устройств Интернета вещей и заканчивая устройствами на кристалле и серверными фермами . Эту тенденцию часто называют «зелеными вычислениями» .
Менее распространенные меры вычислительной эффективности также могут быть актуальны в некоторых случаях:
Проанализируйте алгоритм, обычно используя анализ временной сложности , чтобы получить оценку времени работы в зависимости от размера входных данных. Результат обычно выражается с использованием нотации Big O. Это полезно для сравнения алгоритмов, особенно когда необходимо обработать большой объем данных. Для сравнения производительности алгоритма при небольшом объеме данных необходимы более подробные оценки, хотя это, вероятно, будет иметь меньшее значение. Алгоритмы, включающие параллельную обработку, могут оказаться более трудными для анализа .
Используйте эталонный тест для определения времени использования алгоритма. Многие языки программирования имеют доступную функцию, которая обеспечивает использование процессорного времени . Для долговыполняющихся алгоритмов также может представлять интерес затраченное время. Результаты обычно следует усреднять по нескольким тестам.
Профилирование на основе запуска может быть очень чувствительным к конфигурации оборудования и возможности одновременного запуска других программ или задач в многопроцессорной и многопрограммной среде.
Этот вид теста также во многом зависит от выбора конкретного языка программирования, компилятора и его опций, поэтому все сравниваемые алгоритмы должны быть реализованы в одинаковых условиях.
Этот раздел посвящен использованию ресурсов памяти ( регистров , кэша , ОЗУ , виртуальной памяти , вторичной памяти ) во время выполнения алгоритма. Что касается анализа времени, описанного выше, анализируйте алгоритм, обычно используя анализ пространственной сложности, чтобы получить оценку необходимой оперативной памяти в зависимости от размера входных данных. Результат обычно выражается с использованием нотации Big O.
Необходимо учитывать до четырех аспектов использования памяти:
Ранние электронные компьютеры и первые домашние компьютеры имели относительно небольшой объем рабочей памяти. Например, автоматический калькулятор с электронным запоминанием задержки (EDSAC) 1949 года имел максимальную рабочую память в 1024 17-битных слов, а Sinclair ZX80 1980 года изначально имел 1024 8-битных байта рабочей памяти. В конце 2010-х годов для персональных компьютеров характерно иметь от 4 до 32 ГБ оперативной памяти, что более чем в 300 миллионов раз больше памяти.
Современные компьютеры могут иметь относительно большие объемы памяти (возможно, гигабайты), поэтому необходимость втиснуть алгоритм в ограниченный объем памяти представляет собой гораздо меньшую проблему, чем раньше. Но наличие четырех разных категорий памяти может иметь существенное значение:
Алгоритм, объем памяти которого соответствует кэш-памяти, будет намного быстрее, чем алгоритм, который помещается в основную память, а тот, в свою очередь, будет намного быстрее, чем алгоритм, которому приходится прибегать к виртуальной памяти. По этой причине политики замены кэша чрезвычайно важны для высокопроизводительных вычислений, равно как и программирование с поддержкой кэша и выравнивание данных . Проблема еще больше усложняется тем, что некоторые системы имеют до трех уровней кэш-памяти с разной эффективной скоростью. Различные системы будут иметь разные объемы этих различных типов памяти, поэтому влияние потребностей алгоритма в памяти может сильно различаться от одной системы к другой.
На заре электронных вычислений, если алгоритм и его данные не помещались в основную память, алгоритм нельзя было использовать. В настоящее время использование виртуальной памяти обеспечивает больший объем памяти, но за счет производительности. Если алгоритм и его данные поместятся в кэш-память, то можно получить очень высокую скорость; в этом случае минимизация пространства также поможет минимизировать время. Это называется принципом локальности , и его можно подразделить на локальность отсчета , пространственную локальность и временную локальность . Алгоритм, который не полностью помещается в кэш-память, но обеспечивает локальность ссылки, может работать достаточно хорошо.
