Эффективность алгоритма: Эффективность алгоритмов: простое объяснение большого «О»
Эффективность алгоритма — Карта знаний
- Эффективность алгоритма — это свойство алгоритма, которое связано с вычислительными ресурсами, используемыми алгоритмом. Алгоритм должен быть проанализирован с целью определения необходимых алгоритму ресурсов. Эффективность алгоритма можно рассматривать как аналог производственной производительности повторяющихся или непрерывных процессов.
Для достижения максимальной эффективности мы желаем уменьшить использование ресурсов. Однако различные ресурсы (такие как время и память) нельзя сравнить напрямую, так что какой из двух алгоритмов считать более эффективным часто зависит от того, какой фактор более важен, например, требование высокой скорости, минимального использования памяти или другой меры эффективности.
Заметим, что данная статья НЕ об оптимизации алгоритма, которая обсуждается в статьях оптимизация программы, оптимизирующий компилятор, оптимизация циклов, оптимизатор объектного кода, и так далее. Термин «оптимизация» сам по себе вводит в заблуждение, поскольку всё, что может быть сделано, попадает под определение «улучшение».
Источник: Википедия
Связанные понятия
Оптимизация — модификация системы для улучшения её эффективности. Система может быть одиночной компьютерной программой, цифровым устройством, набором компьютеров или даже целой сетью, такой как Интернет.
Суперкомпиляция, или метакомпиляция, — специальная техника оптимизации алгоритмов, основанная на знании конкретных входных данных алгоритма. Суперкомпилятор принимает исходный код алгоритма плюс некоторые данные о входных параметрах и возвращает новый исходный код, который исполняет свою задачу на этих данных быстрее или является лучше исходного алгоритма по каким-то другим показателям. Очень часто под суперкомпиляцией неверно понимают глобальную оптимизацию программы, то есть эквивалентные преобразования…
Полностью гомоморфное шифрование — шифрование, позволяющее для данного шифротекста π1,…,πt любому (не только держателю ключа) получить шифротекст любой желаемой функции f(π1,…,πt), до тех пор, пока данная функция может быть эффективно вычислена.
Нагрузочное тестирование (англ. load testing) — подвид тестирования производительности, сбор показателей и определение производительности и времени отклика программно-технической системы или устройства в ответ на внешний запрос с целью установления соответствия требованиям, предъявляемым к данной системе (устройству).
Оптимизирующий компилятор — компилятор, в котором используются различные методы получения более оптимального программного кода при сохранении его функциональных возможностей. Наиболее распространённые цели оптимизации: сокращение времени выполнения программы, повышение производительности, компактификация программного кода, экономия памяти, минимизация энергозатрат, уменьшение количества операций ввода-вывода.
Упоминания в литературе
В результате фирменная гарантия на готовый SSD с микропроцессором SandForce 2200/2100 может достигать пяти лет, поскольку и теоретически, и практически доказана эффективность алгоритмов, перераспределяющих нагрузку на все входящие в состав полупроводникового накопителя ячейки памяти. Суммарная емкость микросхем NAND в составе такого накопителя равна 256 Гбайт, но 16 из них выделены под служебные нужды – для хранения контрольных сумм и таблиц размещения данных.
Связанные понятия (продолжение)
Поточный алгоритм (англ. streaming algorithm) — алгоритм для обработки последовательности данных в один или малое число проходов.
Полный перебор (или метод «грубой силы», англ. brute force) — метод решения математических задач. Относится к классу методов поиска решения исчерпыванием всевозможных вариантов. Сложность полного перебора зависит от количества всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий.
Цифровой сигнальный процессор (англ. digital signal processor, DSP, цифровой процессор обработки сигналов (ЦПОС)) — специализированный микропроцессор, предназначенный для обработки оцифрованных сигналов (обычно, в режиме реального времени).
Хот-спот (англ. hotspot) — участок кода в программе, на который приходится бо́льшая часть исполняемых инструкций процессора или на исполнение которого процессор затрачивает очень много времени (одни инструкции исполняются быстрее, а другие — медленнее). Хот-споты могут являться узкими местами программы, если на них приходится лишняя нагрузка из-за неэффективности кода, — в таком случае они могут быть подвергнуты оптимизации.
Источники энтропии используются для накопления энтропии, с последующим получением из неё начального значения (англ. initial value, seed), необходимого генераторам истинно случайных чисел (ГСЧ) для формирования случайных чисел. Отличие от генератора псевдослучайных чисел (ГПСЧ) в том, что ГПСЧ использует единственное начальное значение, откуда и получается его псевдослучайность, а ГСЧ всегда формирует случайное число, имея в начале высококачественную случайную величину, предоставленную различными…
В информатике под алгоритмами кэширования (часто называемыми алгоритмами вытеснения или политиками вытеснения, а также «алгоритмами/политиками замещения») понимают оптимизацию инструкций — алгоритмы — особая компьютерная программа или аппаратно поддерживаемая структура, способная управлять кэшем информации, хранимой в компьютере. Когда кэш заполнен, алгоритм должен выбрать, что именно нужно удалить из него, чтобы иметь возможность записи (в кэш) новой, более актуальной информации.
Подробнее: Алгоритмы кэширования
Таблица виртуальных методов (англ. virtual method table, VMT) — координирующая таблица или vtable — механизм, используемый в языках программирования для поддержки динамического соответствия (или метода позднего связывания).
Сопрограммы (англ. coroutines) — методика связи программных модулей друг с другом по принципу кооперативной многозадачности: модуль приостанавливается в определённой точке, сохраняя полное состояние (включая стек вызовов и счётчик команд), и передаёт управление другому. Тот, в свою очередь, выполняет задачу и передаёт управление обратно, сохраняя свои стек и счётчик.
Подробнее: Сопрограмма
Многопроцессорностью иногда называют выполнение множественных параллельных программных процессов в системе в противоположность выполнению одного процесса в любой момент времени. Однако термины многозадачность или мультипрограммирование являются более подходящими для описания этого понятия, которое осуществлено главным образом в программном обеспечении, тогда как многопроцессорная обработка является более соответствующей, чтобы описать использование множественных аппаратных процессоров. Система не…
Тестирование производительности в инженерии программного обеспечения — тестирование, которое проводится с целью определения, как быстро работает вычислительная система или её часть под определённой нагрузкой. Также может служить для проверки и подтверждения других атрибутов качества системы, таких как масштабируемость, надёжность и потребление ресурсов.
Сравнение с обменом (англ. compare and set, compare and swap, CAS) — атомарная инструкция, сравнивающая значение в памяти с одним из аргументов, и в случае успеха записывающая второй аргумент в память. Поддерживается в семействах процессоров x86, Itanium, Sparc и других.
Модульное тестирование, или юнит-тестирование (англ. unit testing) — процесс в программировании, позволяющий проверить на корректность отдельные модули исходного кода программы, наборы из одного или более программных модулей вместе с соответствующими управляющими данными, процедурами использования и обработки.
Компромисс времени и памяти (англ. Space-time trade-off, «выбор оптимального соотношения „место-время“» (англ. space-time trade-off), или, иначе, «выбор оптимального соотношения „время-память“» (англ. time-memory trade-off)) — компромиссный подход к решению ряда задач в информатике, при котором используется обратное соотношение требуемого объёма памяти и скорости выполнения программы: время вычислений может быть увеличено за счёт уменьшения используемой памяти или, наоборот, снижено за счёт увеличения…
Шифрование, сохраняющее формат (англ. format-preserving encryption, FPE) означает шифрование, в котором выходные данные (шифротекст) находятся в таком же формате, что и входные данные (открытый текст). Значение слова «формат» варьируется. Обычно подразумеваются только конечные множества, например…
Процессор в памяти, Processor-in-memory (PIM), или Вычисляющее ОЗУ или Computational RAM, C-RAM, также, «Вычисления в памяти», называют процессор, тесно интегрированный в память, как правило, на одном кремниевом кристалле, либо оперативную память с интегрированными вычисляющими элементами.
Метод обратного распространения ошибки (англ. backpropagation) — метод вычисления градиента, который используется при обновлении весов многослойного перцептрона. Впервые метод был описан в 1974 г. А. И. Галушкиным, а также независимо и одновременно Полом Дж. Вербосом. Далее существенно развит в 1986 г. Дэвидом И. Румельхартом, Дж. Е. Хинтоном и Рональдом Дж. Вильямсом и независимо и одновременно С.И. Барцевым и В.А. Охониным (Красноярская группа). Это итеративный градиентный алгоритм, который используется…
Операционная система реального времени (ОСРВ, англ. real-time operating system, RTOS) — тип операционной системы, основное назначение которой — предоставление необходимого и достаточного набора функций для работы систем реального времени на конкретном аппаратном оборудовании.
Ансамбль методов в статистике и обучении машин использует несколько обучающих алгоритмов с целью получения лучшей эффективности прогнозирования, чем могли бы получить от каждого обучающего алгоритма по отдельности.
В информатике асинхронный ввод/вывод является формой неблокирующей обработки ввода/вывода, который позволяет процессу продолжить выполнение не дожидаясь окончания передачи данных.
Нейрокриптография — раздел криптографии, изучающий применение стохастических алгоритмов, в частности, нейронных сетей, для шифрования и криптоанализа.
В компьютерной инженерии микроархитектура (англ. microarchitecture; иногда сокращается до µarch или uarch), также называемая организация компьютера — это способ, которым данная архитектура набора команд (ISA, АНК) реализована в процессоре. Каждая АНК может быть реализована с помощью различных микроархитектур.
Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией сложности вычислений. Объём работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Время определяется количеством элементарных шагов, необходимых для решения задачи, тогда как пространство определяется…
Линейное зондирование — это схема в программировании для разрешения коллизий в хеш-таблицах, структурах данных для управления наборами пар ключ – значение и поиска значений, ассоциированных с данным ключом. Схему придумали в 1954 Джин Амдал, Элейн Макгроу и Артур Сэмюэл, а проанализировна она была в 1963 Дональдом Кнутом.
Байесовское программирование — это формальная система и методология определения вероятностных моделей и решения задач, когда не вся необходимая информация является доступной.
Си (англ. C) — компилируемый статически типизированный язык программирования общего назначения, разработанный в 1969—1973 годах сотрудником Bell Labs Деннисом Ритчи как развитие языка Би. Первоначально был разработан для реализации операционной системы UNIX, но впоследствии был перенесён на множество других платформ. Согласно дизайну языка, его конструкции близко сопоставляются типичным машинным инструкциям, благодаря чему он нашёл применение в проектах, для которых был свойственен язык ассемблера…
Параллелизм на уровне команд (англ. Instruction-level parallelism — ILP) является мерой того, какое множество операций в компьютерной программе может выполняться одновременно. Потенциальное совмещение выполнения команд называется «параллелизмом на уровне команд».
Долгая краткосрочная память (англ. Long short-term memory; LSTM) — разновидность архитектуры рекуррентных нейронных сетей, предложенная в 1997 году Сеппом Хохрайтером и Юргеном Шмидхубером. Как и большинство рекуррентных нейронных сетей, LSTM-сеть является универсальной в том смысле, что при достаточном числе элементов сети она может выполнить любое вычисление, на которое способен обычный компьютер, для чего необходима соответствующая матрица весов, которая может рассматриваться как программа. В…
Поиск клонов в исходном коде — анализ исходного кода с помощью различных алгоритмов, с целью обнаружения клонированного кода, который может иметь вредоносный характер.
Переме́нная в императивном программировании — поименованная, либо адресуемая иным способом область памяти, адрес которой можно использовать для осуществления доступа к данным. Данные, находящиеся в переменной (то есть по данному адресу памяти), называются значением этой переменной.
Клэйтро́ника — абстрактная концепция будущего, состоящая в объединении наномасштабных роботов и информатики с целью создания индивидуальных компьютеров атомных размеров, называемых клэйтронными атомами или к-атомами. Они могут вступать в контакт друг с другом и создавать материальные 3-D объекты, с которыми может взаимодействовать пользователь. Эта идея входит в более общую идею создания программируемой материи. Многочисленные исследования и эксперименты с клэйтроникой проводятся группой учёных в…
Обучение с ошибками (англ. Learning with errors) — это концепция машинного обучения, суть которой заключается в том, что в простые вычислительные задачи (например, системы линейных уравнений) намеренно вносится ошибка, делая их решение известными методами неосуществимым за приемлемое время.
Коллаборативная фильтрация, совместная фильтрация (англ. collaborative filtering) — это один из методов построения прогнозов (рекомендаций) в рекомендательных системах, использующий известные предпочтения (оценки) группы пользователей для прогнозирования неизвестных предпочтений другого пользователя. Его основное допущение состоит в следующем: те, кто одинаково оценивали какие-либо предметы в прошлом, склонны давать похожие оценки другим предметам и в будущем. Например, с помощью коллаборативной…
Реентерабельность тесно связана с безопасностью функции в многопоточной среде (thread-safety), тем не менее, это разные понятия. Обеспечение реентерабельности является ключевым моментом при программировании многозадачных систем, в частности, операционных систем.
Векторный процессор — это процессор, в котором операндами некоторых команд могут выступать упорядоченные массивы данных — векторы. Отличается от скалярных процессоров, которые могут работать только с одним операндом в единицу времени. Абсолютное большинство процессоров является скалярными или близкими к ним. Векторные процессоры были распространены в сфере научных вычислений, где они являлись основой большинства суперкомпьютеров начиная с 1980-х до 1990-х. Но резкое увеличение производительности…
В криптографии ‘время атаки (англ. Time attack) — это атака по сторонним каналам, в которой атакующий пытается скомпрометировать криптосистему с помощью анализа времени, затрачиваемого на исполнение криптографических алгоритмов. Каждая логическая операция требует времени на исполнение на компьютере, и это время может различаться в зависимости от входных данных. Располагая точными измерениями времени для разных операций, атакующий может восстановить входные данные.
Подробнее: Атака по времени
Доказательство выполнения работы (англ. Proof-of-work, POW, PoW) — принцип защиты сетевых систем от злоупотребления услугами (например, от DoS-атак или организации рассылок спама), основанный на необходимости выполнения на стороне клиента некоторой достаточно длительной работы (нахождение решения задачи), результат которой легко и быстро проверяется на стороне сервера (см. односторонняя функция). Главная особенность применяемых вычислений заключается в асимметрии затрат времени — они значительны…
В информатике типобезопасность (англ. type safety) языка программирования означает безопасность (или надёжность) его системы типов.
Повторное использование кода (англ. code reuse) — методология проектирования компьютерных и других систем, заключающаяся в том, что система (компьютерная программа, программный модуль) частично либо полностью должна составляться из частей, написанных ранее компонентов и/или частей другой системы, и эти компоненты должны применяться более одного раза (если не в рамках одного проекта, то хотя бы разных). Повторное использование — основная методология, которая применяется для сокращения трудозатрат…
В приведённой ниже таблице отмечено наличие или отсутствие тех или иных возможностей в некоторых популярных сегодня языках программирования. Столбцы упорядочены по алфавиту. Если возможность в языке недоступна напрямую, но может быть эмулирована с помощью других средств, то в таблице отмечено, что её нет.
Подробнее: Сравнение языков программирования
Маскировка (обфускация) данных — это способ защиты конфиденциальной информации от несанкционированного доступа путём замены исходных данных фиктивными данными или произвольными символами. При этом замаскированная информация выглядит реалистично и непротиворечиво и может использоваться в процессе тестирования программного обеспечения. В большинстве случаев маскировка применяется для защиты персональных данных и конфиденциальных сведений организации.
Метод Куайна—Мак-Класки (англ. Quine–McCluskey method) — табличный метод минимизации булевых функций, предложенный Уиллардом Куайном и усовершенствованный Эдвардом Мак-Класки. Представляет собой попытку избавиться от недостатков метода Куайна.
Цифровой водяной знак (ЦВЗ) — технология, созданная для защиты авторских прав мультимедийных файлов. Обычно цифровые водяные знаки невидимы. Однако ЦВЗ могут быть видимыми на изображении или видео. Обычно это информация представляет собой текст или логотип, который идентифицирует автора.
Ту́рбокод — параллельный каскадный блоковый систематический код, способный исправлять ошибки, возникающие при передаче цифровой информации по каналу связи с шумами. Синонимом турбокода является известный в теории кодирования термин — каскадный код (англ. concatenated code) (предложен Д. Форни в 1966 году).
Эффективность алгоритма — Википедия
Эффективность алгоритма — это свойство алгоритма, которое связано с вычислительными ресурсами, используемыми алгоритмом. Алгоритм должен быть проанализирован с целью определения необходимых алгоритму ресурсов. Эффективность алгоритма можно рассматривать как аналог производственной производительности повторяющихся или непрерывных процессов.
Для достижения максимальной эффективности мы желаем уменьшить использование ресурсов. Однако различные ресурсы (такие как время и память) нельзя сравнить напрямую, так что какой из двух алгоритмов считать более эффективным часто зависит от того, какой фактор более важен, например, требование высокой скорости, минимального использования памяти или другой меры эффективности.
- Заметим, что данная статья НЕ об оптимизации алгоритма, которая обсуждается в статьях оптимизация программы, оптимизирующий компилятор, оптимизация циклов[en], оптимизатор объектного кода[en], и так далее. Термин «оптимизация» сам по себе вводит в заблуждение, поскольку всё, что может быть сделано, попадает под определение «улучшение».
История вопроса
Важность эффективности с упором на время исполнения подчёркивала Ада Лавлейс в 1843 по поводу механической аналитической машины Чарлза Бэббиджа:
«Почти во всех вычислениях возможен большой выбор конфигураций для успешного завершения процесса и различные соглашения должны влиять на выбор с целью выполнения вычислений. Существенная вещь — выбор конфигурации, которая приведёт к минимизации времени, необходимого для выполнения вычисления»[1].
Ранние электронные компьютеры были очень ограничены как по скорости, так и по памяти. В некоторых случаях было осознано, что существует компромисс времени и памяти, при котором задача должна либо использовать большое количество памяти для достижения высокой скорости, либо использовать более медленный алгоритм, использующий небольшое количество рабочей памяти. В этом случае использовался наиболее быстрый алгоритм, для которого было достаточно имеющейся памяти.
Современные компьютеры много быстрее тех ранних компьютеров и имеют много больше памяти (гигабайты вместо килобайт). Тем не менее, Дональд Кнут подчёркивает, что эффективность остаётся важным фактором:
«В установившихся технических дисциплинах улучшение на 12 % легко достижимо, никогда не считалось запредельным и я верю, что то же самое должно быть в программировании» [2]
Обзор
Алгоритм считается эффективным, если потребляемый им ресурс (или стоимость ресурса) на уровне или ниже некоторого приемлемого уровня. Грубо говоря, «приемлемый» здесь означает «алгоритм будет работать умеренное время на доступном компьютере». Поскольку с 1950-х годов наблюдалось значительное увеличение вычислительной мощности и доступной памяти компьютеров, существующий «приемлемый уровень» не был приемлемым даже 10 лет назад.
Производители компьютеров периодично выпускают новые модели, зачастую более мощные. Стоимость программного обеспечения может быть достаточно велика, так что в некоторых случаях проще и дешевле для достижения лучшей производительности купить более быстрый компьютер, обеспечивающий совместимость с существующим компьютером.
Существует много путей измерения используемых алгоритмом ресурсов. Два наиболее используемых измерения — скорость и используемая память. Другие измерения могут включать скорость передачи, временное использование диска, долговременное использование диска, потребление энергии, совокупная стоимость владения, время отклика на внешние сигналы и так далее. Многие из этих измерений зависят от размера входных данных алгоритма (то есть от количеств, требующих обработки данных). Измерения могут также зависеть от способа, в котором данные представлены (например, некоторые алгоритмы сортировки плохо работают на уже сортированных данных или когда данные отсортированы в обратном порядке).
На практике существуют и другие факторы, влияющие на эффективность алгоритма, такие как требуемая точность и/или надёжность. Как объяснено ниже, способ реализации алгоритма может также дать существенный эффект на фактическую эффективность, хотя многие аспекты реализации относятся к вопросам оптимизации.
Теоретический анализ
В теоретическом анализе алгоритмов обычной практикой является оценка сложности алгоритма в его асимптотическом поведении, то есть для отражения сложности алгоритма как функции от размера входа n используется нотация «O» большое. Эта оценка, в основном, достаточно точна при большом n, но может привести к неправильным выводам при малых значениях n (так, сортировка пузырьком, считающаяся медленной, может оказаться быстрее «быстрой сортировки», если нужно отсортировать лишь несколько элементов).
Некоторые примеры нотации «O» большое:
| Обозначение | Название | Примеры |
|---|---|---|
| O(1){\displaystyle O(1)\,} | постоянное | Определение, чётно или нечётно число. Использование таблицы поиска постоянного размера. Использование подходящей хэш-функции для выбора элемента. |
| O(logn){\displaystyle O(\log n)\,} | логарифмическое | Нахождение элемента в отсортированном массиве с помощью двоичного поиска или сбалансированного дерева, как и операции в биномиальной куче. |
| O(n){\displaystyle O(n)\,} | линейное | Поиск элемента в несортированном списке или несбалансированном дереве (худший случай). Сложение двух n-битных чисел с использованием сквозного переноса. |
| O(nlogn){\displaystyle O(n\log n)\,} | квазилинейное, логарифмически линейное | Вычисление быстрого преобразования Фурье, пирамидальная сортировка, быстрая сортировка (лучший и средний случай), сортировка слиянием |
| O(n2){\displaystyle O(n^{2})\,} | квадратное | Умножение двух n-значных чисел с помощью простого алгоритма, сортировка пузырьком (худший случай), сортировка Шелла, быстрая сортировка (худший случай), сортировка выбором, сортировка вставками |
| O(cn),c>1{\displaystyle O(c^{n}),\;c>1} | экспоненциальное | Нахождение (точного) решения задачи коммивояжёра с помощью динамического программирования. Определение, не являются ли два логических утверждения эквивалентными с помощью полного перебора |
Проверочные испытания: измерение производительности
Для новых версий программного обеспечения или для обеспечения сравнения с соперничающими системами иногда используются тесты, позволяющие сравнить относительную производительность алгоритмов. Если, например, выпускается новый алгоритм сортировки, его можно сравнить с предшественниками, чтобы убедиться, что алгоритм по меньшей мере столь же эффективен на известных данных, как и другие. Тесты производительности могут быть использованы пользователями для сравнения продуктов от различных производителей для оценки, какой продукт будет больше подходить под их требования в терминах функциональности и производительности.
Некоторые тесты производительности дают возможность проведения сравнительного анализа различных компилирующих и интерпретирующих языков, как, например, Roy Longbottom’s PC Benchmark Collection[3], а The Computer Language Benchmarks Game[en] сравнивает производительность реализаций типичных задач в некоторых языках программирования.
(Достаточно легко создать «самодельные» тесты производительности для получения представления об относительной эффективности различных языков программирования, используя набор пользовательских критериев, как это сделал Христофер Коувел-Шах в статье «Nine language Performance roundup»)[4]
Вопросы реализации
Вопросы реализации могут также повлиять на фактическую эффективность. Это касается выбора языка программирования и способа, каким алгоритм фактически закодирован, выбора транслятора для выбранного языка или используемых опций компилятора, и даже используемой операционной системы. В некоторых случаях язык, реализованный в виде интерпретатора, может оказаться существенно медленнее, чем язык, реализованный в виде компилятора[5].
Есть и другие факторы, которые могут повлиять на время или используемую память, но которые оказываются вне контроля программиста. Сюда попадают выравнивание данных, детализация[en], сборка мусора, параллелизм на уровне команд и вызов подпрограмм[6].
Некоторые процессоры имеют способность выполнять векторные операции, что позволяет одной операцией обработать несколько операндов. Может оказаться просто или непросто использовать такие возможности на уровне программирования или компиляции. Алгоритмы, разработанные для последовательных вычислений, могут потребовать полной переработки для использования параллельных вычислений.
Другая проблема может возникнуть с совместимостью процессоров, в которых команды могут быть реализованы по другому, так что команды на одних моделях могут быть относительно более медленными на других моделях. Это может оказаться проблемой для оптимизирующего компилятора.
Измерение использования ресурсов
Измерения обычно выражаются как функция от размера входа n.
Два наиболее важных измерения:
- Время: как долго алгоритм занимает процессор.
- Память: как много рабочей памяти (обычно RAM) нужно для алгоритма. Здесь есть два аспекта: количество памяти для кода и количество памяти для данных, с которыми код работает.
Для компьютеров, питающихся от батарей (например, лэптопов) или для очень длинных/больших вычислений (например, на суперкомпьютерах), представляют интерес измерения другого рода:
- Прямое потребление энергии: энергия, необходимая для работы компьютера.
- Косвенное потребление энергии: энергия, необходимая для охлаждения, освещения, и т. п.
В некоторых случаях нужны другие, менее распространённые измерения:
- Размер передачи: пропускная способность канала может оказаться ограничивающим фактором. Для уменьшения количества передаваемых данных можно использовать сжатие. Отображение рисунка или изображения (как, например, Google logo) может привести к передаче десятков тысяч байт (48K в данном случае). Сравните это с передачей шести байт в слове «Google».
- Внешняя память: память, необходимая на диске или другом устройстве внешней памяти. Эта память может использоваться для временного хранения или для будущего использования.
- Время отклика: параметр особенно важен для приложений, работающих в реальном времени, когда компьютер должен отвечать быстро на внешние события.
- Общая стоимость владения: параметр важен, когда предназначен для выполнения одного алгоритма.
Время
Теория
Для анализа алгоритма обычно используется анализ временно́й сложности алгоритма, чтобы оценить время работы как функцию от размера входных данных. Результат обычно выражается в терминах «O» большое. Это полезно для сравнения алгоритмов, особенно в случае обработки большого количества данных. Более детальные оценки нужны для сравнения алгоритмов, когда объём данных мал (хотя такая ситуация вряд ли вызовет проблемы). Алгоритмы, которые включают параллельные вычисления, могут оказаться для анализа более трудными.
Практика
Используются сравнительные тесты времени работы алгоритма. Многие языки программирования содержат функции, отражающие время использования процессора. Для долго работающих алгоритмов затраченное время также может представлять интерес. Результаты в общем случае нужно усреднять по серии тестов.
Этот вид тестов может быть очень чувствителен к конфигурации «железа» и возможности работы других программ в то же самое время в мультипроцессорной и мультизадачной среде.
Этот вид тестов существенно зависит также от выбора языка программирования, компилятора и его опций, так что сравниваемые алгоритмы должны быть реализованы в одинаковых условиях.
Память
Этот раздел касается использования основной памяти (зачастую, RAM) нужной алгоритму. Как и для временно́го анализа выше, для анализа алгоритма обычно используется анализ пространственной сложности алгоритма[en], чтобы оценить необходимую память времени исполнения как функцию от размера входа. Результат обычно выражается в терминах «O» большое.
Существует четыре аспекта использования памяти:
- Количество памяти, необходимой для хранения кода алгоритма.
- Количество памяти, необходимое для входных данных.
- Количество памяти, необходимое для любых выходных данных (некоторые алгоритмы, такие как сортировки, часто переставляют входные данные и не требуют дополнительной памяти для выходных данных).
- Количество памяти, необходимое для вычислительного процесса во время вычислений (сюда входят именованные переменные и любое стековое пространство, необходимое для вызова подпрограмм, которое может быть существенным при использовании рекурсии).
Ранние электронные компьютеры и домашние компьютеры имели относительно малый объём рабочей памяти. Так, в 1949 EDSAC имел максимальную рабочую память 1024 17-битных слов, а в 1980 Sinclair ZX80 выпускался с 1024 байтами рабочей памяти.
Современные компьютеры могут иметь относительно большое количество памяти (возможно, гигабайты), так что сжатие используемой алгоритмом памяти в некоторое заданное количество памяти требуется меньше, чем ранее. Однако существование трёх различных категорий памяти существенно:
- Кэш (часто, статическая RAM) — работает на скоростях, сравнимых с ЦПУ
- Основная физическая память (часто, динамическая RAM) — работает чуть медленнее ЦПУ
- Виртуальная память (зачастую, на диске) — даёт иллюзию огромной памяти, но работает в тысячи раз медленнее RAM.
Алгоритм, необходимая память которого укладывается в кэш компьютера, работает много быстрее, чем алгоритм, умещающийся в основную память, который, в свою очередь, будет много быстрее алгоритма, который использует виртуальное пространство. Усложняет ситуацию факт, что некоторые системы имеют до трёх уровней кэша. Различные системы имеют различное количество этих типов памяти, так что эффект памяти для алгоритма может существенно отличаться при переходе от одной системы к другой.
В ранние дни электронных вычислений, если алгоритм и его данные не помещались в основную память, он не мог использоваться. В наши дни использование виртуальной памяти обеспечивает огромную память, но за счёт производительности. Если алгоритм и его данные умещаются в кэш, можно получить очень высокую скорость, так что минимизация требуемой памяти помогает минимизировать время. Алгоритм, который не помещается полностью в кэш, но обеспечивает локальность ссылок[en], может работать сравнительно быстро.
Примеры эффективных алгоритмов
Критика текущего состояния программирования
Программы становятся медленнее более стремительно, чем компьютеры становятся быстрее.
- Мэй утверждает:
В широко распространённых системах уменьшение вдвое выполнение команд может удвоить жизнь батареи, а большие данные дают возможность для лучших алгоритмов: Уменьшение числа операций с 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» (Автостопом по галактике)[8]). Он оценил падение производительности на 70 dB, или на «99.99999 % от возможного», по сравнению с 1980-ми годами — «когда Артур Кларк сравнил вычислительные способности компьютеров 2001 с компьютером HAL в книге 2001: A Space Odyssey, он указал, что удивительно малы и мощны были компьютеры, но программы стали печально разочаровывающими».
Соревнования за лучший алгоритм
Следующие соревнования приглашают принять участие в разработке лучших алгоритмов, критерий качества которых определяют судьи:
См. также
- Анализ алгоритмов
- Арифметическое кодирование — вид энтропийного кодирования с переменной длиной кода[en] для эффективного сжатия данных
- Ассоциативный массив — структура данных, которую можно сделать более эффективной при применении деревьев PATRICIA[en] или массивов Джуди[en]
- Тест производительности — метод измерения сравнительного времени исполнения в определённых случаях
- Наилучший, наихудший и средний случай[en] — соглашения по оценке времени выполнения по трём сценариям
- Двоичный поиск — простая и эффективная техника поиска в отсортированном списке
- Таблица ветвления[en] — техника сокращения длины команд, размера машинного кода, и зачастую, памяти
- Оптимизирующий компилятор — компилятор, использующий различные методы получения более оптимального программного кода при сохранении функциональных возможностей
- Вычислительная сложность математических операций[en]
- Вычислительная сложность — понятие в информатике, обозначающее зависимости объёма работы от размера входных данных
- Вычислительная мощность компьютера — количественная характеристика скорости выполнения операций на компьютере
- Сжатие данных — сокращение объёма передачи данных и занимаемого дискового пространства
- Индекс — данные, увеличивающие скорость выборки данных из таблиц
- Энтропийное кодирование — кодирование последовательности значений с возможностью однозначного восстановления с целью уменьшения объёма данных (длины последовательности) с помощью усреднения вероятностей появления элементов в закодированной последовательности
- Сборка мусора — автоматическое освобождение памяти после использования
- Зелёные информационные технологии[en] — движение за внедрение «зелёных» технологий, потребляющих меньше ресурсов
- Код Хаффмана — алгоритм эффективного кодирования данных
- Improving Managed code Performance — Microsoft MSDN Library
- Локальность ссылок[en] — во избежание задержек, вызванных кэшированием из-за нелокального доступа к памяти
- Оптимизация циклов[en]
- Управление паматью
- Оптимизация (информатика)
- Анализ производительности — методы измерения фактической производительности алгоритма в реальном времени
- Вычисления в реальном времени — пример критичных по времени приложений
- Динамический анализ[en] — оценка ожидаемого времени работы и расщепляемость алгоритма
- Одновременная многопоточность
- Упреждающее исполнение[en], когда вычисления проводятся, даже если ещё неизвестно, понадобятся ли их результаты, или немедленное вычисление[en] как противоположность ленивым вычислениям
- Временна́я многопоточность
- Шитый код — один из способов реализации промежуточной виртуальной машины при интерпретации языков программирования (наряду с байт-кодом)
- Таблица виртуальных методов — механизм поддержки динамического соответствия (или метода позднего связывания)
Примечания
Литература
Ссылки
Эффективность алгоритма — Википедия
Эффективность алгоритма — это свойство алгоритма, которое связано с вычислительными ресурсами, используемыми алгоритмом. Алгоритм должен быть проанализирован с целью определения необходимых алгоритму ресурсов. Эффективность алгоритма можно рассматривать как аналог производственной производительности повторяющихся или непрерывных процессов.
Для достижения максимальной эффективности мы желаем уменьшить использование ресурсов. Однако различные ресурсы (такие как время и память) нельзя сравнить напрямую, так что какой из двух алгоритмов считать более эффективным часто зависит от того, какой фактор более важен, например, требование высокой скорости, минимального использования памяти или другой меры эффективности.
- Заметим, что данная статья НЕ об оптимизации алгоритма, которая обсуждается в статьях оптимизация программы, оптимизирующий компилятор, оптимизация циклов[en], оптимизатор объектного кода[en], и так далее. Термин «оптимизация» сам по себе вводит в заблуждение, поскольку всё, что может быть сделано, попадает под определение «улучшение».
История вопроса
Важность эффективности с упором на время исполнения подчёркивала Ада Лавлейс в 1843 по поводу механической аналитической машины Чарлза Бэббиджа:
«Почти во всех вычислениях возможен большой выбор конфигураций для успешного завершения процесса и различные соглашения должны влиять на выбор с целью выполнения вычислений. Существенная вещь — выбор конфигурации, которая приведёт к минимизации времени, необходимого для выполнения вычисления»[1].
Ранние электронные компьютеры были очень ограничены как по скорости, так и по памяти. В некоторых случаях было осознано, что существует компромисс времени и памяти, при котором задача должна либо использовать большое количество памяти для достижения высокой скорости, либо использовать более медленный алгоритм, использующий небольшое количество рабочей памяти. В этом случае использовался наиболее быстрый алгоритм, для которого было достаточно имеющейся памяти.
Современные компьютеры много быстрее тех ранних компьютеров и имеют много больше памяти (гигабайты вместо килобайт). Тем не менее, Дональд Кнут подчёркивает, что эффективность остаётся важным фактором:
«В установившихся технических дисциплинах улучшение на 12 % легко достижимо, никогда не считалось запредельным и я верю, что то же самое должно быть в программировании» [2]
Обзор
Алгоритм считается эффективным, если потребляемый им ресурс (или стоимость ресурса) на уровне или ниже некоторого приемлемого уровня. Грубо говоря, «приемлемый» здесь означает «алгоритм будет работать умеренное время на доступном компьютере». Поскольку с 1950-х годов наблюдалось значительное увеличение вычислительной мощности и доступной памяти компьютеров, существующий «приемлемый уровень» не был приемлемым даже 10 лет назад.
Производители компьютеров периодично выпускают новые модели, зачастую более мощные. Стоимость программного обеспечения может быть достаточно велика, так что в некоторых случаях проще и дешевле для достижения лучшей производительности купить более быстрый компьютер, обеспечивающий совместимость с существующим компьютером.
Существует много путей измерения используемых алгоритмом ресурсов. Два наиболее используемых измерения — скорость и используемая память. Другие измерения могут включать скорость передачи, временное использование диска, долговременное использование диска, потребление энергии, совокупная стоимость владения, время отклика на внешние сигналы и так далее. Многие из этих измерений зависят от размера входных данных алгоритма (то есть от количеств, требующих обработки данных). Измерения могут также зависеть от способа, в котором данные представлены (например, некоторые алгоритмы сортировки плохо работают на уже сортированных данных или когда данные отсортированы в обратном порядке).
На практике существуют и другие факторы, влияющие на эффективность алгоритма, такие как требуемая точность и/или надёжность. Как объяснено ниже, способ реализации алгоритма может также дать существенный эффект на фактическую эффективность, хотя многие аспекты реализации относятся к вопросам оптимизации.
Теоретический анализ
В теоретическом анализе алгоритмов обычной практикой является оценка сложности алгоритма в его асимптотическом поведении, то есть для отражения сложности алгоритма как функции от размера входа n используется нотация «O» большое. Эта оценка, в основном, достаточно точна при большом n, но может привести к неправильным выводам при малых значениях n (так, сортировка пузырьком, считающаяся медленной, может оказаться быстрее «быстрой сортировки», если нужно отсортировать лишь несколько элементов).
Некоторые примеры нотации «O» большое:
| Обозначение | Название | Примеры |
|---|---|---|
| O(1){\displaystyle O(1)\,} | постоянное | Определение, чётно или нечётно число. Использование таблицы поиска постоянного размера. Использование подходящей хэш-функции для выбора элемента. |
| O(logn){\displaystyle O(\log n)\,} | логарифмическое | Нахождение элемента в отсортированном массиве с помощью двоичного поиска или сбалансированного дерева, как и операции в биномиальной куче. |
| O(n){\displaystyle O(n)\,} | линейное | Поиск элемента в несортированном списке или несбалансированном дереве (худший случай). Сложение двух n-битных чисел с использованием сквозного переноса. |
| O(nlogn){\displaystyle O(n\log n)\,} | квазилинейное, логарифмически линейное | Вычисление быстрого преобразования Фурье, пирамидальная сортировка, быстрая сортировка (лучший и средний случай), сортировка слиянием |
| O(n2){\displaystyle O(n^{2})\,} | квадратное | Умножение двух n-значных чисел с помощью простого алгоритма, сортировка пузырьком (худший случай), сортировка Шелла, быстрая сортировка (худший случай), сортировка выбором, сортировка вставками |
| O(cn),c>1{\displaystyle O(c^{n}),\;c>1} | экспоненциальное | Нахождение (точного) решения задачи коммивояжёра с помощью динамического программирования. Определение, не являются ли два логических утверждения эквивалентными с помощью полного перебора |
Проверочные испытания: измерение производительности
Для новых версий программного обеспечения или для обеспечения сравнения с соперничающими системами иногда используются тесты, позволяющие сравнить относительную производительность алгоритмов. Если, например, выпускается новый алгоритм сортировки, его можно сравнить с предшественниками, чтобы убедиться, что алгоритм по меньшей мере столь же эффективен на известных данных, как и другие. Тесты производительности могут быть использованы пользователями для сравнения продуктов от различных производителей для оценки, какой продукт будет больше подходить под их требования в терминах функциональности и производительности.
Некоторые тесты производительности дают возможность проведения сравнительного анализа различных компилирующих и интерпретирующих языков, как, например, Roy Longbottom’s PC Benchmark Collection[3], а The Computer Language Benchmarks Game[en] сравнивает производительность реализаций типичных задач в некоторых языках программирования.
(Достаточно легко создать «самодельные» тесты производительности для получения представления об относительной эффективности различных языков программирования, используя набор пользовательских критериев, как это сделал Христофер Коувел-Шах в статье «Nine language Performance roundup»)[4]
Вопросы реализации
Вопросы реализации могут также повлиять на фактическую эффективность. Это касается выбора языка программирования и способа, каким алгоритм фактически закодирован, выбора транслятора для выбранного языка или используемых опций компилятора, и даже используемой операционной системы. В некоторых случаях язык, реализованный в виде интерпретатора, может оказаться существенно медленнее, чем язык, реализованный в виде компилятора[5].
Есть и другие факторы, которые могут повлиять на время или используемую память, но которые оказываются вне контроля программиста. Сюда попадают выравнивание данных, детализация[en], сборка мусора, параллелизм на уровне команд и вызов подпрограмм[6].
Некоторые процессоры имеют способность выполнять векторные операции, что позволяет одной операцией обработать несколько операндов. Может оказаться просто или непросто использовать такие возможности на уровне программирования или компиляции. Алгоритмы, разработанные для последовательных вычислений, могут потребовать полной переработки для использования параллельных вычислений.
Другая проблема может возникнуть с совместимостью процессоров, в которых команды могут быть реализованы по другому, так что команды на одних моделях могут быть относительно более медленными на других моделях. Это может оказаться проблемой для оптимизирующего компилятора.
Измерение использования ресурсов
Измерения обычно выражаются как функция от размера входа n.
Два наиболее важных измерения:
- Время: как долго алгоритм занимает процессор.
- Память: как много рабочей памяти (обычно RAM) нужно для алгоритма. Здесь есть два аспекта: количество памяти для кода и количество памяти для данных, с которыми код работает.
Для компьютеров, питающихся от батарей (например, лэптопов) или для очень длинных/больших вычислений (например, на суперкомпьютерах), представляют интерес измерения другого рода:
- Прямое потребление энергии: энергия, необходимая для работы компьютера.
- Косвенное потребление энергии: энергия, необходимая для охлаждения, освещения, и т. п.
В некоторых случаях нужны другие, менее распространённые измерения:
- Размер передачи: пропускная способность канала может оказаться ограничивающим фактором. Для уменьшения количества передаваемых данных можно использовать сжатие. Отображение рисунка или изображения (как, например, Google logo) может привести к передаче десятков тысяч байт (48K в данном случае). Сравните это с передачей шести байт в слове «Google».
- Внешняя память: память, необходимая на диске или другом устройстве внешней памяти. Эта память может использоваться для временного хранения или для будущего использования.
- Время отклика: параметр особенно важен для приложений, работающих в реальном времени, когда компьютер должен отвечать быстро на внешние события.
- Общая стоимость владения: параметр важен, когда предназначен для выполнения одного алгоритма.
Время
Теория
Для анализа алгоритма обычно используется анализ временно́й сложности алгоритма, чтобы оценить время работы как функцию от размера входных данных. Результат обычно выражается в терминах «O» большое. Это полезно для сравнения алгоритмов, особенно в случае обработки большого количества данных. Более детальные оценки нужны для сравнения алгоритмов, когда объём данных мал (хотя такая ситуация вряд ли вызовет проблемы). Алгоритмы, которые включают параллельные вычисления, могут оказаться для анализа более трудными.
Практика
Используются сравнительные тесты времени работы алгоритма. Многие языки программирования содержат функции, отражающие время использования процессора. Для долго работающих алгоритмов затраченное время также может представлять интерес. Результаты в общем случае нужно усреднять по серии тестов.
Этот вид тестов может быть очень чувствителен к конфигурации «железа» и возможности работы других программ в то же самое время в мультипроцессорной и мультизадачной среде.
Этот вид тестов существенно зависит также от выбора языка программирования, компилятора и его опций, так что сравниваемые алгоритмы должны быть реализованы в одинаковых условиях.
Память
Этот раздел касается использования основной памяти (зачастую, RAM) нужной алгоритму. Как и для временно́го анализа выше, для анализа алгоритма обычно используется анализ пространственной сложности алгоритма[en], чтобы оценить необходимую память времени исполнения как функцию от размера входа. Результат обычно выражается в терминах «O» большое.
Существует четыре аспекта использования памяти:
- Количество памяти, необходимой для хранения кода алгоритма.
- Количество памяти, необходимое для входных данных.
- Количество памяти, необходимое для любых выходных данных (некоторые алгоритмы, такие как сортировки, часто переставляют входные данные и не требуют дополнительной памяти для выходных данных).
- Количество памяти, необходимое для вычислительного процесса во время вычислений (сюда входят именованные переменные и любое стековое пространство, необходимое для вызова подпрограмм, которое может быть существенным при использовании рекурсии).
Ранние электронные компьютеры и домашние компьютеры имели относительно малый объём рабочей памяти. Так, в 1949 EDSAC имел максимальную рабочую память 1024 17-битных слов, а в 1980 Sinclair ZX80 выпускался с 1024 байтами рабочей памяти.
Современные компьютеры могут иметь относительно большое количество памяти (возможно, гигабайты), так что сжатие используемой алгоритмом памяти в некоторое заданное количество памяти требуется меньше, чем ранее. Однако существование трёх различных категорий памяти существенно:
- Кэш (часто, статическая RAM) — работает на скоростях, сравнимых с ЦПУ
- Основная физическая память (часто, динамическая RAM) — работает чуть медленнее ЦПУ
- Виртуальная память (зачастую, на диске) — даёт иллюзию огромной памяти, но работает в тысячи раз медленнее RAM.
Алгоритм, необходимая память которого укладывается в кэш компьютера, работает много быстрее, чем алгоритм, умещающийся в основную память, который, в свою очередь, будет много быстрее алгоритма, который использует виртуальное пространство. Усложняет ситуацию факт, что некоторые системы имеют до трёх уровней кэша. Различные системы имеют различное количество этих типов памяти, так что эффект памяти для алгоритма может существенно отличаться при переходе от одной системы к другой.
В ранние дни электронных вычислений, если алгоритм и его данные не помещались в основную память, он не мог использоваться. В наши дни использование виртуальной памяти обеспечивает огромную память, но за счёт производительности. Если алгоритм и его данные умещаются в кэш, можно получить очень высокую скорость, так что минимизация требуемой памяти помогает минимизировать время. Алгоритм, который не помещается полностью в кэш, но обеспечивает локальность ссылок[en], может работать сравнительно быстро.
Примеры эффективных алгоритмов
Критика текущего состояния программирования
Программы становятся медленнее более стремительно, чем компьютеры становятся быстрее.
- Мэй утверждает:
В широко распространённых системах уменьшение вдвое выполнение команд может удвоить жизнь батареи, а большие данные дают возможность для лучших алгоритмов: Уменьшение числа операций с 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» (Автостопом по галактике)[8]). Он оценил падение производительности на 70 dB, или на «99.99999 % от возможного», по сравнению с 1980-ми годами — «когда Артур Кларк сравнил вычислительные способности компьютеров 2001 с компьютером HAL в книге 2001: A Space Odyssey, он указал, что удивительно малы и мощны были компьютеры, но программы стали печально разочаровывающими».
Соревнования за лучший алгоритм
Следующие соревнования приглашают принять участие в разработке лучших алгоритмов, критерий качества которых определяют судьи:
См. также
- Анализ алгоритмов
- Арифметическое кодирование — вид энтропийного кодирования с переменной длиной кода[en] для эффективного сжатия данных
- Ассоциативный массив — структура данных, которую можно сделать более эффективной при применении деревьев PATRICIA[en] или массивов Джуди[en]
- Тест производительности — метод измерения сравнительного времени исполнения в определённых случаях
- Наилучший, наихудший и средний случай[en] — соглашения по оценке времени выполнения по трём сценариям
- Двоичный поиск — простая и эффективная техника поиска в отсортированном списке
- Таблица ветвления[en] — техника сокращения длины команд, размера машинного кода, и зачастую, памяти
- Оптимизирующий компилятор — компилятор, использующий различные методы получения более оптимального программного кода при сохранении функциональных возможностей
- Вычислительная сложность математических операций[en]
- Вычислительная сложность — понятие в информатике, обозначающее зависимости объёма работы от размера входных данных
- Вычислительная мощность компьютера — количественная характеристика скорости выполнения операций на компьютере
- Сжатие данных — сокращение объёма передачи данных и занимаемого дискового пространства
- Индекс — данные, увеличивающие скорость выборки данных из таблиц
- Энтропийное кодирование — кодирование последовательности значений с возможностью однозначного восстановления с целью уменьшения объёма данных (длины последовательности) с помощью усреднения вероятностей появления элементов в закодированной последовательности
- Сборка мусора — автоматическое освобождение памяти после использования
- Зелёные информационные технологии[en] — движение за внедрение «зелёных» технологий, потребляющих меньше ресурсов
- Код Хаффмана — алгоритм эффективного кодирования данных
- Improving Managed code Performance — Microsoft MSDN Library
- Локальность ссылок[en] — во избежание задержек, вызванных кэшированием из-за нелокального доступа к памяти
- Оптимизация циклов[en]
- Управление паматью
- Оптимизация (информатика)
- Анализ производительности — методы измерения фактической производительности алгоритма в реальном времени
- Вычисления в реальном времени — пример критичных по времени приложений
- Динамический анализ[en] — оценка ожидаемого времени работы и расщепляемость алгоритма
- Одновременная многопоточность
- Упреждающее исполнение[en], когда вычисления проводятся, даже если ещё неизвестно, понадобятся ли их результаты, или немедленное вычисление[en] как противоположность ленивым вычислениям
- Временна́я многопоточность
- Шитый код — один из способов реализации промежуточной виртуальной машины при интерпретации языков программирования (наряду с байт-кодом)
- Таблица виртуальных методов — механизм поддержки динамического соответствия (или метода позднего связывания)
Примечания
Литература
Ссылки
Эффективность алгоритма — Википедия. Что такое Эффективность алгоритма
Эффективность алгоритма — это свойство алгоритма, которое связано с вычислительными ресурсами, используемыми алгоритмом. Алгоритм должен быть проанализирован с целью определения необходимых алгоритму ресурсов. Эффективность алгоритма можно рассматривать как аналог производственной производительности повторяющихся или непрерывных процессов.
Для достижения максимальной эффективности мы желаем уменьшить использование ресурсов. Однако различные ресурсы (такие как время и память) нельзя сравнить напрямую, так что какой из двух алгоритмов считать более эффективным часто зависит от того, какой фактор более важен, например, требование высокой скорости, минимального использования памяти или другой меры эффективности.
- Заметим, что данная статья НЕ об оптимизации алгоритма, которая обсуждается в статьях оптимизация программы, оптимизирующий компилятор, оптимизация циклов[en], оптимизатор объектного кода[en], и так далее. Термин «оптимизация» сам по себе вводит в заблуждение, поскольку всё, что может быть сделано, попадает под определение «улучшение».
История вопроса
Важность эффективности с упором на время исполнения подчёркивала Ада Лавлейс в 1843 по поводу механической аналитической машины Чарлза Бэббиджа:
«Почти во всех вычислениях возможен большой выбор конфигураций для успешного завершения процесса и различные соглашения должны влиять на выбор с целью выполнения вычислений. Существенная вещь — выбор конфигурации, которая приведёт к минимизации времени, необходимого для выполнения вычисления»[1].
Ранние электронные компьютеры были очень ограничены как по скорости, так и по памяти. В некоторых случаях было осознано, что существует компромисс времени и памяти, при котором задача должна либо использовать большое количество памяти для достижения высокой скорости, либо использовать более медленный алгоритм, использующий небольшое количество рабочей памяти. В этом случае использовался наиболее быстрый алгоритм, для которого было достаточно имеющейся памяти.
Современные компьютеры много быстрее тех ранних компьютеров и имеют много больше памяти (гигабайты вместо килобайт). Тем не менее, Дональд Кнут подчёркивает, что эффективность остаётся важным фактором:
«В установившихся технических дисциплинах улучшение на 12 % легко достижимо, никогда не считалось запредельным и я верю, что то же самое должно быть в программировании» [2]
Обзор
Алгоритм считается эффективным, если потребляемый им ресурс (или стоимость ресурса) на уровне или ниже некоторого приемлемого уровня. Грубо говоря, «приемлемый» здесь означает «алгоритм будет работать умеренное время на доступном компьютере». Поскольку с 1950-х годов наблюдалось значительное увеличение вычислительной мощности и доступной памяти компьютеров, существующий «приемлемый уровень» не был приемлемым даже 10 лет назад.
Производители компьютеров периодично выпускают новые модели, зачастую более мощные. Стоимость программного обеспечения может быть достаточно велика, так что в некоторых случаях проще и дешевле для достижения лучшей производительности купить более быстрый компьютер, обеспечивающий совместимость с существующим компьютером.
Существует много путей измерения используемых алгоритмом ресурсов. Два наиболее используемых измерения — скорость и используемая память. Другие измерения могут включать скорость передачи, временное использование диска, долговременное использование диска, потребление энергии, совокупная стоимость владения, время отклика на внешние сигналы и так далее. Многие из этих измерений зависят от размера входных данных алгоритма (то есть от количеств, требующих обработки данных). Измерения могут также зависеть от способа, в котором данные представлены (например, некоторые алгоритмы сортировки плохо работают на уже сортированных данных или когда данные отсортированы в обратном порядке).
На практике существуют и другие факторы, влияющие на эффективность алгоритма, такие как требуемая точность и/или надёжность. Как объяснено ниже, способ реализации алгоритма может также дать существенный эффект на фактическую эффективность, хотя многие аспекты реализации относятся к вопросам оптимизации.
Теоретический анализ
В теоретическом анализе алгоритмов обычной практикой является оценка сложности алгоритма в его асимптотическом поведении, то есть для отражения сложности алгоритма как функции от размера входа n используется нотация «O» большое. Эта оценка, в основном, достаточно точна при большом n, но может привести к неправильным выводам при малых значениях n (так, сортировка пузырьком, считающаяся медленной, может оказаться быстрее «быстрой сортировки», если нужно отсортировать лишь несколько элементов).
Некоторые примеры нотации «O» большое:
| Обозначение | Название | Примеры |
|---|---|---|
| O(1){\displaystyle O(1)\,} | постоянное | Определение, чётно или нечётно число. Использование таблицы поиска постоянного размера. Использование подходящей хэш-функции для выбора элемента. |
| O(logn){\displaystyle O(\log n)\,} | логарифмическое | Нахождение элемента в отсортированном массиве с помощью двоичного поиска или сбалансированного дерева, как и операции в биномиальной куче. |
| O(n){\displaystyle O(n)\,} | линейное | Поиск элемента в несортированном списке или несбалансированном дереве (худший случай). Сложение двух n-битных чисел с использованием сквозного переноса. |
| O(nlogn){\displaystyle O(n\log n)\,} | квазилинейное, логарифмически линейное | Вычисление быстрого преобразования Фурье, пирамидальная сортировка, быстрая сортировка (лучший и средний случай), сортировка слиянием |
| O(n2){\displaystyle O(n^{2})\,} | квадратное | Умножение двух n-значных чисел с помощью простого алгоритма, сортировка пузырьком (худший случай), сортировка Шелла, быстрая сортировка (худший случай), сортировка выбором, сортировка вставками |
| O(cn),c>1{\displaystyle O(c^{n}),\;c>1} | экспоненциальное | Нахождение (точного) решения задачи коммивояжёра с помощью динамического программирования. Определение, не являются ли два логических утверждения эквивалентными с помощью полного перебора |
Проверочные испытания: измерение производительности
Для новых версий программного обеспечения или для обеспечения сравнения с соперничающими системами иногда используются тесты, позволяющие сравнить относительную производительность алгоритмов. Если, например, выпускается новый алгоритм сортировки, его можно сравнить с предшественниками, чтобы убедиться, что алгоритм по меньшей мере столь же эффективен на известных данных, как и другие. Тесты производительности могут быть использованы пользователями для сравнения продуктов от различных производителей для оценки, какой продукт будет больше подходить под их требования в терминах функциональности и производительности.
Некоторые тесты производительности дают возможность проведения сравнительного анализа различных компилирующих и интерпретирующих языков, как, например, Roy Longbottom’s PC Benchmark Collection[3], а The Computer Language Benchmarks Game[en] сравнивает производительность реализаций типичных задач в некоторых языках программирования.
(Достаточно легко создать «самодельные» тесты производительности для получения представления об относительной эффективности различных языков программирования, используя набор пользовательских критериев, как это сделал Христофер Коувел-Шах в статье «Nine language Performance roundup»)[4]
Вопросы реализации
Вопросы реализации могут также повлиять на фактическую эффективность. Это касается выбора языка программирования и способа, каким алгоритм фактически закодирован, выбора транслятора для выбранного языка или используемых опций компилятора, и даже используемой операционной системы. В некоторых случаях язык, реализованный в виде интерпретатора, может оказаться существенно медленнее, чем язык, реализованный в виде компилятора[5].
Есть и другие факторы, которые могут повлиять на время или используемую память, но которые оказываются вне контроля программиста. Сюда попадают выравнивание данных, детализация[en], сборка мусора, параллелизм на уровне команд и вызов подпрограмм[6].
Некоторые процессоры имеют способность выполнять векторные операции, что позволяет одной операцией обработать несколько операндов. Может оказаться просто или непросто использовать такие возможности на уровне программирования или компиляции. Алгоритмы, разработанные для последовательных вычислений, могут потребовать полной переработки для использования параллельных вычислений.
Другая проблема может возникнуть с совместимостью процессоров, в которых команды могут быть реализованы по другому, так что команды на одних моделях могут быть относительно более медленными на других моделях. Это может оказаться проблемой для оптимизирующего компилятора.
Измерение использования ресурсов
Измерения обычно выражаются как функция от размера входа n.
Два наиболее важных измерения:
- Время: как долго алгоритм занимает процессор.
- Память: как много рабочей памяти (обычно RAM) нужно для алгоритма. Здесь есть два аспекта: количество памяти для кода и количество памяти для данных, с которыми код работает.
Для компьютеров, питающихся от батарей (например, лэптопов) или для очень длинных/больших вычислений (например, на суперкомпьютерах), представляют интерес измерения другого рода:
- Прямое потребление энергии: энергия, необходимая для работы компьютера.
- Косвенное потребление энергии: энергия, необходимая для охлаждения, освещения, и т. п.
В некоторых случаях нужны другие, менее распространённые измерения:
- Размер передачи: пропускная способность канала может оказаться ограничивающим фактором. Для уменьшения количества передаваемых данных можно использовать сжатие. Отображение рисунка или изображения (как, например, Google logo) может привести к передаче десятков тысяч байт (48K в данном случае). Сравните это с передачей шести байт в слове «Google».
- Внешняя память: память, необходимая на диске или другом устройстве внешней памяти. Эта память может использоваться для временного хранения или для будущего использования.
- Время отклика: параметр особенно важен для приложений, работающих в реальном времени, когда компьютер должен отвечать быстро на внешние события.
- Общая стоимость владения: параметр важен, когда предназначен для выполнения одного алгоритма.
Время
Теория
Для анализа алгоритма обычно используется анализ временно́й сложности алгоритма, чтобы оценить время работы как функцию от размера входных данных. Результат обычно выражается в терминах «O» большое. Это полезно для сравнения алгоритмов, особенно в случае обработки большого количества данных. Более детальные оценки нужны для сравнения алгоритмов, когда объём данных мал (хотя такая ситуация вряд ли вызовет проблемы). Алгоритмы, которые включают параллельные вычисления, могут оказаться для анализа более трудными.
Практика
Используются сравнительные тесты времени работы алгоритма. Многие языки программирования содержат функции, отражающие время использования процессора. Для долго работающих алгоритмов затраченное время также может представлять интерес. Результаты в общем случае нужно усреднять по серии тестов.
Этот вид тестов может быть очень чувствителен к конфигурации «железа» и возможности работы других программ в то же самое время в мультипроцессорной и мультизадачной среде.
Этот вид тестов существенно зависит также от выбора языка программирования, компилятора и его опций, так что сравниваемые алгоритмы должны быть реализованы в одинаковых условиях.
Память
Этот раздел касается использования основной памяти (зачастую, RAM) нужной алгоритму. Как и для временно́го анализа выше, для анализа алгоритма обычно используется анализ пространственной сложности алгоритма[en], чтобы оценить необходимую память времени исполнения как функцию от размера входа. Результат обычно выражается в терминах «O» большое.
Существует четыре аспекта использования памяти:
- Количество памяти, необходимой для хранения кода алгоритма.
- Количество памяти, необходимое для входных данных.
- Количество памяти, необходимое для любых выходных данных (некоторые алгоритмы, такие как сортировки, часто переставляют входные данные и не требуют дополнительной памяти для выходных данных).
- Количество памяти, необходимое для вычислительного процесса во время вычислений (сюда входят именованные переменные и любое стековое пространство, необходимое для вызова подпрограмм, которое может быть существенным при использовании рекурсии).
Ранние электронные компьютеры и домашние компьютеры имели относительно малый объём рабочей памяти. Так, в 1949 EDSAC имел максимальную рабочую память 1024 17-битных слов, а в 1980 Sinclair ZX80 выпускался с 1024 байтами рабочей памяти.
Современные компьютеры могут иметь относительно большое количество памяти (возможно, гигабайты), так что сжатие используемой алгоритмом памяти в некоторое заданное количество памяти требуется меньше, чем ранее. Однако существование трёх различных категорий памяти существенно:
- Кэш (часто, статическая RAM) — работает на скоростях, сравнимых с ЦПУ
- Основная физическая память (часто, динамическая RAM) — работает чуть медленнее ЦПУ
- Виртуальная память (зачастую, на диске) — даёт иллюзию огромной памяти, но работает в тысячи раз медленнее RAM.
Алгоритм, необходимая память которого укладывается в кэш компьютера, работает много быстрее, чем алгоритм, умещающийся в основную память, который, в свою очередь, будет много быстрее алгоритма, который использует виртуальное пространство. Усложняет ситуацию факт, что некоторые системы имеют до трёх уровней кэша. Различные системы имеют различное количество этих типов памяти, так что эффект памяти для алгоритма может существенно отличаться при переходе от одной системы к другой.
В ранние дни электронных вычислений, если алгоритм и его данные не помещались в основную память, он не мог использоваться. В наши дни использование виртуальной памяти обеспечивает огромную память, но за счёт производительности. Если алгоритм и его данные умещаются в кэш, можно получить очень высокую скорость, так что минимизация требуемой памяти помогает минимизировать время. Алгоритм, который не помещается полностью в кэш, но обеспечивает локальность ссылок[en], может работать сравнительно быстро.
Примеры эффективных алгоритмов
Критика текущего состояния программирования
Программы становятся медленнее более стремительно, чем компьютеры становятся быстрее.
- Мэй утверждает:
В широко распространённых системах уменьшение вдвое выполнение команд может удвоить жизнь батареи, а большие данные дают возможность для лучших алгоритмов: Уменьшение числа операций с 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» (Автостопом по галактике)[8]). Он оценил падение производительности на 70 dB, или на «99.99999 % от возможного», по сравнению с 1980-ми годами — «когда Артур Кларк сравнил вычислительные способности компьютеров 2001 с компьютером HAL в книге 2001: A Space Odyssey, он указал, что удивительно малы и мощны были компьютеры, но программы стали печально разочаровывающими».
Соревнования за лучший алгоритм
Следующие соревнования приглашают принять участие в разработке лучших алгоритмов, критерий качества которых определяют судьи:
См. также
- Анализ алгоритмов
- Арифметическое кодирование — вид энтропийного кодирования с переменной длиной кода[en] для эффективного сжатия данных
- Ассоциативный массив — структура данных, которую можно сделать более эффективной при применении деревьев PATRICIA[en] или массивов Джуди[en]
- Тест производительности — метод измерения сравнительного времени исполнения в определённых случаях
- Наилучший, наихудший и средний случай[en] — соглашения по оценке времени выполнения по трём сценариям
- Двоичный поиск — простая и эффективная техника поиска в отсортированном списке
- Таблица ветвления[en] — техника сокращения длины команд, размера машинного кода, и зачастую, памяти
- Оптимизирующий компилятор — компилятор, использующий различные методы получения более оптимального программного кода при сохранении функциональных возможностей
- Вычислительная сложность математических операций[en]
- Вычислительная сложность — понятие в информатике, обозначающее зависимости объёма работы от размера входных данных
- Вычислительная мощность компьютера — количественная характеристика скорости выполнения операций на компьютере
- Сжатие данных — сокращение объёма передачи данных и занимаемого дискового пространства
- Индекс — данные, увеличивающие скорость выборки данных из таблиц
- Энтропийное кодирование — кодирование последовательности значений с возможностью однозначного восстановления с целью уменьшения объёма данных (длины последовательности) с помощью усреднения вероятностей появления элементов в закодированной последовательности
- Сборка мусора — автоматическое освобождение памяти после использования
- Зелёные информационные технологии[en] — движение за внедрение «зелёных» технологий, потребляющих меньше ресурсов
- Код Хаффмана — алгоритм эффективного кодирования данных
- Improving Managed code Performance — Microsoft MSDN Library
- Локальность ссылок[en] — во избежание задержек, вызванных кэшированием из-за нелокального доступа к памяти
- Оптимизация циклов[en]
- Управление паматью
- Оптимизация (информатика)
- Анализ производительности — методы измерения фактической производительности алгоритма в реальном времени
- Вычисления в реальном времени — пример критичных по времени приложений
- Динамический анализ[en] — оценка ожидаемого времени работы и расщепляемость алгоритма
- Одновременная многопоточность
- Упреждающее исполнение[en], когда вычисления проводятся, даже если ещё неизвестно, понадобятся ли их результаты, или немедленное вычисление[en] как противоположность ленивым вычислениям
- Временна́я многопоточность
- Шитый код — один из способов реализации промежуточной виртуальной машины при интерпретации языков программирования (наряду с байт-кодом)
- Таблица виртуальных методов — механизм поддержки динамического соответствия (или метода позднего связывания)
Примечания
Литература
Ссылки
Оценка эффективности алгоритма | Data Science
Алгоритм — набор инструкций, описывающих порядок действий исполнителя для достижения некоторого результата.
ВременнАя эффективность является индикатором скорости работы алгоритма
оценивается по количеству основных операций, которые должен выполнить алгоритм при обработке входных данных размера n
Важен порядок роста времени выполнения алгоритма в зависимости от n
Пространственная эффективность показывает, сколько дополнительной оперативной памяти нужно для работы алгоритма. Эффективность оценивают в наихудшем, наилучшем и среднем случаях.
Виды анализа: математический и эмпирический
Измерение времени выполнения алгоритма
1. Непосредственное (эмпирический анализ)
2. Определение количества базовых операций, которые должен выполнить алгоритм при обработке входных данных размера n (математический анализ)
Порядок роста
При малых размерах входных данных невозможно заметить разницу во времени выполнения между эффективным и неэффективным алгоритмом. Для больших значений n вычисляют порядок роста функции.
Эффективность алгоритма в разных случаях
Существует большое количество алгоритмов, время выполнения которых зависит не только от размера входных данных, но и от конкретных особенностей входных данных (пример – поиск).
Эффективность измеряют для:
Пример: среднее количество операций сравнения при поиске:
Итак:
При разработке алгоритмов очень важно иметь возможность оценить ресурсы, необходимые для проведения вычислений, результатом оценки является функция сложности (трудоемкости). Оцениваемым ресурсом чаще всего является процессорное время (вычислительная сложность) и память (сложность алгоритма по памяти). Оценка позволяет предсказать время выполнения и сравнивать эффективность алгоритмов.
Эффективность алгоритмов
Внимание! Данный сайт не обновляется. Новая версия: shatalov.su
Дата создания: 2009-03-25 12:50:48
Последний раз редактировалось: 2012-02-08 06:29:55
Данная статья — вступительная в разделе «Алгоритмы».
В данном разделе мы сосредоточимся на двух направлениях: структуры данных и непосредственно алгоритмы.
С кое-какими структурами данных Вы уже познакомились: массивы, структуры, классы. Это примеры статических структур данных. Т.е. задали мы вначале программы десять элементов массива, в конце программы этих элементов так и осталось десять. На страницах рассылки и в данном разделе мы познакомимся динамическими структурами данных. Некоторые из этих структур просто делают программистскую жизнь легче, без других невозможно построить определённый алгоритм.
Также структур данных касаются ещё две области программирования, которые мы будем рассматривать: STL и D3DX. В STL (стандартная библиотека шаблонов в C++) собраны математические структуры данных и алгоритмы, а в D3DX (вспомогательная библиотека DirectX) присутствует ряд интересных нам структур, которые непосредственно используются в графических приложениях.
Эффективность алгоритмов
В данном — вступительном выпуске мы не будем рассматривать какую-либо конкретную структуру. Здесь мы поговорим об эффективности алгоритмов. Для этого нам потребуется ввести несколько понятий.
Сразу хочу подчеркнуть, что в данной статье я сознательно упрощаю материал. И с математической точки зрения, некоторые определения в данной статье не корректны. За более точным и полным описанием математических понятий, вам потребуется обратиться к учебникам по алгоритмам.
Приступим. Есть несколько критериев оценки эффективности алгоритмов. Для простоты мы будем обсуждать только временную эффективность.
Казалось бы временная эффективность должна выражаться в секундах. Но в данном случае это не так. потому что один и тот же алгоритм на разных компьютерах выполнится за разное количество времени.
Рассмотрим пример: у нас есть массив из десяти элементов. И у нас есть два алгоритма: поиск элемента в массиве и сортировка массива.
Первый алгоритм ищет в массиве определённое значение. Например, нужно проверить есть ли в массиве число 14. Для этого каждый элемент массива сравнивается с этим числом.
Второй алгоритм выстраивает элементы массива по возрастанию. Для этого ищется самое маленькое значение и помещается в начало, затем ищется следующее значение и так далее, пока в начале массива не окажется самый маленький элемент, а в конце — самый большой.
Что у нас здесь есть? Прежде всего размер входных данных. Обозначим его — n. Из нашего примера n = 10.
Так вот, эффективность алгоритма — это функция зависящая от размера входных данных. Чем больше входных данных, тем дольше будет выполняться алгоритм.
Функция в математическом контексте и в программистском понимается примерно одинаково. Есть различия, но пока они для нас несущественны.
При выполнении алгоритма для каждого входного значения выполняется какая-то базовая операция. В алгоритме поиска — это простое сравнение. При сортировке базовая операция посложнее. Базовая операция тоже влияет на эффективность алгоритма.
В данном примере эффективность алгоритма удобно понимать не как функцию, а как цикл. Смотрите: у нас есть набор входных данных в количестве n. n — это количество повторений цикла. А базовая операция — это тело цикла.
Порядок роста
Теперь нам нужно рассмотреть зависимость изменения количества базовых операций необходимых для выполнения алгоритма от увеличения размера входных данных.
Пример: у нас есть упорядоченный массив из 10 элементов. Представим, что нам нужно найти два числа. Во время поиска оказалось, что первое число находилось в середине массива, а второе — в конце. Теперь возьмём массив из 20 элементов (в два раза больше). И опять, элементы расположены так, что первый элемент оказался в середине, а второй в конце. Эти два случая имеют одинаковый порядок роста: при увеличении размера входных данных в два раза, количество базовых операций необходимых для выполнения алгоритма увеличилось в два раза.
Примечание: заметьте, что хотя мы и используем один алгоритм в примере, но рассматриваем два случая выполнения этого алгоритма. В данном контексте мы можем говорить о двух разных алгоритмах. Это важно!
Теперь переходим к самому важному в статье.
Сравнение порядков роста
Количество базовых операций за которое выполняется алгоритм — это время выполнения алгоритма. Обозначим его как t(n).
И обозначим какую-нибудь простая функция g(n) с которой мы будем сравнивать время выполнения t(n).
Для сравнения порядков роста двух алгоритмов используют предел отношения времени выполнения двух алгоритмов.
При постоянно увеличивающемся n мы вычисляем отношение t(n) к g(n).
В первом случае t(n) имеет меньший порядок роста. При увеличении размера входных данных, знаменатель будет расти намного быстрее числителя. Соответственно чем больше n, тем результат будет ближе к нулю.
Во втором случае порядок роста t(n) и g(n) одинаковый. с — какая-то константа. Т.е. при увеличении размера входных данных, насколько вырос порядок роста t(n) настолько же вырос и порядок роста g(n).
В третьем случае t(n) имеет больший порядок роста. Соответственно результат стремится к бесконечности.
Ну, вот в общем то и всё. Тема на первый взгляд не сильно нужная, но иногда бывает очень нужно выразить эффективность алгоритма числом. Практическое применение материала из данной статьи Вы увидите в последующих уроках этого раздела.
Анализ алгоритма / Хабр
Что такое анализ?
Анализируя алгоритм, можно получить представление о том, сколько времени займет решение данной задачи при помощи данного алгоритма. Одну и ту же задачу можно решить с помощью различных алгоритмов. Анализ алгоритмов дает нам инструмент для выбора алгоритма.
Результат анализа алгоритмов — не формула для точного количества секунд или компьютерных циклов, которые потребует конкретный алгоритм. Нужно понимать, что разница между алгоритмом, который делает N + 5 операций, и тем, который делает N + 250 операций, становится незаметной, как только N становится очень большим.
Классы входных данных
При анализе алгоритма выбор входных данных может существенно повлиять на его выполнение. Скажем, некоторые алгоритмы сортировки могут работать очень быстро, если входной список уже отсортирован, тогда как другие алгоритмы покажут весьма скромный результат на таком списке. А вот на случайном списке результат может оказаться противоположным. Поэтому не будем ограничиваться анализом поведения алгоритмов на одном входном наборе данных. Практически нужно искать такие данные, которые обеспечивают как самое быстрое, так и самое медленное выполнение алгоритма. Кроме того, полезно оценивать и среднюю эффективность алгоритма на всех возможных наборах данных.
Наилучший случай
Время выполнения алгоритма в наилучшем случае очень часто оказывается маленьким или просто постоянным, поэтому подобный анализ проводится редко.
Наихудший случай
Анализ наихудшего случая чрезвычайно важен, поскольку он позволяет представить максимальное время работы алгоритма. При анализе наихудшего случая необходимо найти входные данные, на которых алгоритм будет выполнять больше всего работы.
Средний случай
Анализ среднего случая является самым сложным, поскольку он требует учета множества разнообразных деталей. В основе анализа лежит определение различных групп, на которые следует разбить возможные входные наборы данных. На втором шаге определяется вероятность, с которой входной набор данных принадлежит каждой группе. На третьем шаге подсчитывается время работы алгоритма на данных из каждой группы. Время работы алгоритма на всех входных данных одной группы должно быть одинаковым, в противном случае группу следует подразбить. Среднее время работы вычисляется по формуле
где через n обозначен размер входных данных, через m — число групп. через pi — вероятность того, что входные данные принадлежат группе с номером i, а через ti — время, необходимое алгоритму для обработки данных из группы с номером i.
В большинстве случаев мы будем предполагать, что вероятности попадания входных данных в каждую из групп одинаковы. Другими словами, если групп пять, то вероятность попасть в первую группу такая же, как вероятность попасть во вторую, и т.д., то есть вероятность
попасть в каждую группу равна 0.2. В этом случае среднее время работы можно либо оценить по предыдущей формуле, либо воспользоваться эквивалентной ей формулой
Нижние границы. Дерево решений.
Алгоритм является оптимальным, если любой любой другой алгоритм, решающий данную задачу, работает не быстрее данного. Как узнать оптимальность алгоритма? Для этого мы должны знать минимальное количество операций, необходимое для решения поставленной задачи, которое называется нижней границей. Но для этого нам нужно изучать именно ЗАДАЧУ, а не конкретный алгоритм!
Как пример, рассмотрим анализ процесса сортировки списка из 3 чисел, воспользовавшись бинарным деревом. Такое дерево называется деревом решений.
Самый длинный путь в данном дереве соответствует наихудшему случаю и наоборот, кратчайший — наилучшему. Средний случай описывается частным от деления числа ребер в дереве на число листов.
Для перестановки 2-х элементов мы имеем 1лист, для N эл-тов, по правилам комбинаторики, N! листов. Число листов на уровне K равно 2k-1, поэтому в нашем дереве решений буде L -уровней, где L — наименьшее целое число, для которого N! ≤ 2L-1. Логарифмируя, получим
В конечном итоге, получаем:
Вот мы и узнали, что любой алгоритм сортировки, порядка О(NlgN) является наилучшим и его можно считать оптимальным. Более того, из этого исследования вытекает, что алгоритм, решающий задачу сортировки быстрее О(NlgN) операций, не может работать правильно!
Алгоритмическая эффективность и нотация Big-O
В информатике часто вопрос не в том, как решить проблему,
но как решить проблему хорошо. Например, возьмем задачу сортировки.
Многие алгоритмы сортировки хорошо известны; проблема не в том, чтобы найти
способ сортировки слов, но найти способ эффективно сортировать слова. Эта
статья о том, как сравнить относительную эффективность
алгоритмов и почему это важно, используя концепцию, называемую нотацией большого О, для определения эффективности алгоритма.
Почему грубой силы недостаточно
Если возможно решить проблему методом грубой силы,
например, опробовать все возможные комбинации решений (например,
сортировка группы слов, пробуя все возможные порядки, пока вы
найти тот, который в порядке), тогда зачем нужно искать лучший
подходить? Самый простой ответ: если у вас был достаточно быстрый компьютер,
может, и не было бы. Но в настоящее время у нас нет доступа к компьютерам.
достаточно быстро.149 секунд, что больше ожидаемого срока службы
Вселенная. Очевидно, что наличие более эффективного алгоритма сортировки слов
быть под рукой; и, конечно же, многие из них могут сортировать 100 слов в
жизнь вселенной.
Прежде чем двигаться дальше, важно понять некоторую терминологию
используется для измерения алгоритмической эффективности. Обычно эффективность
алгоритм выражается в том, как долго он работает по отношению к его входным данным.Например, в приведенном выше примере мы показали, сколько времени потребуется
наш наивный алгоритм сортировки для сортировки определенного количества слов. Как правило
мы называем длину ввода n; Итак, для приведенного выше примера
эффективность примерно n !. Вы могли заметить, что это возможно
придумать правильный порядок на ранней стадии попытки — например,
если слова уже частично упорядочены, маловероятно, что алгоритм
пришлось бы все попробовать! комбинации.Часто мы говорим о среднем
КПД, который в этом случае был бы n! / 2. Но поскольку разделение
на два почти не имеет значения с ростом n (половина от 2 миллиардов
это, например, все еще очень большое число), мы обычно игнорируем константу
условия (если постоянный член не равен нулю).
Теперь, когда мы можем описать эффективность любого алгоритма с точки зрения его
длина ввода (при условии, что мы знаем, как вычислить эффективность), мы можем
сравнивать алгоритмы по их «порядку».2).
Эта нотация, известная как нотация большого O, является типичным способом описания
алгоритмическая эффективность; обратите внимание, что нотация большого O обычно не
призыв к включению констант. Также, если вы определяете заказ
алгоритма и порядка оказывается суммой нескольких слагаемых,
вы обычно выражаете эффективность как только термин с
высший заказ. Например, если у вас есть эффективный алгоритм
n ^ 2 + n, тогда это алгоритм порядка O (n ^ 2).
Ученые-информатики (и обычные программисты тоже) используют нотацию с большим О для обсуждения многих алгоритмов, а также для анализа кода, который они пишут. В следующей статье этой серии вы узнаете, как анализировать алгоритм и определять его нотацию с большим О.
Часть 2: Как определить большой О алгоритма (он же порядок алгоритма)
перейти к Части 3: Примеры различных
приказы и алгоритмы
.
|
.Производительность
— Эффективность алгоритма — Qaru
Переполнение стека
- Около
Продукты
- Для команд
Переполнение стека
Общественные вопросы и ответыПереполнение стека для команд
Где разработчики и технологи делятся частными знаниями с коллегамиВакансии
Программирование и связанные с ним технические возможности карьерного ростаТалант
Нанимайте технических специалистов и создавайте свой бренд работодателяРеклама
Обратитесь к разработчикам и технологам со всего мира
.Эффективность алгоритма
— это … Что такое эффективность алгоритма?
Алгоритм — Блок-схема алгоритма (алгоритм Евклида) для вычисления наибольшего общего делителя (НОД) двух чисел a и b в точках с именами A и B. Алгоритм выполняется путем последовательного вычитания в двух циклах: IF тест B ≤ A дает да…… Wikipedia
Примеры алгоритмов — Эта статья Примеры алгоритмов дополняют характеристики алгоритмов и алгоритмов.= Пример: спецификация алгоритма сложения m + n = Выбор модели машины: Эта проблема не была решена математическим сообществом. Нет…… Википедия
алгоритм — (происходит от имени исламского математика Аль Ховаризми) Набор правил или инструкций, которые приведут к решению проблемы. Алгоритм дает процедуру решения или вычислимый метод решения проблемы. Хотя…… Философский словарь
Алгоритм «разделяй и властвуй» — В информатике «разделяй и властвуй» (D C) является важной парадигмой разработки алгоритмов, основанной на многоразветвленной рекурсии.Алгоритм «разделяй и властвуй» работает путем рекурсивного разбиения проблемы на две или более подзадач одной и той же (или…… Wikipedia
Алгоритмическая эффективность — В информатике эффективность используется для описания свойств алгоритма, связанных с тем, сколько различных типов ресурсов он потребляет. Алгоритмическую эффективность можно рассматривать как аналог производительности разработки для повторяющихся или…… Wikipedia
Генетический алгоритм — Генетический алгоритм (GA) — это эвристика поиска, которая имитирует процесс естественной эволюции.Эта эвристика обычно используется для выработки полезных решений проблем оптимизации и поиска. Генетические алгоритмы принадлежат к большему классу…… Wikipedia
Алгоритм Кнута – Морриса – Пратта — Алгоритм поиска строки Кнута – Морриса – Пратта (или алгоритм KMP) ищет вхождения слова W в основной текстовой строке S, используя наблюдение, что при возникновении несоответствия слово сам по себе содержит достаточно информации для…… Wikipedia
Алгоритм «разделяй и властвуй на собственные значения» — Алгоритмы «разделяй и властвуй на собственные значения» — это класс алгоритмов собственных значений для эрмитовых или вещественных симметричных матриц, которые в последнее время (около 1990-х годов) стали конкурентоспособными с точки зрения стабильности и эффективности с более традиционными алгоритмами, такими как… … Википедия
Алгоритм Марзулло — алгоритм Марзулло, изобретенный Китом Марзулло для его Ph.Докторская диссертация в 1984 году представляет собой алгоритм согласования, используемый для выбора источников для оценки точного времени из ряда зашумленных источников времени. Его усовершенствованная версия, переименованная в…… Wikipedia
Алгоритм замены страницы — Эта статья посвящена алгоритмам, специфичным для разбиения на страницы. Описание общих алгоритмов кэширования (например, процессора, диска, базы данных, сети) см. В разделе Алгоритмы кеширования. В компьютерной операционной системе, которая использует подкачку для управления виртуальной памятью, страница…… Wikipedia
Экономическая эффективность — (или экономическая оптимальность) в контексте параллельных компьютерных алгоритмов означает меру того, насколько эффективно параллельные вычисления могут использоваться для решения конкретной проблемы.Параллельный алгоритм считается рентабельным, если его асимптотическое выполнение… Wikipedia
.