Алгоритмічна складність або як зробити зручним

Багато хто з нас стикалися з оцінкою складності алгоритмів і добре уявляють собі для чого вона потрібна. Але часто розробники застосовують-позначення виключно до коду, забуваючи про те, що алгоритми існують за його межами. При цьому, з її допомогою можна легко описати успіх Инстаграма, передбачити, що веб-додатки займуть домінуючу роль в найближчому десятилітті і навіть описати принцип роботи мозку.
Нещодавно я зіткнувся статті про користь Про-нотації в управлінні проектом, яка і змусила мене написати цей текст. Я давно і успішно застосовую оцінку складності в розробці і періодично стикаюся з обмеженим розумінням її розробниками.
Те, про що я кажу – це сама суть інформаційних технологій. Артемій Лебедєв спробував описати цей принцип, але вийшло ось що, сподіваюся, у мене вийде краще.
Ключем до успіху є зниження складності. Чимось це нагадує суміш з принципів KISS і ТРИЗ. Суть викладеного підходу формалізації будь-якого алгоритму і пошуку математичної симетрії там, де до цих пір прийнято користуватися інтуїцією і творчим підходом.
Приклади
Для початку я наведу різні приклади застосування принципу зниження алгоритмічної складності або ж порушення цих принципів. Можливо їх буде більше ніж ви очікували. Взагалі ідеальним прикладом є конвеєр Генрі Форда, але давайте розглянемо і інші:
Успіх Instagram
Я давно займаюся фотографією і добре уявляю собі процес перетворення знімка в продукт готовий до споживання. Давайте перерахуємо кроки, які здійснює користувач, для того щоб поділитися гарною фотографією. Для цього він повинен:
  1. Вивантажити знімок з фотоапарата на комп'ютер:
    1. Фізично підключити фотоапарат до комп'ютера/вставити карту пам'яті
    2. Відкрити папку з фотографіями

    3. Створити папку призначення на комп'ютері
    4. Перемістити файли
  2. Вибрати відповідний знімок:
    1. Відкрити програму-переглядач
    2. Відібрати кращі знімки

    3. Вибрати один-два з вподобаних
    4. Конвертувати в формат, прийнятний для редагування
  3. Обробити фотографію
    1. Запустити фоторедактор
    2. Перенести фотографію в фоторедактор

    3. Провести обробку (тут кількість вкладених кроків варіюється і може досягати декількох десятків, якщо не сотень)
    4. Зберегти оброблений дублікат
  4. Поділитися результатом
    1. Вибрати підходящу площадку: flickr, 500px, vk, fb, tumblr.
    2. Завантажити фотографію в альбом або колекцію, помістити на стіні/стрічці (залежить від сервісу).

    3. Придумати назву або опис, вказати теги (опціонально).
В описі даного алгоритму я опустив те, що людина при цьому має розібратися у відмінності JPEG і RAW, принцип роботи фоторедактора, встановити кілька програм і розібратися в десятках нюансів роботи кожної з них і при цьому володіти художнім смаком для отримання пристойного результату після обробки.
Тепер давайте поглянемо на цей процес з точки зору користувача Instagram:
  1. Запустити Instagram
  2. Зробити фотографію
  3. Накласти фільтр
  4. Придумати опис, додати мітки
  5. Опублікувати
Спочатку ми маємо 15 кроків і при цьому деякі з них можуть містити безліч "вкладених". Завдяки Instagram складність знизилася з 15+x дій до 5, а витрати часу знизилися з 30-40 хвилин, до декількох хвилин. Це колосальний виграш.
Приклад програми
Існує утиліта NVM для розробників на Node.js. Вона допомагає встановлювати різні версії Node.js і перемикатися між ними за допомогою двох команд install use. Той же самий процес установки свіжої версії Node.js на Ubuntu, вимагає як мінімум трьох кроків і двох ухвалення рішень, а про перемиканні між версіями я і говорити не хочу.
При цьому для роботи NVM патчіть файл
~/.profile
(щоб завантажуватися кожен раз, як користувач відкриває консоль), для цього в ньому міститься близько тисячі рядків досить складного коду з безліччю розгалужень для різних ОС. При цьому в unix є механізм стандартного розширення – це директорія
~/.profile.d
, куди потрібно складати такі скрипти, тоді установка і видалення розширення займає всього два рядки коду:
# Додати
cp some-init-script.sh ~/.profile.d/
# Видалити
rm ~/.profile.d/some-init-script.sh

