Русская Википедия:Эффективность алгоритма

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

Заметим, что данная статья НЕ об оптимизации алгоритма, которая обсуждается в статьях оптимизация программы, оптимизирующий компилятор, Шаблон:Iw, Шаблон:Iw, и так далее. Термин «оптимизация» сам по себе вводит в заблуждение, поскольку всё, что может быть сделано, попадает под определение «улучшение».

История вопроса

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

«Почти во всех вычислениях возможен большой выбор конфигураций для успешного завершения процесса и различные соглашения должны влиять на выбор с целью выполнения вычислений. Существенная вещь — выбор конфигурации, которая приведёт к минимизации времени, необходимого для выполнения вычисления»Шаблон:Sfn.

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

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

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

Обзор

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

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

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

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

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

В теоретическом анализе алгоритмов обычной практикой является оценка сложности алгоритма в его асимптотическом поведении, то есть для отражения сложности алгоритма как функции от размера входа n используется нотация «O» большое. Эта оценка, в основном, достаточно точна при большом n, но может привести к неправильным выводам при малых значениях n (так, сортировка пузырьком, считающаяся медленной, может оказаться быстрее «быстрой сортировки», если нужно отсортировать лишь несколько элементов).

Некоторые примеры нотации «O» большое:

Обозначение Название Примеры
<math>O(1)\,</math> постоянное Определение, чётно или нечётно число. Использование таблицы поиска постоянного размера. Использование подходящей хеш-функции для выбора элемента.
<math>O(\log n)\,</math> логарифмическое Нахождение элемента в отсортированном массиве с помощью двоичного поиска или сбалансированного дерева, как и операции в биномиальной куче.
<math>O(n)\,</math> линейное Поиск элемента в несортированном списке или несбалансированном дереве (худший случай). Сложение двух n-битных чисел с использованием сквозного переноса.
<math>O(n\log n)\,</math> квазилинейное, логарифмически линейное Вычисление быстрого преобразования Фурье, пирамидальная сортировка, быстрая сортировка (лучший и средний случай), сортировка слиянием
<math>O(n^2)\,</math> квадратное Умножение двух n-значных чисел с помощью простого алгоритма, сортировка пузырьком (худший случай), сортировка Шелла, быстрая сортировка (худший случай), сортировка выбором, сортировка вставками
<math>O(c^n),\;c>1</math> экспоненциальное Нахождение (точного) решения задачи коммивояжёра с помощью динамического программирования. Определение, не являются ли два логических утверждения эквивалентными с помощью полного перебора

Проверочные испытания: измерение производительности

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

Некоторые тесты производительности дают возможность проведения сравнительного анализа различных компилирующих и интерпретирующих языков, как, например, Roy Longbottom’s PC Benchmark CollectionШаблон:Sfn, а Шаблон:Не переведено 5 сравнивает производительность реализаций типичных задач в некоторых языках программирования.

(Достаточно легко создать «самодельные» тесты производительности для получения представления об относительной эффективности различных языков программирования, используя набор пользовательских критериев, как это сделал Христофер Коувел-Шах в статье «Nine language Performance roundup»)[1]

Вопросы реализации

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

Есть и другие факторы, которые могут повлиять на время или используемую память, но которые оказываются вне контроля программиста. Сюда попадают выравнивание данных, Шаблон:Iw, сборка мусора, параллелизм на уровне команд и вызов подпрограммШаблон:Sfn.

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

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

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

Измерения обычно выражаются как функция от размера входа n.

Два наиболее важных измерения:

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

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

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

В некоторых случаях нужны другие, менее распространённые измерения:

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

Время

Теория

Для анализа алгоритма обычно используется анализ временно́й сложности алгоритма, чтобы оценить время работы как функцию от размера входных данных. Результат обычно выражается в терминах «O» большое. Это полезно для сравнения алгоритмов, особенно в случае обработки большого количества данных. Более детальные оценки нужны для сравнения алгоритмов, когда объём данных мал (хотя такая ситуация вряд ли вызовет проблемы). Алгоритмы, которые включают параллельные вычисления, могут оказаться для анализа более трудными.

Практика

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

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

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

Память

Этот раздел касается использования основной памяти (зачастую, RAM) нужной алгоритму. Как и для временно́го анализа выше, для анализа алгоритма обычно используется анализ Шаблон:Iw, чтобы оценить необходимую память времени исполнения как функцию от размера входа. Результат обычно выражается в терминах «O» большое.

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

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

Ранние электронные компьютеры и домашние компьютеры имели относительно малый объём рабочей памяти. Так, в 1949 EDSAC имел максимальную рабочую память 1024 17-битных слов, а в 1980 Sinclair ZX80 выпускался с 1024 байтами рабочей памяти.

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

  • Кэш (часто, статическая RAM) — работает на скоростях, сравнимых с ЦПУ
  • Основная физическая память (часто, динамическая RAM) — работает чуть медленнее ЦПУ
  • Виртуальная память (зачастую, на диске) — даёт иллюзию огромной памяти, но работает в тысячи раз медленнее RAM.

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

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

Примеры эффективных алгоритмов

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

Программы становятся медленнее более стремительно, чем компьютеры становятся быстрее.

Мэй утверждает:

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

  • Программист Адам Н. Розербург в своём блоге «The failure of the Digital computer », описал текущее состояние программирования как близкое к «Software event horizon» (уровню программной катастрофы, намек на фантастический «shoe event horizon» (уровень обувной катастрофы), описанный Дугласом Адамсом в его книге «Hitchhiker’s Guide to the Galaxy» (Автостопом по галактике)[3]). Он оценил падение производительности на 70 dB, или на «99.99999 % от возможного», по сравнению с 1980-ми годами — «когда Артур Кларк сравнил вычислительные способности компьютеров 2001 с компьютером HAL в книге 2001: A Space Odyssey, он указал, что удивительно малы и мощны были компьютеры, но программы стали печально разочаровывающими».

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

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

См. также

Примечания

Шаблон:Примечания

Литература

Ссылки

Шаблон:Качество программного обеспечения Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Nine Language Performance Round-up: Benchmarking Math & File I/O | OSnews
  2. ↑ Шаблон:Cite web
  3. ↑ http://www.the-adam.com/adam/rantrave/computers.htm
  4. ↑ Шаблон:Cite news
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Эффективность_алгоритма&oldid=11412802