Ефективність алгоритму

Ефективність алгоритму — це властивість алгоритму, пов'язана з обчислювальними ресурсами, використовуваними алгоритмом. Алгоритм повинен бути проаналізований з метою визначення необхідних йому ресурсів. Ефективність алгоритму можна розглядати як аналог виробничої продуктивності повторюваних або безперервних процесів.

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

Зауважимо, що дана стаття НЕ про оптимізацію алгоритму, яка обговорюється в статтях оптимізація програми, оптимізувальний компілятор, оптимізація циклів, оптимізатор об'єктного коду^[en] тощо. Термін «оптимізація» сам по собі вводить в оману, оскільки все, що може бути зроблено, потрапляє під визначення «покращення».

Історія питання

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

	Майже у всіх обчисленнях можливий великий вибір конфігурацій для успішного завершення процесу і різні угоди повинні впливати на вибір з метою виконання обчислень. Істотна річ - вибір конфігурації, яка приведе до мінімізації часу, необхідного для виконання обчислення.»
— [1]

Ранні електронні комп'ютери були дуже обмежені як за швидкістю, так і за пам'яттю. У деяких випадках було усвідомлено, що існує компроміс часу і пам'яті, за якого задача повинна або використовувати велику кількість пам'яті для досягнення високої швидкості, або застосовувати більш повільний алгоритм, який використовує невелику кількість робочої пам'яті. В цьому випадку використовувався найбільш швидкий алгоритм, для якого вистачало наявної пам'яті.

Сучасні комп'ютери набагато швидші від тих ранніх комп'ютерів і мають значно більше пам'яті (гігабайти замість кілобайт). Проте, Дональд Кнут підкреслює, що ефективність залишається важливим фактором:

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

Огляд

Алгоритм вважається ефективним, якщо споживаний ним ресурс (або вартість ресурсу) на рівні або нижче деякого прийнятного рівня. Грубо кажучи, «прийнятний» тут означає «алгоритм буде працювати помірний час на доступному комп'ютері». Оскільки з 1950-х років спостерігалося значне збільшення обчислювальної потужності і доступної пам'яті комп'ютерів, сучасний «прийнятний рівень» не був прийнятним навіть 10 років тому.

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

Існує багато шляхів вимірювання використовуваних алгоритмом ресурсів. Два найбільш використовуваних вимірювання — швидкість і використовувана пам'ять. Інші вимірювання можуть включати швидкість, тимчасове використання диска, тривале використання диска, споживання енергії, сукупна вартість володіння, час відгуку на зовнішні сигнали тощо. Багато з цих вимірювань залежать від обсягу вхідних даних алгоритму (тобто від кількостей даних, що вимагають обробки). Вимірювання можуть також залежати від того, як подані дані (наприклад, деякі алгоритми сортування погано працюють на вже відсортованих даних або коли дані відсортовані в зворотному порядку).

На практиці існують й інші чинники, що впливають на ефективність алгоритму, такі як необхідна точність і/або надійність. Як пояснено нижче, спосіб реалізації алгоритму може також істотно вплинути на фактичну ефективність, хоча багато аспектів реалізації відносяться до питань оптимізації.

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

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

Деякі приклади нотації «O» велике :

позначення	Назва	приклади
${\displaystyle O(1)\,}$	постійне	Визначення, парне чи непарне число. Використання таблиці пошуку постійного розміру. Використання підхожої хеш-функції для вибору елемента.
${\displaystyle O(\log n)\,}$	логарифмічне	Знаходження елемента у відсортованому масиві за допомогою двійкового пошуку або збалансованого дерева, як і операції в біноміальній купі.
${\displaystyle O(n)\,}$	лінійне	Пошук елемента в несортованому списку або незбалансованому дереві (найгірший випадок). Додавання двох n-бітних чисел з використанням наскрізного переносу.
${\displaystyle O(n\log n)\,}$	квазілінійне, логарифмічно лінійне	Обчислення швидкого перетворення Фур'є, пірамідальне сортування, швидке сортування (кращий і середній випадок), сортування злиттям
${\displaystyle O(n^{2})\,}$	квадратне	Множення двох n-значних чисел за допомогою простого алгоритму, сортування бульбашкою (найгірший випадок), сортування Шелла, швидке сортування (найгірший випадок), сортування вибором, сортування вставками
${\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) може передбачати передавання десятків тисяч байт (232K в даному випадку). Порівняйте це з передачею шести байт у слові «Google».
• Зовнішня пам'ять: пам'ять, необхідна на диску або іншому пристрої зовнішньої пам'яті. Ця пам'ять може використовуватися для тимчасового зберігання або для майбутнього використання.
• Час відгуку: параметр особливо важливий для застосунків, що працюють у реальному часі, коли комп'ютер повинен швидко відповідати на зовнішні події.
• Загальна вартість володіння: параметр важливий, коли призначений для виконання одного алгоритму.

