В информатике, алгоритмическая эффективность является свойством алгоритма , который относится к количеству вычислительных ресурсов, используемых алгоритмом. Алгоритм должен быть проанализирован для определения использования ресурсов, а эффективность алгоритма может быть измерена на основе использования различных ресурсов. Алгоритмическую эффективность можно рассматривать как аналог производительности проектирования для повторяющегося или непрерывного процесса.
Для максимальной эффективности мы хотим минимизировать использование ресурсов. Однако разные ресурсы, такие как время и пространство сложность, нельзя сравнивать напрямую, поэтому какой из двух алгоритмов считается более эффективным, часто зависит от того, какой показатель эффективности считается наиболее важным.
Например, пузырьковая сортировка и timsort - это алгоритмы для сортировки списка элементов от наименьшего к наибольшему. Пузырьковая сортировка сортирует список во времени, пропорциональном квадрату количества элементов (, см. нотация Big O ), но требует лишь небольшого количества дополнительной памяти , которая постоянна по отношению к длине списка (). Timsort сортирует список по времени линеарифмически (пропорционально количеству, умноженному на его логарифм) по длине списка (), но для него требуется место linear по длине списка (). Если для данного приложения требуется высокоскоростная сортировка больших списков, лучше выбрать timsort; однако, если минимизация объема памяти, используемого при сортировке, важнее, пузырьковая сортировка - лучший выбор.
Важность эффективности по отношению ко времени была подчеркнута Адой Лавлейс в 1843 году применительно к Механическая аналитическая машина Чарльза Бэббиджа :
«Почти в каждом вычислении возможно большое количество разнообразных схем для последовательности процессов, и различные соображения должны влиять на выбор среди них для целей вычислительной машины. Одна из важных задач состоит в том, чтобы выбрать такую схему, которая должна сводить к минимуму время, необходимое для завершения расчета "
Ea rly электронные компьютеры были сильно ограничены как скоростью операций, так и объемом доступной памяти. В некоторых случаях было обнаружено, что существует компромисс между пространством и временем, при котором задача может быть обработана либо с помощью быстрого алгоритма, который использует довольно много рабочей памяти, либо или с помощью более медленного алгоритма, использующего очень мало рабочей памяти. Тогда инженерный компромисс заключался в использовании самого быстрого алгоритма, который поместился бы в доступную память.
Современные компьютеры значительно быстрее, чем первые компьютеры, и имеют гораздо больший объем доступной памяти (гигабайт вместо килобайт ). Тем не менее, Дональд Кнут подчеркнул, что эффективность по-прежнему является важным фактором:
«В общепринятых инженерных дисциплинах легко достижимое улучшение на 12% никогда не считается маргинальным, и я считаю, что такая же точка зрения должна преобладать в разработке программного обеспечения. "
Алгоритм считается эффективным, если его потребление ресурсов, также известное как вычислительные затраты, находится на некотором приемлемом уровне или ниже. Грубо говоря, «приемлемый» означает: он будет работать в течение разумного промежутка времени или пространства на доступном компьютере, обычно как функция размера ввода. С 1950-х годов в компьютерах произошло резкое увеличение как доступной вычислительной мощности, так и доступного объема памяти, поэтому нынешние приемлемые уровни были бы неприемлемыми даже 10 лет назад. Фактически, благодаря приблизительному удвоению мощности компьютера каждые 2 года задачи, которые приемлемо эффективны на современных смартфонах и встроенных системах, могли оказаться неприемлемо неэффективными для промышленные серверы 10 лет назад.
Производители компьютеров часто выпускают новые модели, часто с более высокой производительностью. Стоимость программного обеспечения может быть довольно высокой, поэтому в некоторых случаях самым простым и дешевым способом повышения производительности может быть просто покупка более быстрого компьютера, при условии, что он совместим с существующим компьютером.
Есть много способов, которыми можно измерить ресурсы, используемые алгоритмом: два наиболее распространенных показателя - это скорость и использование памяти; другие меры могут включать скорость передачи, временное использование диска, долгосрочное использование диска, энергопотребление, общая стоимость владения, время отклика на внешние воздействия и т. д. Многие из этих показателей зависят от от размера входных данных алгоритма, то есть количества данных, которые необходимо обработать. Они также могут зависеть от того, как организованы данные; например, некоторые алгоритмы сортировки плохо работают с данными, которые уже отсортированы или отсортированы в обратном порядке.
На практике есть и другие факторы, которые могут повлиять на эффективность алгоритма, например требования к точности и / или надежности. Как подробно описано ниже, способ реализации алгоритма также может иметь значительное влияние на фактическую эффективность, хотя многие аспекты этого связаны с проблемами оптимизации.
В теоретическом анализе алгоритмов обычной практикой является оценка их сложности в асимптотическом смысле. Наиболее часто используемая нотация для описания потребления ресурсов или «сложности» - это Big O Дональда Кнута, представляющая сложность алгоритма как функцию размера входных данных . Обозначение Big O - это асимптотическая мера сложности функции, где примерно означает, что время, необходимое для алгоритма, пропорционально , опуская члены более низкого порядка, вклад которых меньше на рост функции, поскольку становится произвольно большим. Эта оценка может вводить в заблуждение, когда мало, но обычно достаточно точна, когда - большой, поскольку обозначения асимптотичны. Например, пузырьковая сортировка может быть быстрее, чем сортировка слиянием, когда нужно отсортировать только несколько элементов; однако любая реализация, вероятно, будет соответствовать требованиям производительности для небольшого списка. Обычно программистов интересуют алгоритмы, которые эффективно масштабируют до больших входных размеров, и сортировка слиянием предпочтительнее пузырьковой сортировки для списков длины, встречающихся в большинстве программ с большим объемом данных.
Некоторые примеры нотации Big O, применяемой к асимптотической временной сложности алгоритмов, включают:
Notation | Name | Примеры |
---|---|---|
константа | Нахождение медианы из отсортированного списка измерений; Использование таблицы поиска постоянного размера ; Использование подходящей хэш-функции для поиска элемента. | |
логарифмический | Поиск элемента в отсортированном массиве с помощью двоичного поиска или сбалансированное поисковое дерево, а также все операции в биномиальной куче. | |
linear | Нахождение элемента в несортированном списке или искаженном дереве (худший случай) или в несортированном массиве; Добавление двух n-битных целых чисел с помощью переноса пульсации. | |
linearithmic, loglinear, или квазилинейный | Выполнение быстрого преобразования Фурье ; heapsort, quicksort (лучший и средний случай ) или сортировка слиянием | |
квадратичный | Умножение двух n-значных чисел на простой алгоритм ; пузырьковая сортировка (наихудший случай или наивная реализация), сортировка оболочки, быстрая сортировка (наихудший случай ), сортировка по выбору или вставка sort | |
экспоненциальный | <Поиск оптимального (не->приблизительное ) решение задачи коммивояжера с использованием динамического программирования ; определение эквивалентности двух логических операторов с использованием перебора |
Для новых версий программного обеспечения или для сравнения с конкурирующими системами иногда используются тесты, которые помогают измерить относительную производительность алгоритмов. Если новая алгоритм сортировки, например, его можно сравнить с его предшественниками, чтобы убедиться, что он по крайней мере эффективен с известными данными с учетом любых функциональных улучшений. Клиенты могут использовать контрольные показатели при сравнении различных продуктов от альтернативных поставщиков, чтобы оценить, какой продукт лучше всего соответствует их конкретным требованиям с точки зрения функциональности и производительности. Например, в мире мэйнфреймов некоторые проприетарные sort продукты независимых компаний-разработчиков программного обеспечения, такие как Syncsort, конкурируют с продуктами таких крупных поставщиков, как IBM для скорости.
Некоторые тесты предоставляют возможности для проведения анализа, сравнивая, например, относительную скорость различных компилируемых и интерпретируемых языков, а Игра компьютерных языковых тестов сравнивает производительность реализаций типичных проблем программирования в нескольких программах языков.
Даже создание тестов «сделай сам » может продемонстрировать относительную производительность различных языков программирования с использованием множества критериев, заданных пользователем. Это довольно просто, как демонстрирует на примере «Обзор производительности девяти языков» Кристофер В. Коуэлл-Ша.
Проблемы реализации также могут влиять на эффективность, например выбор языка программирования, или способ, которым фактически закодирован алгоритм, или выбор компилятора для конкретного языка, или используемые параметры компиляции, или даже используется операционная система. Во многих случаях язык, реализованный интерпретатором , может быть намного медленнее, чем язык, реализованный компилятором. См. Статьи о своевременной компиляции и интерпретируемых языках.
Существуют и другие факторы, которые могут повлиять на проблемы с временем или пространством, но которые могут быть вне контроля программиста; к ним относятся выравнивание данных, гранулярность данных, расположение кэша, согласованность кеша, сборка мусора, параллелизм на уровне команд, многопоточность (на аппаратном или программном уровне), одновременная многозадачность и вызовы подпрограмм.
Некоторые процессоры имеют возможности для векторной обработки, что позволяет одной инструкции работать с несколькими операндами ; Программисту или компилятору может быть непросто использовать эти возможности. Алгоритмы, разработанные для последовательной обработки, могут нуждаться в полной переработке, чтобы использовать параллельную обработку, или их можно легко перенастроить. По мере того как параллельные и распределенные вычисления становятся все более важными в конце 2010-х годов, все больше инвестиций вкладывается в эффективные высокого уровня API для параллельных и распределенных вычислительных систем, таких как CUDA, TensorFlow, Hadoop, OpenMP и MPI.
Еще одна проблема, которая может возникнуть при программировании, заключается в том, что процессоры, совместимые с одним и тем же набором инструкций (например, x86-64 или ARM ), могут реализовывать инструкции в разных Таким образом, инструкции, которые являются относительно быстрыми на некоторых моделях, могут быть относительно медленными на других моделях. Это часто создает проблемы для оптимизирующих компиляторов, которые должны обладать большим объемом знаний о конкретном CPU и другом оборудовании, доступном на цели компиляции, чтобы наилучшим образом оптимизировать программу по производительности. В крайнем случае компилятор может быть вынужден эмулировать инструкции, не поддерживаемые на целевой платформе компиляции, заставляя его генерировать код или ссылку на внешнюю вызов библиотеки для получения результата, который в противном случае невозможно вычислить на этой платформе, даже если он изначально поддерживается и более эффективен на оборудовании на других платформах. Это часто имеет место в встроенных системах по отношению к арифметике с плавающей запятой, где в маленьких и маломощных микроконтроллерах часто не хватает аппаратного обеспечения. поддержка арифметики с плавающей запятой и, следовательно, требует дорогостоящих в вычислительном отношении программных средств для выполнения вычислений с плавающей запятой.
Меры обычно выражаются как функция размера входных данных .
Два наиболее распространенных показателя являются:
Для компьютеров, питание которых обеспечивается аккумулятор (например, ноутбуки и смартфоны ), или для очень длинных / больших вычислений (например, суперкомпьютеры ), другими интересными показателями являются:
С 2018 года потребление энергии растет как важный показатель для вычислительных задач всех типов и во всех масштабах: от встроенных устройств Интернета вещей до устройств система на кристалле до серверных ферм. Эту тенденцию часто называют экологически чистыми вычислениями.
В некоторых случаях могут иметь значение менее распространенные показатели вычислительной эффективности:
Проанализируйте алгоритм, обычно используя анализ временной сложности, чтобы получить оценку времени выполнения как функцию размера входных данных. Результат обычно выражается с использованием нотации Big O. Это полезно для сравнения алгоритмов, особенно когда нужно обработать большой объем данных. Для сравнения производительности алгоритмов при небольшом объеме данных необходимы более подробные оценки, хотя это, вероятно, будет иметь меньшее значение. Алгоритмы, включающие параллельную обработку, могут быть труднее анализировать.
Используйте тест, чтобы рассчитать время использования алгоритма. Многие языки программирования имеют доступную функцию, которая обеспечивает использование процессорного времени. Для длительно работающих алгоритмов также может быть интересным прошедшее время. Обычно результаты следует усреднять по нескольким тестам.
Профилирование на основе запуска может быть очень чувствительным к конфигурации оборудования и возможности одновременного выполнения других программ или задач в многопроцессорной и многопрограммной Окружающая среда.
Этот вид теста также сильно зависит от выбора конкретного языка программирования, компилятора и параметров компилятора, поэтому сравниваемые алгоритмы должны быть реализованы в одинаковых условиях.
Этот раздел касается использования ресурсов памяти (регистры, кэш, RAM, виртуальная память, вторичная память ) во время выполнения алгоритма. Что касается анализа времени, описанного выше, проанализируйте алгоритм, обычно используя анализ пространственной сложности, чтобы получить оценку требуемой оперативной памяти в зависимости от размера входных данных. Результат обычно выражается с использованием нотации Big O.
. Необходимо учитывать до четырех аспектов использования памяти:
Ранние электронные компьютеры и первые домашние компьютеры имели относительно небольшие объемы рабочей памяти. Например, автоматический калькулятор с электронным запоминанием задержки (EDSAC) 1949 года имел максимальную рабочую память 1024 17-битных слов, тогда как Sinclair ZX80 1980 года изначально имел 1024 8-битных байта. рабочей памяти. В конце 2010-х годов для персональных компьютеров типично иметь от 4 до 32 ГБ ОЗУ, что более чем в 300 миллионов раз превышает объем памяти.
Текущие компьютеры могут иметь относительно большие объемы памяти (возможно, гигабайты), поэтому необходимость втиснуть алгоритм в ограниченный объем памяти - гораздо меньшая проблема. раньше был. Но наличие четырех разных категорий памяти может иметь значение:
Алгоритм, объем памяти которого умещается в кэш-памяти, будет намного быстрее, чем алгоритм, который умещается в основной памяти, что, в свою очередь, будет намного быстрее, чем алгоритм, использующий виртуальную память. Из-за этого политики замены кеша чрезвычайно важны для высокопроизводительных вычислений, как и программирование с учетом кеширования и выравнивание данных. Чтобы еще больше усложнить проблему, некоторые системы имеют до трех уровней кэш-памяти с различными эффективными скоростями. Разные системы будут иметь разное количество этих различных типов памяти, поэтому влияние потребностей алгоритмов в памяти может сильно различаться от одной системы к другой.
На заре электронных вычислений, если алгоритм и его данные не помещались в основную память, алгоритм нельзя было использовать. В настоящее время использование виртуальной памяти, по-видимому, обеспечивает большой объем памяти, но за счет производительности. Если алгоритм и его данные умещаются в кэш-памяти, то можно получить очень высокую скорость; в этом случае минимизация пространства также поможет минимизировать время. Это называется принципом локальности, и его можно подразделить на эталонную локальность, пространственную локальность и временную локальность. Алгоритм, который не помещается полностью в кэш-память, но демонстрирует локальность ссылки, может работать достаточно хорошо.
Эффективность программного обеспечения снижается вдвое каждые 18 месяцев, что компенсирует закон Мура
В В повсеместных системах сокращение вдвое выполняемых инструкций может удвоить время автономной работы, а большие наборы данных открывают большие возможности для улучшения программного обеспечения и алгоритмов: сокращение количества операций с N x N до N x log (N) имеет драматический эффект, когда N велико.... для N = 30 миллиардов это изменение равно пятидесятилетнему совершенствованию технологий.
На следующие конкурсы приглашаются заявки на лучшие алгоритмы, основанные на некоторых произвольных критериях, установленных судьями:
В Викиучебнике есть книга по теме: Оптимизация кода для скорости |