Звичайно, не всі системи включають підтримку
~/.profile.d
тому ви можете легко знайти безліч програм які патчат
~/.profile
і кожен раз програмісти витрачають час на власну реалізацію такого патча для різних систем. Більш того визначити наявність патчів інших розробників стає просто неможливо через велику кількість кастомних рішень. Я називаю це явище too custom, коли єдине рішення не може бути впроваджено з-за надмірної кількості розгалужень, які потрібно буде врахувати.
до Речі, абсолютно така ж ситуація з автокомплитом. Багато програми не містять скрипт автодоповнення, тому що він вимагає прав супер-користувача при установці, хоча іноді програма повинна бути встановлена від імені користувача і тоді покласти скрипт автодоповнення можна в
~/.bash_completion.d
, але про це мало хто знає.
Чому веб-додатки будуть домінуватиЩоб почати користуватися веб-додатком, вам взагалі не потрібно нічого встановлювати. Час доставки прагне до нуля, як і кількість прийнятих рішень.
І т. д. і т. п.
Дуже багато сфер і компаній застосовують цей принцип, перераховувати можна дуже довго DevOps, UX, PayPal, AppStore, iTunes, Github...
Мозок
Наш мозок теж застосовує зниження алгоритмічної складності. Наочним прикладом є сленг і мова сам по собі. Замість того, щоб говорити "масивний газова куля, що випромінює світло й утримується силами власної гравітації і внутрішнім тиском, в надрах якого відбуваються (або відбувалися раніше) реакції термоядерного синтезу", ми просто говоримо "зоря". Очевидно, що це не тільки економить купу часу, але і спрощує розуміння. Візьмемо просте речення:
Сонце встає на Сході
і розгорнемо його
Масивний газова куля, що випромінює світло й утримується силами власної гравітації і внутрішнім тиском, в надрах якого відбуваються реакції термоядерного синтезу, який є центральним об'єктом Сонячної системи, з'являється з-за лінії горизонту з боку світла в напрямку якої обертається планета Земля.
Більш ніж упевнений, що ви читали друге речення побіжно, адже ви і так вже знаєте про що йде мова. Але що, якщо поміняти приклади місцями? Вам спочатку довелося розмістити в пам'яті всі ці поняття, розібратися у зв'язках причетних оборотів і спробувати уявити загальний зміст, перш ніж приступити до короткої версії.
Оцінка складності
Будь-який вибір – це збільшення складності.
І так, як же оцінити свій алгоритм. Необхідно скласти докладний план дій користувача від моменту знайомства до початку використання програми чи продукту, а так само проаналізувати кожну дію. Для цього достатньо зробити наступне:
  • Необхідно розписати кожен крок навіть з вигляду незначне.
  • Врахувати компетенції користувача та внести отримання цієї компетенції у складність алгоритму. Можна розділити користувачів за категоріями.
  • Кожен момент прийняття рішень користувачем повинен бути проаналізовано. Будь-який вибір ускладнює алгоритм.
  • Оцініть розгалуження алгоритму (всі конструкції "якщо-то" створюють нову гілку), якщо якісь гілки є найбільш часто використовуваними застосуйте до них механізм спрощення: придумайте термін, команду, зробіть окрему кнопку або панель швидкого доступу/параметрів/редагування/додавання/видалення.
Не зайвим буде врахувати попередній досвід користувача, так як переучуватися важче, ніж освоїти нове. І тепер ви розумієте чому: спочатку потрібно послабити старі зв'язки в мозку, а потім створити і зміцнити нові, а це два кроки замість одного.
Після того, як складений план, потрібно класифікувати дії і вибрати відповідний спосіб спрощення.
На жаль в даний момент у мене немає списку універсальних способів зниження складності, це питання потребує окремого вивчення, а застосування кожного способу вимагає розуміння специфіки продукту. Хорошим прикладом є гейміфікація, яку можна визначити як процес спрощення освоєння алгоритмів з більш високою складністю за рахунок поетапного збільшення складності. Так само у своїй роботі я часто застосовую ізоляцію, складні ділянки коду я виношу в окремий проект, щоб відсікти все зайве і сконцентруватися на головному, коли результат досягнутий і всі складні зв'язки розплутати або усунені, я переношу код.
Оцінка ефективності
Для того щоб оцінити результат потрібно підрахувати витрачаються користувачем ресурси: час, гроші й енергію. Враховувати бажано все: кількість рухів миші, час очікування, пошук потрібної кнопки і т. п. Якщо в результаті зміни алгоритму ви зекономили якийсь ресурс або значно поліпшили отриманий результат, значить ви на правильному шляху. Якщо ви не можете визначити ресурс, який користувач отримує в результаті, значить, швидше за все, ви не розумієте що робите насправді.
Сподіваюся ця стаття допоможе вам у подальшому при розробці ваших продуктів. Розраховую на подальше продовження дискусії для розвитку цієї теми.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.