Час

Теорія

Для аналізу алгоритму зазвичай використовується аналіз часової складності алгоритму, щоб оцінити час роботи як функцію від розміру вхідних даних. Результат зазвичай виражається в термінах «O» велике . Це корисно для порівняння алгоритмів, особливо в разі обробки великої кількості даних. Більш детальні оцінки потрібні для порівняння алгоритмів, коли обсяг даних малий (хоча така ситуація навряд чи викличе проблеми). Алгоритми, які включають паралельні обчислення, можуть виявитися важчими для аналізу.

Практика

Використовуються порівняльні тести часу роботи алгоритму. Багато мов програмування містять функції, що відображають час використання процесора. Для алгоритмів, що працюють довго, витрачений час також може являти інтерес. Результати в загальному випадку потрібно усереднювати за серією тестів.

Цей вид тестів може бути дуже чутливим до зміни обладнання і можливості роботи інших програм у той самий час у багатопроцесорному і багатозадачному середовищі.

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

Пам'ять

Цей розділ стосується використання основної пам'яті (найчастіше, RAM) потрібної алгоритму. Як і для часового аналізу вище, для аналізу алгоритму зазвичай використовується аналіз просторової складності алгоритму^[en], щоб оцінити необхідну пам'ять часу виконання як функцію від розміру входу. Результат зазвичай виражається в термінах «O» велике.

Існує чотири аспекти використання пам'яті:

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

Ранні електронні комп'ютери і домашні комп'ютери мали відносно малий обсяг робочої пам'яті. Так, в 1949 EDSAC мав найбільшу робочу пам'ять 1024 17-бітних слів, а в 1980 Sinclair ZX80 випускався з 1024 байтами робочої пам'яті.

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

• Кеш (часто, статична RAM) — працює на швидкостях, порівнянних з ЦПУ
• Основна фізична пам'ять (часто, динамічна RAM) — працює трохи повільніше, ніж ЦПУ
• Віртуальна пам'ять (найчастіше, на диску) — дає ілюзію величезної пам'яті, але працює в тисячі разів повільніше, ніж RAM.

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

У ранні дні електронних обчислень, якщо алгоритм і його дані не вміщалися в основну пам'ять, він не міг використовуватися. В наші дні використання віртуальної пам'яті забезпечує величезну пам'ять, але за рахунок продуктивності. Якщо алгоритм і його дані вміщаються в кеш, можна отримати дуже високу швидкість, так що мінімізація необхідної пам'яті допомагає мінімізувати час. Алгоритм, який не поміщається повністю в кеш, але забезпечує локальність посилань^[en], може працювати порівняно швидко.

Приклади ефективних алгоритмів

• Швидке сортування, перший відомий алгоритм зі швидкістю близько ${\displaystyle O(n\log n)}$
• Пірамідальне сортування, інший швидкий алгоритм сортування
• Двійковий пошук для пошуку в упорядкованій таблиці
• Алгоритм Бойера — Мура для пошуку рядка всередині іншого рядка

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

• Девід Мей^[en], британський учений в галузі інформатики, професор інформатики Бристольського університету, засновник і головний інженер XMOS Semiconductor^[en] вважає, що одна з проблем полягає в існуванні віри, що закон Мура вирішує питання неефективності. Він запропонував «альтернативний» закон Мура (Закон Вірта^[ru])[7] :

Програми стають повільнішими більш стрімко, ніж комп'ютери стають швидшими.

Мей стверджує:

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

• Програміст Адам Н. Розербург у своєму блозі «The failure of the Digital computer», описав поточний стан програмування як близький до «Software event horizon» (рівню програмної катастрофи, натяк на фантастичний «shoe event horizon» (рівень взуттєвої катастрофи), описаний Дугласом Адамсом в його книзі «Автостопом по галактиці»[8]). Він оцінив падіння продуктивності на 70 dB, або на «99.99999 % від можливого», в порівнянні з 1980-ми роками — «коли Артур Кларк порівняв обчислювальні здатності комп'ютерів 2001 з комп'ютером HAL у книзі „2001: Космічна Одіссея“, він вказав, що на диво малі і потужні були комп'ютери, але програми стали сумно розчаровувати».

Змагання за кращий алгоритм

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

• Wired[9]

Див. також

