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

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

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

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

Задний план

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

"Практически в каждом вычислении возможно большое разнообразие схем для последовательности процессов, и различные соображения должны влиять на выбор среди них для целей вычислительной машины. Одна важная цель состоит в том, чтобы выбрать такую ​​схему, которая будет иметь тенденцию сводиться к минимум времени, необходимого для завершения расчета »^[1]

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

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

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

Обзор

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

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

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

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

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

В теоретическом анализ алгоритмов, нормальная практика заключается в оценке их сложности в асимптотическом смысле. Наиболее часто используемые обозначения для описания потребления ресурсов или "сложности" - Дональд Кнут с Обозначение Big O, представляющий сложность алгоритма как функцию размера входных данных ${ textstyle scriptstyle n}$. Обозначение Big O - это асимптотический мера сложности функции, где ${ textstyle scriptstyle {е влево (п вправо) , = , { mathcal {O}} влево (г влево (п вправо) вправо)}}$ примерно означает, что время, необходимое для алгоритма, пропорционально ${ Displaystyle scriptstyle {г влево (п вправо)}}$, опуская условия более низкого порядка которые вносят меньше чем ${ Displaystyle scriptstyle {г влево (п вправо)}}$ к росту функции при ${ displaystyle scriptstyle n}$ становится сколь угодно большим. Эта оценка может ввести в заблуждение, когда ${ textstyle scriptstyle n}$ мала, но обычно достаточно точна, когда ${ textstyle scriptstyle n}$ велико из-за асимптотики обозначений. Например, пузырьковая сортировка может быть быстрее, чем Сортировка слиянием когда нужно отсортировать только несколько предметов; однако любая реализация, вероятно, будет соответствовать требованиям производительности для небольшого списка. Обычно программистов интересуют алгоритмы, которые масштаб эффективно для больших размеров ввода, а сортировка слиянием предпочтительнее пузырьковой сортировки для списков длины, встречающихся в большинстве программ с большим объемом данных.

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

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

Бенчмаркинг: измерение производительности

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

Некоторые тесты предоставляют возможности для проведения анализа, сравнивающего относительную скорость различных компилируемых и интерпретируемых языков, например^[3][4]и Игра "Тесты компьютерного языка" сравнивает производительность реализаций типичных задач программирования на нескольких языках программирования.

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

Проблемы реализации

Проблемы реализации также могут влиять на эффективность, такие как выбор языка программирования или способ, которым фактически кодируется алгоритм,^[6] или выбор компилятор для определенного языка, или варианты компиляции использовали, или даже Операционная система использовался. Во многих случаях язык, реализованный переводчик может быть намного медленнее, чем язык, реализованный компилятором.^[3] См. Статьи на своевременная компиляция и интерпретируемые языки.

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

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

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

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

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

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

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

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

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

По состоянию на 2018 год^{[Обновить]}, энергопотребление растет как важный показатель для вычислительных задач всех типов и масштабов, начиная от встроенный Интернет вещей устройства для система на кристалле устройства для серверные фермы. Эту тенденцию часто называют зеленые вычисления.

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

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

Время

Теория

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

Практика

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

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

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

Космос

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

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

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

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

Кеширование и иерархия памяти

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

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

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

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

Критика текущего состояния программирования

• Дэвид Мэй ФРС а Британский специалист в области информатики и в настоящее время Профессор из Информатика в Бристольский университет и основатель и Технический директор из XMOS Semiconductor, считает, что одна из проблем заключается в том, что Закон Мура для устранения недостатков. Он выдвинул «альтернативу» закону Мура (Закон мая ) заявил следующее:^[9]

Эффективность программного обеспечения снижается вдвое каждые 18 месяцев, что компенсирует закон Мура.

Мэй продолжает:

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

• Автор программного обеспечения Адам Н. Розенбург в своем блоге "Выход из строя цифрового компьютера", описал текущее состояние программирования как близкое к" горизонту программных событий "(намекая на вымышленное"Горизонт событий обуви"описанный Дуглас Адамс в его Автостопом по Галактике книга^[10]). По его оценкам, с 1980-х годов произошло снижение производительности на коэффициент 70 дБ, или «99,99999 процентов его способности доставлять товары», с 1980-х годов - «Когда Артур Кларк сравнил реальность вычислений в 2001 году с компьютером HAL 9000 в его книге 2001: Космическая одиссея, он отметил, насколько удивительно маленькие и мощные компьютеры, но каким разочаровывающим стало компьютерное программирование ».

Конкурсы на лучшие алгоритмы

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

• Wired журнал^[11]

Смотрите также

• Анализ алгоритмов - как определить ресурсы, необходимые алгоритму
• Арифметическое кодирование - форма переменная длина энтропийное кодирование для эффективного сжатия данных
• Ассоциативный массив - структуру данных, которую можно сделать более эффективной с помощью Деревья Патрисии или Джуди массивы
• Контрольный показатель —Метод для измерения сравнительного времени выполнения в определенных случаях
• Лучший, худший и средний случай - соображения по оценке времени выполнения в трех сценариях
• Алгоритм двоичного поиска - простой и эффективный метод поиска в отсортированных массивах
• Таблица ответвлений - метод уменьшения длины пути команд, размер Машинный код, (а часто и память)
• Сравнение парадигм программирования - особенности производительности парадигмы
• Оптимизация компилятора - оптимизация на основе компилятора
• Вычислительная сложность математических операций
• Теория вычислительной сложности
• Производительность компьютера - показатели компьютерного оборудования
• Сжатие данных —Снижение полосы пропускания передачи и дискового пространства
• Индекс базы данных —Структура данных, повышающая скорость операций извлечения данных из таблицы базы данных.
• Энтропийное кодирование - эффективное кодирование данных с использованием частоты появления строк в качестве критерия для замены
• Вывоз мусора - автоматическое освобождение памяти после использования
• Экологичные вычисления - переход к внедрению «зеленых» технологий с меньшим потреблением ресурсов
• Алгоритм Хаффмана - алгоритм эффективного кодирования данных
• Повышение производительности управляемого кода —Библиотека Microsoft MSDN
• Местоположение ссылки - во избежание кеширование задержки, вызванные доступом к нелокальной памяти
• Оптимизация цикла
• Управление памятью
• Оптимизация (информатика)
• Анализ производительности - методы измерения фактической производительности алгоритма во время выполнения
• Вычисления в реальном времени - другие примеры критичных ко времени приложений
• Анализ во время выполнения - оценка ожидаемого времени выполнения и масштабируемости алгоритма
• Одновременная многопоточность
• Алгоритм сортировки § Сравнение алгоритмов
• Спекулятивное исполнение или Нетерпеливое исполнение
• Прогноз ветвления
• Суперпоточность
  • Hyper Threading
• Резьбовой код - аналогично таблице виртуальных методов или таблице ветвей
• Таблица виртуальных методов - таблица веток с динамически назначаемыми указателями для диспетчеризации

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

внешние ссылки

• Анимация алгоритма Бойера-Мура (Java-апплет )
• «Как алгоритмы формируют наш мир». А TED (конференция) Выступление Кевина Славина.
• Заблуждения об алгоритмической эффективности в средней школе