Эффективность алгоритма

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

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

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

Фон

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

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

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

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

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

Обзор

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

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

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

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

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

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

Вот несколько примеров нотации «О большое», применяемой к асимптотической временной сложности алгоритмов:

Измерение производительности

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Время

Теория

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

Упражняться

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

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

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

Космос

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

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

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

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

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

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

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

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

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

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

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

Ссылки

↑ Грин, Кристофер, Классика в истории психологии , получено 19 мая 2013 г.
^ Кнут, Дональд (1974), «Структурное программирование с go-to операторами» (PDF) , Computing Surveys , 6 (4): 261–301, CiteSeerX 10.1.1.103.6084 , doi :10.1145/356635.356640, S2CID 207630080, заархивировано из оригинала (PDF) 24 августа 2009 г. , извлечено 19 мая 2013 г.
^ ab "Floating Point Benchmark: Comparing Languages (Fourmilog: None Dare Call It Reason)". Fourmilab.ch. 4 августа 2005 г. Получено 14 декабря 2011 г.
^ "Whetstone Benchmark History". Roylongbottom.org.uk . Получено 14 декабря 2011 г. .
^ Сотрудники OSNews. «Обзор производительности девяти языков: сравнительный анализ математических и файловых операций ввода-вывода». osnews.com . Получено 18 сентября 2018 г.
^ Кригель, Ханс-Петер ; Шуберт, Эрих; Зимек, Артур (2016). «(Черное) искусство оценки времени выполнения: сравниваем ли мы алгоритмы или реализации?». Knowledge and Information Systems . 52 (2): 341–378. doi :10.1007/s10115-016-1004-2. ISSN 0219-1377. S2CID 40772241.
^ Гай Льюис Стил-младший. «Развенчание мифа о «дорогом вызове процедур», или Реализации вызова процедур, считающиеся вредными, или Лямбда: Окончательный GOTO». Лаборатория ИИ Массачусетского технологического института. Записка лаборатории ИИ AIM-443. Октябрь 1977 г.[1]
^ abcd Хеннесси, Джон Л.; Паттерсон, Дэвид А.; Асанович, Крсте ; Бакос, Джейсон Д.; Колвелл, Роберт П.; Бхаттачарджи, Абхишек; Конте, Томас М.; Дуато, Хосе; Франклин, Диана; Голдберг, Дэвид; Джуппи, Норман П.; Ли, Шэн; Муралиманохар, Навин; Петерсон, Грегори Д.; Пинкстон, Тимоти Марк; Ранганатан, Пракаш; Вуд, Дэвид Аллен; Янг, Клиффорд; Заки, Амр (2011). Архитектура компьютера: количественный подход (шестое изд.). Elsevier Science. ISBN 978-0128119051. OCLC 983459758.