• Аналіз алгоритмів
• Арифметичне кодування — вид ентропійного кодування зі змінною довжиною коду^[en] для ефективного стиснення даних
• Асоціативний масив — структура даних, яку можна зробити більш ефективною при застосуванні дерев PATRICIA або масивів Джуді^[en]
• Тест продуктивності — метод вимірювання порівняльного часу виконання в певних випадках
• Найкращий, найгірший і середній випадки^[en] — домовленості щодо оцінки часу виконання за трьома сценаріями
• Двійковий пошук — проста і ефективна техніка пошуку у відсортованому списку
• Таблиця галуження^[en] — техніка скорочення довжини команд, розміру машинного коду, і найчастіше, пам'яті
• Оптимізувальний компілятор — компілятор, який використовує різні методи отримання більш оптимального програмного коду при збереженні функціональних можливостей
• Обчислювальна складність математичних операцій^[en]
• Обчислювальна складність — поняття в інформатиці, що позначає залежності обсягу роботи від розміру вхідних даних
• Обчислювальна потужність комп'ютера — кількісна характеристика швидкості виконання операцій на комп'ютері
• Стиснення даних — скорочення обсягу передаваних даних і займаного дискового простору
• Індекс — дані, що збільшують швидкість вибірки даних з таблиць
• Ентропійне кодування — кодування послідовності значень з можливістю однозначного відновлення з метою зменшення обсягу даних (довжини послідовності) за допомогою усереднення ймовірностей появи елементів у закодованій послідовності
• Збирання сміття — автоматичне звільнення пам'яті після використання
• Зелені інформаційні технології — рух за впровадження «зелених» технологій, які споживають менше ресурсів
• Код Гаффмана — алгоритм ефективного кодування даних
• Improving Managed code Performance [Архівовано 24 грудня 2017 у Wayback Machine.] — Microsoft MSDN Library
• Локальність посилань — щоб уникнути затримок, викликаних кешуванням через доступ до нелокальної пам'яті
• Оптимізація циклів
• Керування пам'яттю
• Оптимізація (інформатика)
• Аналіз продуктивності — методи вимірювання фактичної продуктивності алгоритму в реальному часі
• Обчислення в реальному часі — приклад критичних за часом застосунків
• Одночасна багатопотоковість
• Випереджувальне виконання, коли обчислення проводяться, навіть якщо ще невідомо, чи знадобляться їх результати, або негайне обчислення(інші мови) як протилежність ледачих обчислень
• Часова багатопотоковість
• Шитий код — один із способів реалізації проміжної віртуальної машини при інтерпретації мов програмування (поряд з байт-кодом)
• Таблиця віртуальних методів — механізм підтримки динамічної відповідності (або методу пізнього зв'язування)

Примітки

1. Green, 2013.
2. Knuth, 1974.
3. Benchmark History.
4. Nine Language Performance Round-up: Benchmarking Math & File I/O | OSnews. Архів оригіналу за 28 листопада 2019. Процитовано 28 листопада 2019.
5. Floating Point Benchmark.
6. Steele, 1977.
7. Архивированная копия (PDF). Архів оригіналу (PDF) за 3 березня 2016. Процитовано 14 вересня 2017.
8. Архівована копія. Архів оригіналу за 23 листопада 2019. Процитовано 28 листопада 2019.
9. Fagone, Jason (29 листопада 2010). Teen Mathletes Do Battle at Algorithm Olympics. Wired. Архів оригіналу за 16 березня 2014. Процитовано 28 листопада 2019.

Література

• Christopher Green (2013). Classics in the History of Psychology. Архів оригіналу за 27 вересня 2013. Процитовано 19 травня 2013.
• Knuth D. Structured Programming with go-to Statements : [арх. 24 серпня 2009] // Computing Surveys. — ACM, 1974. — Т. 6, вип. 4.
• Whetstone Benchmark History. Roylongbottom.org.uk. Архів оригіналу за 15 січня 2012. Процитовано 14 грудня 2011.
• Floating Point Benchmark: Comparing Languages (Fourmilog: None Dare Call It Reason). Fourmilab.ch. 4 серпня 2005. Архів оригіналу за 11 грудня 2011. Процитовано 14 грудня 2011.
• Guy Lewis Steele, Jr. Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO // MIT AI Lab. AI Lab Memo AIM-443.. — 1977. — October.

Посилання

• Анімація алгоритму Бойєра-Мура (Java-аплет)
• «How algorithms shape our world». Виступ Кельвіна Славіна на TED-конференції .
• Misconceptions about algorithmic efficiency in high-schools

Портал «Програмування»   Портал «Інформаційні технології»