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

редактировать

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

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

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

Содержание

  • 1 Предпосылки
  • 2 Обзор
    • 2.1 Теоретический анализ
    • 2.2 Бенчмаркинг: измерение производительности
    • 2.3 Проблемы реализации
  • 3 Измерения использования ресурсов
    • 3.1 Время
      • 3.1.1 Теория
      • 3.1.2 Практика
    • 3.2 Пространство
      • 3.2.1 Кэширование и иерархия памяти
  • 4 Критика текущего состояния программирования
  • 5 Конкурсы на лучшие алгоритмы
  • 6 См. Также
  • 7 Ссылки
  • 8 Внешние ссылки

Предпосылки

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

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

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

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

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

Обзор

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

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

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

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

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

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

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

NotationNameПримеры
O (1) {\ displaystyle { \ mathcal {O}} (1) \,}{\ displaystyle {\ mathcal {O}} (1) \,} константа Нахождение медианы из отсортированного списка измерений; Использование таблицы поиска постоянного размера ; Использование подходящей хэш-функции для поиска элемента.
O (log ⁡ n) {\ displaystyle {\ mathcal {O}} (\ log {n}) \,}{\ displaystyle {\ mathcal {O}} (\ log {n}) \,} логарифмический Поиск элемента в отсортированном массиве с помощью двоичного поиска или сбалансированное поисковое дерево, а также все операции в биномиальной куче.
O (n) {\ displaystyle {\ mathcal {O}} (n) \,}{\ displaystyle {\ mathcal {O}} (n) \,} linear Нахождение элемента в несортированном списке или искаженном дереве (худший случай) или в несортированном массиве; Добавление двух n-битных целых чисел с помощью переноса пульсации.
O (n log ⁡ n) {\ displaystyle {\ mathcal {O}} (n \ log n) \,}{\ displaystyle {\ mathcal {O}} (n \ log n) \,} linearithmic, loglinear, или квазилинейныйВыполнение быстрого преобразования Фурье ; heapsort, quicksort (лучший и средний случай ) или сортировка слиянием
O (n 2) {\ displaystyle {\ mathcal {O }} (n ^ {2}) \,}{\ displaystyle {\ mathcal {O}} (n ^ {2}) \,} квадратичный Умножение двух n-значных чисел на простой алгоритм ; пузырьковая сортировка (наихудший случай или наивная реализация), сортировка оболочки, быстрая сортировка (наихудший случай ), сортировка по выбору или вставка sort
O (cn), c>1 {\ displaystyle {\ mathcal {O}} (c ^ {n}), \; c>1}{\displaystyle {\mathcal {O}}(c^{n}),\;c>1} экспоненциальный <Поиск оптимального (не->приблизительное ) решение задачи коммивояжера с использованием динамического программирования ; определение эквивалентности двух логических операторов с использованием перебора

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

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

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

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

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

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

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

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

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

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

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

Два наиболее распространенных показателя являются:

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

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

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

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

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

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

Время

Теория

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

Практика

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

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

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

Пространство

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

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

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

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

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

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

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

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

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

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

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

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

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

Соревнования для лучшие алгоритмы

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

См. также

ссылок

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

В Викиучебнике есть книга по теме: Оптимизация кода для скорости
Последняя правка сделана 2021-06-10 22:44:39
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте