Опановуємо основи алгоритмів, або Як прискорити код з 15 до 1000 запитів за секунду

У статті поговоримо про прикладне значення розуміння алгоритмів. Ви зможете наочно побачити, як маючи базові навички алгоритмічного аналізу можна суттєво покращи роботу ваших програм. Спочатку напишемо програму за неоптимальним алгоритмом, а потім крок за кроком будемо його поліпшувати, розглядаючи теорію складності алгоритмів, аналіз алгоритмів і структури даних. Пройдемо шлях від алгоритму, який опрацьовує 15 запитів на секунду, до алгоритму, який виконує 1000. Торкнемося тими розпаралелення задач. Стаття має бути цікавою як для бекенд, так і фронтенд-розробників різних рівнів.

Скоро вийде наступна стаття, де ми розглянємо SOLID. Я покажу кілька прикладів з кодом, де принципи SOLID порушуються, поясню, до чого це може призвести в довгостроковій перспективи та як це виправити.

10 років тому я почав кар'єр єру в IT як .NET-розробник. Зараз співпрацюю з EPAM Systems як Solution Architect. Мій основний стек технологій: Node.js, React, React Native, AWS та GCP. Роблю проєктування високонавантажених систем, попереднє оцінювання та планування проєктів. Проводжу консультації щодо розв'язків язання проблем продуктивності та стабільної роботи систем. Проєктую та імплементую UI/UX для бізнес-процесів високої складності. Сьогодні активно займаюся вивченням роботи стартапів на ранніх етапах розвитку, а також DLT та Blockchain технологій для потреб бізнесу.

Передмова

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

Через своє швидке зростання та масштаб індустрія програмного забезпечення спонукає розробників добре опанувати насамперед фреймворки, спеціалізовані бібліотеки та шаблони проєктування. Це правильний та оптимальний підхід, оскільки він дає змогу швидко та прогнозовано розробляти програмні системи, уникаючи великої кількості помилок. Глибинне розуміння того, як працює технологія, на якій ведеться розробка, алгоритмічний аналіз та оптимізація відходять на другий план. Фокус змінюється в протилежний бік лише тоді, коли потрібно розробляти самі фреймворки та бібліотеки.

Оскільки зараз процесорний годину порівняно дешевий і оперативна пам'ять також, від програмістів не вимагають писати супероптимальні програми. Бо порівняно з процесорним часом і оперативною пам яттю годину програміста дуже дорогий. Написання оптимізованих програм може тривати справді довго.

Гра починає змінюватися тоді, коли з'єднання являється високе навантаження. Наприклад, є система, запущена на 10 000 віртуальних комп'ютерній комп'ютерах (реальний випадок). 2000 з них — це вебсервери, решта — сервери з базами даних, розподіленими кешами та системами обміну повідомленнями. Зосередимось на вебсерверах. Чи допустима це віртуальні комп'ютерній комп'ютери з 4-ядерним процесором та 16 гігабайтами оперативної пам'яті. Місячна вартість роботи одного такого комп'ютера в AWS становить 70 доларів, а всіх 2000 комп'ютерній ютерів — 140 000 доларів. Тут вже стає цікавіше, адже якщо можна оптимізувати роботу програми хоча б на 10%, то на місяць досягнемо економії 14 000 доларів, а на рік це 168 000.

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

Схожий випадок був на одному з проєктів, для якого я проводив консультацію. Команда прийшла з проблемою, що їй не вдається масштабуватися. Система під високим навантаженням вже за кілька секунд переставала відповідати. Як виявилось, причиною стало те, що на API виконувалося багато обчислень, але за неоптимальними алгоритмами. Система показувала себе добре на етапі розробки, бо тоді її навантаження здатність становило не більше як 10 запитів за секунду. Коли під час навантажувального тестування пішли тисячі конкурентних запитів — система захлинулася.

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

Звісно, весь цей список покривається фреймворками та бібліотеками. Ситуації, коли є певний функціонал і його не вдається покрити фреймворком або бібліотекою, трапляються рідко. Проте часто, коли робиш щось складення на UI, стикаєшся з тим, що:

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

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

Опис задачі, в якій ми будемо оптимізувати алгоритм

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

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

Створимо API-сервіс, який на початку роботи вичитує масив елементів, а тоді на кожен запит робить обчислення і повертає дані із середніми за день температурами. Сервіс буде запущений на Node.js. Всі запити будуть опрацьовуватися в Event Loop — це потік у Node.js процесі, який бере з черги запит, опрацьовує його і переходити до наступного. Потік Event Loop може бути тільки один на Node.js процес. Якщо якийсь запит опрацьовується дуже довго, це призводить до того, що в черзі запити накопичуються. З часом їх стає так багато, що ті, які надійшли пізніше, будуть відхилені через timeout, і клієнт отримає відповідь connection refused. Від того, наскільки оптимально написано версію алгоритму, буде залежати, скільки запитів буде опрацьовано, а скільки відхилено. Сервіс розроблятимемо на Nest.js мовою TypeScript.

Запуск сервісу

Вихідний код завантажимо з GitHub . Для запуску потрібно інсталювати Node.js . Після того, як завантажили код, потрібно в корені каталогу запустити команду npm install . Коли всі пакети будуть завантажені, виконаємо команду npm start .

Кожна версія алгоритму буде доступна за адресою увазі localhost:3000/v1 (/v2 /v3...). У відповіді міститимуться середні температури за день, а також час виконання запиту.

Вхідні дані взяті із сервісу OpenWeatherMap і збережені як JSON-файл.

Тестування ефективності

Для оцінювання ефективності запустимо load test:

Тобто загалом буде створен 10 000 запитів, і наше завдання за одну секунду виконувати понад 1000 запитів. Для load test використаємо фреймворк Artillery.

Перший алгоритм

Опис

Почнемо з максимально неоптимального алгоритмом.

  1. Елементи початкової колекції містять годину увазі 2019-01-01 00:10:00 . Створимо нову колекцію (source), елементи якої міститимуть тільки дату увазі 2019-01-01 і температуру.
  2. Тепер, коли у нас є лише дата, можна групувати за нею елементи source. Погруповані елементи збережемо у колекції groupedByDate, кожен елемент якої буде мати поля date та array. У полі array збережемо всі елементи source, які мають однакову дату.
  3. Групувати елементи source будемо так:
    • поки колекція source не порожня, беремо перший елемент (item) і шукаємо в колекції groupedByDate елемент, де поле date рівне item.date;
    • якщо такий елемент знайдено, додаємо в поле array знайденого елемента;
    • якщо такого елемента не існує, то в groupedByDate додаємо новий елемент, який буде містити дату, що дорівнює item.date, а також поле array, що буде містити масив один з елементом — item;
    • видаляємо перший елемент колекції source, оскільки ми його вже опрацювали, і переходимо до першого кроку.
  4. Залишилось знайті середнє арифметичне температур, які вже погруповані за датою. Для цього створимо нову колекцію meanTemperaturesByDate, кожен елемент якої матиме поля date і meanTemperature. У полі meanTemperature запишемо середнє арифметичне значення температур, які містяться в полі array, елементів колекції groupedByDate. Для цього просумуємо їх та поділимо на кількість.
  5. Повертаємо результат, який містить meanTemperaturesByDate.
 // we have a time field '2019-01-01 00:10:00'.
 // to make a grouping by date we need to cut '00:10:00' part, so leave only date.
 // let's create a new collection, which contains temperature and date
 const source = data.map(item => ({
 temperature: item.temperature,
 date: moment(item.time).format('YYYY-MM-DD')
}));

 // in this collection we store items with the same date
 const groupedByDate: { date: string, array: IWeatherItem[] }[] = [];

 // take the first element, process it, and remove from the collection
 // stop processing once collection is empty
 while (source.length > 0) {
 const item = source[0];

 // check if we already have found items with date of the current element
 const = match groupedByDate.find(itemToFind => itemToFind.date === item.date);

 // if found
 if (match) {
 // add the current element to the array, which has elements with the same date
match.array.push(item);

 // otherwise (if no elements with the date we are looking for)
 } else {
 // add new grouping with the current date
groupedByDate.push({
 date: item.date,
 array: [item]
})
}

 // remove the first element, so we can process the next one on the following step
 source.splice(0, 1);
}

 // count mean temperature for items with the same date
 const meanTemperaturesByDate: { date: string, meanTemperature: number }[] =
 groupedByDate.map(item => {
 return {
 date: item.date,
meanTemperature:
 _.sumBy(item.array, item => item.temperature)/item.array.length
}
})

 return new Result data.length, meanTemperaturesByDate, start);

GitHub-репозиторій

Результат виконання

localhost:3000/v1 

{
 "count": 8784,
 "memoryUsed": "19.08 Mb",
 "processingTime": "174ms",
 "pid": 15028,
 "meanTemperaturesByDate": [
{
 "date": "2019-01-01",
 "meanTemperature": 8.441666666666663
},
{
 "date": "2019-01-02",
 "meanTemperature": 5.054166666666666
},
{
 "date": "2019-01-03",
 "meanTemperature": 4.724999999999999
},

Для кожної версії будемо записувати, скільки часу виконується один запит. Це середнє значення для 5 викликів.


 v1 v2 v3 v4 v5 v6 pm2
Response time (single request) ms 174




Load test

У нас загалом 10 000 запитів. У таблиці нижче порівняємо, скільки з них може опрацювати кожна версія і скільки запитів опрацьовується за секунду.


 v1 v2 v3 v4 v5 v6 pm2
Requests completed (10 000 total) 565




Mean response/sec 15.93




Як бачимо, перша версія змогла опрацювати лише 565 запитів із 10 000 (трохи більше як 5%). За секунду — майже 16 запитів. Спробуємо поліпшити ці показники у наступних версіях алгоритмом.

Другий алгоритм. Пошук вузьких місць у програмі

Profiling

Profiling — це процес моніторингу роботи програми, під час якого ми діагностуємо, які частини коду займають найбільше процесорного часу. Саме вони мають бути основною ціллю оптимізації.

Деякі IDE вже мають вбудовані профайлери. Для інших профайлер можна встановити як плагін. Я скористався цим інструментом .

Профайлер працює так:

  1. Ставимо break point у тому місці, де починається процес виконання кодом, який нас цікавить.
  2. Натискаємо кнопку Start Profiling.
  3. Активуємо процес, над яким відбувається профайлінг. У нашому випадку це надсилання запиту на localhost:3000/v1 .
  4. Щойно виконання запиту закінчилося, зупиняємо профайлінг.

Після того як профайлер закінчив роботу, аналізуємо результати. Посортуємо їх за часом виконання:

Як бачимо, непомірно велику кількість процесорного часу займає виклик:

moment(item.time).format('YYYY-MM-DD')

У ньому виокремлюємо дату 2019-01-01 з поля time 2019-01-01 00:10:00. Оскільки moment вміє приймати на вхід безліч форматів даті та часу, то витрачає чимало процесорного часу на ті, щоб проаналізувати рядок з ними, перетворити їх у своє внутрішнє представлення, яке буде дозволяти, наприклад, знайті різницю з іншою датою або перетворити в інший формат, як ми робимо в нашому випадку.

Можемо прискорити виконання, передавши у функцію moment параметр, який вказує, у якому саме форматі у нас надходять дані. Тепер moment вже не буде підбирати формат, а буде використовувати завдань. Початково у нас було 174 мілісекунди, після задання формату вхідного даних отримуємо 150.

Альо формат даних у нас завжди однаковий, і все, що потрібно, це отримати першу частину рядка, що містить дату. То чому замість виклику дорогого в часі методом moment не взяти перших 10 символів рядка? Спробуймо.

const source = data.map(item => ({
...item,
 // date: moment(item.time).format('YYYY-MM-DD')
 // replace moment, since it decrease performance significantly
 date: item.time.substring(0, 10)
}));

GitHub-репозиторій

Результат виконання

localhost:3000/v2 

{
 "count": 8784,
 "memoryUsed": "23.77 Mb",
 "processingTime": "26ms",
 "pid": 23508,
 "meanTemperaturesByDate": [
{
 "date": "2019-01-01",
 "meanTemperature": 8.441666666666663
},
{
 "date": "2019-01-02",
 "meanTemperature": 5.054166666666666
},
{
 "date": "2019-01-03",
 "meanTemperature": 4.724999999999999
},

v1 v2 v3 v4 v5 v6 pm2
Response time (single request) ms 174 26



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

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

Load test


 v1 v2 v3 v4 v5 v6 pm2
Requests completed (10 000 total) 565 2380



Mean response/sec 15.93 48.7



Наш Load test теж демонструє явне поліпшення: з 10 000 запитів обробилося 2380, кількість відповідей за секунду зросла з 15.93 до 48.7.

Третій алгоритм. Оптимізуємо пошук. Як працює Hashmap

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

Розглянємо код, де ми шукаємо елемент за датою:

const = match groupedByDate.find(itemToFind => itemToFind.date === item.date);

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

Усім відомий алгоритм сортування бульбашкою. У ньому є два цикли:

  1. Зовнішній, де ми визначаємо, який елемент є поточним.
  2. Внутрішній, де ми йдемо за всіх елементів до кінця масиву і робимо перестановку, якщо знайдемо менший елемент за поточний.

Алгоритм сортування бульбашкою має алгоритмічну складність О(n2), оскільки для шкірного елемента ми перевіряємо всі наступні елементи.

Що менше значення O, то ефективніший алгоритм. Наприклад, завдяки тому, що алгоритм сортування Quick Sort поділяє масив за певним принципом, він зменшує кількість необхідних порівнянь між елементами. Його складність O(n log(n)). Більше тут .

Повернемось до нашого алгоритму. Як було сказано, складність пошуку елемента за датою дорівнює O(n). Це не є високою складністю, якщо це окрема операція. Але у нас цей пошук відбувається в циклі:

while (source.length > 0) {
 const item = source[0];
 const = match groupedByDate.find(itemToFind => itemToFind.date === item.date);

 // ...
 source.splice(0, 1); // remove the first element 
}

Виходить, щоб погрупувати всі елементи з однаковою датою, ми використовуємо алгоритм зі складністю O(n2), а це вже висока складність.

Бінарний пошук (Binary Search)

Існує алгоритм, складність пошуку якого дорівнює O(log(n)). Він називається «бінарний пошук». Масив, у якому відбуваються пошук, має бути відсортований. Як він працює:

  1. Маємо відсортований масив.
  2. Якщо масив порожній, то елемента не знайдено.
  3. Беремо елемент посередині масиву:
    • якщо він рівний тому, який ми шукаємо, — пошук завершено;
    • якщо він більший від того, який ми шукаємо, — візьмемо лише ліву частину масиву і проводитимемо пошук тільки в ній. Виконаємо крок № 2 лише у цій частині;
    • якщо елемент посередині масиву менший, то візьмемо лише праву частину масиву і виконаємо у ній крок.

Завдяки тому, що на кожному кроці розмір масиву, в якому ми робимо пошук, зменшується вдвічі, отримуємо O(log(n)).

Бінарне дерево пошуку (Binary Search Tree — BSD)

Є структури даних, що призначені для швидкого пошуку. Розглянємо бінарне дерево пошуку.

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

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

У найгіршому випадку нам потрібно O(h) кроків, щоб знайте завдань ключ, де h — висота дерева. Оскільки швидкість пошуку залежить від висоти дерева, потрібно добитися того, щоб у світові додавання нових елементів його висота зменшувалася максимально повільно. Якщо у кожної вершини дерева висота її лівого піддерева відрізняється від висоти правого піддерева на більше ніж на 1, то таке дерево називають збалансованим. Пошук у ньому найоптимальніший. У збалансованому дереві складність пошуку елемента дорівнює O(log(n)).

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

Самозбалансовані бінарні дерева пошуку

Приклади самозбалансованих бінарних дерев пошуку:

АВЛ-дерево (AVL tree)

Червоно-чорне дерево (Red-black tree)

Б-дерево (B tree)

Б-дерево цікаве тім, що вершина може мати кілька значень і з неї виходять більше ніж дві дочірні вершини. Якщо вершина має кілька значень (a, b), то між ними буде піддерево, в якому кожен ключ xn кожної вершини буде a < xn < b. Якщо таке дерево міститиме багато даних, то порівняно з іншими типами бінарних дерев пошуку його висота буде малою. Це важливо тоді, коли робимо пошук по дереву, яке зберігають не в оперативній пам'яті, а в постійній (HDD, SSD). В постійній пам'яті годину доступу до інформації на носії значно довший. Інформація на постійному носії збережена у вигляді неперервних блоків (секторів), розмір яких може становити 4 кБ (залежить від файлової системи та вибраного розміру сектора). Оскільки ми за раз читаємо весь сектор (де записана вершина з кількома ключами), можемо за значно меншу кількість зчитувань з носія зробити обхід по дереву і знайте потрібну вершину.

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

Хеш-таблиця (HashMap)

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

const item = source[index];

Алгоритмічна складність такої операції дорівнює O(1).

Якщо є потреба часто звертатися до елемента певної множини за ID, іменем, датою чи іншим ключем, замість пошуку по масиву можемо використати структуру даних «хеш-таблиця».

const item = hashMap[`2020-01-01`];

Складність доступу до елемента хеш-таблиці дорівнює O(1), тобто така сама, як би ми отримували доступ до елемента за індексом.

Хеш-функція hash(a) = b, призначений для перетворення деякого набору даних a у певний результат фіксованої довжини b . При цьому мають виконуватися дві умови:

  1. Будь-яка, навіть найменша зміна вхідного набору даних a має повністю змінювати результат функції b .
  2. Знаючи лише результат функції b, має бути складно вирахувати оригінальний набір вхідних даних a .

Можливі випадки, коли хеш-функція для різних значень a дає однакові значення b . Такі ситуації називаються колізіями. Що краща функція hash, то менше колізій вона буде створювати.

В основі хеш-таблиці лежить масив. Коли ми робимо вставлення в хеш-таблицю, беремо hash від нашого ключа і зіставляємо результат з позицією у масиві hash(key) = index . Хеш-функція має працювати таким чином, щоб генерувати hash, значення якого буде менше за довжину масиву, і викликати найменше число колізій.

Оскільки будуть з'єднання являтися колізії, нам потрібен механізм, щоб з ними боротися. Таких механізмів є кілька. Розглянємо два з них.

Про перший механізм: якщо у нас виникає колізія, то значення елемента разом з його ключем записуємо у наступну клітинку масиву. Тоді, щоб отримати за ключем елемент, спочатку рахуємо його hash, так отримуємо можливу позицію в масиві. Далі порівнюємо за ключем: якщо вони збіглися, елемент знайдено, якщо ні, беремо наступний і так далі. Для наступних елементів додатково потрібно робити порівняння ключів, бо, якщо вони відрізняються, це означає, що елементи не знайдено.

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

Алгоритм з використанням хеш-таблиці.

Повернемось до нашого сервісу з обчислення середньої температури за день. Ми брали кожен елемент з масиву source і шукали інші елементи за датою у масиві groupedByDate. Як вже з'єднання ясували, такий алгоритм має складність пошуку O(n2):

const groupedByDate: { date: string, array: IWeatherItem[] }[] = [];

 while (source.length > 0) {
 const item = source[0];

 // check if we already have found items with date of the current element
 const = match groupedByDate.find(itemToFind => itemToFind.date === item.date);

Тепер масив groupedByDate замінимо хеш-таблицею. Це дасть змогу замість операції пошуку, складність якої O(n), використати операцію доступу до елемента хеш-таблиці за ключем.

const groupedByDate: { [date: string]: IWeatherItem[] } = {};

 while (source.length > 0) {
 const item = source[0];

 const = match groupedByDate[item.date];

Складність такої операції O(1).

// was: const groupedByDate: { date: string, array: IWearerItem[] }[] = [];
 // hashmap instead of list
 const groupedByDate: { [date: string]: IWeatherItem[] } = {};

 while (source.length > 0) {
 const item = source[0];

 // was:
 // const = match groupedByDate.find(itemToFind => itemToFind.date === item.date);
 // search O(1) instead of O(n)
 const = match groupedByDate[item.date];

 if (match) {
match.push(item);
 } else {
 // was:
 // groupedByDate.push({
 // date: item.date,
 // array: [item]
 // })
 groupedByDate[item.date] = [item];
}

 source.splice(0, 1); // remove the first element 
}

 // get all dates
 const dates = Object.keys(groupedByDate);
 const meanTemperaturesByDate: { date: string, meanTemperature: number }[] =
 // for every date get mean temperature
 dates.map(date => {
 const temperaturesInOneDay = groupedByDate[date];
 return {
date,
meanTemperature:
 _.sumBy(temperaturesInOneDay, item => item.temperature)/temperaturesInOneDay.length
}
})

 return new Result data.length, meanTemperaturesByDate, start);
}

GitHub-репозиторій

Результат виконання

localhost:3000/v3 

{
 "count": 8784,
 "memoryUsed": "18.69 Mb",
 "processingTime": "11ms",
 "pid": 7440,
 "meanTemperaturesByDate": [
{
 "date": "2019-01-01",
 "meanTemperature": 8.441666666666663
},
{
 "date": "2019-01-02",
 "meanTemperature": 5.054166666666666
},
{
 "date": "2019-01-03",
 "meanTemperature": 4.724999999999999
},

Як бачимо, середній час виконання одного запиту скоротився з 26 до 11 мілісекунд.


 v1 v2 v3 v4 v5 v6 pm2
Response time (single request) ms 174 26 11


Load test


 v1 v2 v3 v4 v5 v6 pm2
Requests completed (10 000 total) 565 2,380 3,960


Mean response/sec 15.93 48.7 92.76


Після запуску навантажувального тесту видно, що кількість виконаних запитів зросла з 2380 до 3960. Це все одне тільки 39% успішних запитів зі 10 000. Кількість опрацьованих запитів за секунду зросла з 48.7 до 92.76. Наша ціль — понад 1000 за секунду, — все ще дуже далека, тому будемо продовжувати оптимізацію.

Четвертий алгоритм. Як працюють зв'язаний список (linked list), масив (array) та список (list)

Зв'язаний список (linked list)

Зв'язаний список — колекція у вигляді ланцюжка, де кожен елемент містить певний об'єкт і має вказівник на наступний елемент (next). Перший елемент списку називають його головою (head), а останній — хвіст (tail).

У зв'язку язаному списку ми не можемо одразу прямо отримати елемент за індексом (index), оскільки елементи не розміщені послідовно в пам'яті, а розкидані в різних її частинах. Починаючи з head, ми послідовно переміщаємося з одного елемента на інший, використовуючи next. Нам потрібно зробити стільки кроків, скільки рівне значення index. Тобто якщо в масиві у нас складність доступу за індексом рівна O(1), то у зв'язку язаного списком аж O(n).

Додавання нового елемента працює так:

  1. Якщо додаємо новий елемент на початку списку, то next нового елемента задаємо рівному того елементу, який зараз head, а після цього робимо новий елемент head.
  2. Якщо додаємо вкінці, то next елемента, який зараз tail, задаємо рівним новому елементу, а тоді новий елемент робимо tail.
  3. Якщо ми додаємо елемент в довільну позицію index, то нам треба зупинитися на елементі (index — 1) — previous, прочитати його поле next і записати це значення в next нового елемента, а тоді в поле next елемента previous записати новий елемент.

Видалення відбувається аналогічним чином.

Характеристики зв'язку язаного списком:

Масив (array)

Масивом називають множину даних фіксованої довжини, які розміщені послідовно в пам'яті.

Основні характеристики:

Ті, що JavaScript називають масивом (array), насправді є списком (list), оскільки його довжина може змінюватися.

Список (list)

В основі списку лежить масив. Альо довжина списку може змінюватися.

Як це працює:

  1. Створюється масив. У нього є дві властивості: довжина (length) і місткість (capacity). Довжина показує, скільки елементів вже заповнили виділений простір пам'яті під масив. Місткість — скільки ще може вміститися елементів до того моменту, як масив доведеться збільшувати.
  2. Якщо додаємо новий елемент і length > capacity, то тоді створюємо більший масив, копіюємо в нього дані з попереднього масиву і додаємо новий елемент. У різних імплементаціях новий масив має різну місткість. Він може бути більший на половину від своєї попередньої capacity, а може і подвоїти її. Вісь чому корисно наперед задавати capacity, якщо вона точно відома. Розширення списку є дорогою операцією.
  3. Якщо ми видаляємо багато елементів зі списку, то немає змісту тримати виділеною велику ділянку пам'яті, яка не використовується. Тому якщо length < 0.75 capacity (або 0,5 залежно від імплементації), то створюється менший масив і у нього копіюються елементи з попередньою.
  4. Після копіювання попередній масив видаляється відразу (C, C++) або під годину Garbage Collection.

Характеристики списком:

  1. Пам'ять виділяється наперед.
  2. Довжина списку може змінюватися:
    • якщо новий елемент додається в кінець списку (append, push), то амортизаційна складність алгоритму буде Про(1). Амортизаційна, бо в найгіршому випадку, коли список збільшуватиметься, складність буде O(n). Оскільки це дуже песимістична оцінка (ця операція відбуватиметься досить рідко), то беруть тієї випадок, який буде відбуватися майже весь час, а саме запис елемента у незайняте місце масиву, тобто зі складністю O(1);
    • якщо новий елемент видаляється з кінця списку (pop), то амортизаційна складність дорівнює O(1);
    • якщо новий елемент додається на позицію index, то складність буде O(n). Така складність зумовлена тім, що всі елементи, в яких позиція більша за позицію index, треба перенести на одну позицію далі в кінець списку. Також якщо вільного місця немає, потрібно створити новий масив і зробити копіювання;
    • якщо новий елемент видаляється з позиції index, то складність буде O(n), оскільки всі елементи з позицією більшою за index треба посунути на початок масиву або скопіювати в новий масив, якщо length < 0.75 capacity.
  3. Елемент списку можна отримати за його індексом відразу O(1).

Оптимізований алгоритм

Отже, видалення елемента зі списку є дорогою операцією. Ми її виконуємо, коли проходимось по колекції source:

while (source.length > 0) {
 const item = source[0];
...
 source.splice(0, 1); // remove the first element 
}

Щоб кожного разу не видаляти перший елемент, будемо проходити по кожному елементу колекції source, не змінюючи її.

// was: while (source.length > 0) {
 source.forEach(item => {
 const = match groupedByDate[item.date];

 if (match) {
match.push(item);
 } else {
 groupedByDate[item.date] = [item];
}

 // was: source.splice(0, 1); remove the first element 
 // remove element from the list is an expensive operation
});

GitHub-репозиторій

Результат виконання

localhost:3000/v4 

{
 "count": 8784,
 "memoryUsed": "24.05 Mb",
 "processingTime": "5ms",
 "pid": 19488,
 "meanTemperaturesByDate": [
{
 "date": "2019-01-01",
 "meanTemperature": 8.441666666666663
},
{
 "date": "2019-01-02",
 "meanTemperature": 5.054166666666666
},
{
 "date": "2019-01-03",
 "meanTemperature": 4.724999999999999
},

Попередня версія алгоритму опрацьовувала запит 11 мілісекунд, нова версія робить це за 5.


 v1 v2 v3 v4 v5 v6 pm2
Response time (single request) ms 174 26 11 5

Load test


 v1 v2 v3 v4 v5 v6 pm2
Requests completed (10 000 total) 565 2380 3960 4940

Mean response/sec 15.93 48.7 92.76 213.07

Як видно за результатами навантажувального тесту, ми успішно опрацювали майже половину запитів. За секунду нова версія алгоритму опрацьовує 213 запитів, порівняйте з 92 запитами попередньої версії.

Алгоритм п'ятий. Позбуваємося зайвих циклів і виділення пам'яті

Шукаємо зайві операції

У попередній версії алгоритму ми позбулися видалення елементів з колекції source. Оскільки тепер source ми не змінюємо, а колекція data відрізняється від source лише тім, що в її елементів немає поля date, можемо обійтися без source. Будемо проходити за data, обчислювати дату, використовуючи поле time шкірного елемента. І маючи ці дані, групувати елементи в хеш-таблиці groupedByDate.

 // was:
 // const source = data.map(item => ({
 // ...item,
 // date: item.time.substring(0, 10)
 // }));

 const groupedByDate: { [date: string]: IWeatherItem[] } = {};

 // was: source.forEach(item => {
 data.forEach(item => {
 const date = item.time.substring(0, 10);

 // was:
 // const = match groupedByDate[item.date];

 // if (match) {
 // match.push(item);
 // } else {
 // groupedByDate[item.date] = [item];
 // }

 // less code
 // if groupedByDate[date] is not undefined, set self, otherwise set an empty list
 groupedByDate[date] = groupedByDate[date] || []; 
groupedByDate[date].push(item);
})

GitHub-репозиторій

Результат виконання

localhost:3000/v5 

{
 "count": 8784,
 "memoryUsed": "14.21 Mb",
 "processingTime": "2ms",
 "pid": 7992,
 "meanTemperaturesByDate": [
{
 "date": "2019-01-01",
 "meanTemperature": 8.441666666666663
},
{
 "date": "2019-01-02",
 "meanTemperature": 5.054166666666666
},
{
 "date": "2019-01-03",
 "meanTemperature": 4.724999999999999
},

Оскільки вдалося обійтися без створення додаткової колекції source, ми заощадили процесорний час на виділенні великого об'єднання об'єму пам'яті та додаванні елементів. Це позитивно відбилося на продуктивності програми. Якщо порівнювати з попередньою версією, годину виконання одного запиту скоротився з п'яти мілісекунд до двох.


 v1 v2 v3 v4 v5 v6 pm2
Response time (single request) ms 174 26 11 5 2

Load test


 v1 v2 v3 v4 v5 v6 pm2
Requests completed (10 000 total) 565 2380 3960 4940 7860
Mean response/sec 15.93 48.7 92.76 213.07 594.55

Результати навантажувального тестування показують, що ми успішно опрацювати 78% запитів. За секунду опрацьовуємо 594 запити.

Алгоритм шостий. Зведення до загального рішення. Паралельне виконання

Загальні рішення

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

Коли розбиваємо на простіші задачі, пам " ятайте, що різні задачі будуть мати рішення різної алгоритмічної складності. Треба комбінувати так, щоб у кінцевому результаті складність алгоритму була найнижча. Не варто забувати і про пам'ять: