Опановуємо основи алгоритмів, або Як прискорити код з 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 з них — це вебсервери, решта — сервери з базами даних, розподіленими кешами та системами обміну повідомленнями. Зосередимось на вебсерверах. Припустимо це віртуальні комп’ютери з
Це добре, коли є система, яку можна оптимізувати, зекономивши гроші. Але бувають випадки, що систему розробили, але не можуть випустити в реліз, бо вона не витримує навантаження. Тобто, звісно, є варіант її масштабувати, але це надзвичайно дорого. Проблема таких систем у тому, що там занадто пізно почали навантажувальне тестування, не робили профайлінг продуктивності програми й не шукали вузьких місць на етапі розробки.
Схожий випадок був на одному з проєктів, для якого я проводив консультацію. Команда прийшла з проблемою, що їй не вдається масштабуватися. Система під високим навантаженням вже за кілька секунд переставала відповідати. Як виявилось, причиною стало те, що на API виконувалося багато обчислень, але за неоптимальними алгоритмами. Система показувала себе добре на етапі розробки, бо тоді її навантаження становило не більше як 10 запитів за секунду. Коли під час навантажувального тестування пішли тисячі конкурентних запитів — система захлинулася.
Якщо говорити про алгоритми в контексті фронтенду, то наскільки оптимально написаний код, настільки плавний і приємний буде досвід користувача під час роботи з програмою. Деякі приклади оптимізації UI:
- оптимізовані оновлення DOM (тільки частини UI, які справді потребують оновлення);
- правильна робота та організація стейту: нормалізація даних; селектори, які вміють кешувати денормалізовані дані або дані, які потребують розрахунків; забезпечення immutability;
- Memoisation — кешування в пам’яті компонентів, які часто повторно використовуються;
- Virtual Scroll — показ тільки тієї частини контенту, яку бачить користувач у певний момент;
- Preload контенту і стратегії кешування запитів з API.
Звісно, весь цей список покривається фреймворками та бібліотеками. Ситуації, коли є певний функціонал і його не вдається покрити фреймворком або бібліотекою, трапляються рідко. Проте часто, коли робиш щось складне на UI, стикаєшся з тим, що:
- вебсторінка фризиться;
- минає багато часу, поки відбудеться перший рендер сторінки;
- FPS дуже низький, коли скролиш сторінку або починаєш з нею якось взаємодіяти.
Просто завантажити фреймворк або бібліотеку не завжди достатньо. Потрібно ще навчитися з ними працювати. Це набагато легше, якщо є гарна алгоритмічна база.
Хоча розуміння алгоритмів і структур даних не завжди в пріоритеті розробників, незнання базової теорії алгоритмів спричиняє серйозні ризики для проєкту. У свою чергу, знання алгоритмів підвищує ефективність роботи, оскільки мозок генеруватиме більше рішень, з-поміж яких можна вибрати краще та простіше водночас.
Опис задачі, в якій ми будемо оптимізувати алгоритм
Вибір завдання виявився не таким легким, як я вважав із самого початку. Потрібна була задача, яка легка для розуміння, до якої можна придумати кілька достатньо різних рішень, в кожному з яких розкривається той чи інший аспект алгоритмів чи структур даних. Крім того, кожне рішення має видавати відчутно кращий результат за попередній.
Я взяв за основу проблему з великою кількістю обчислень на 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:
- Одночасно приходять 1000 користувачів.
- Кожен з них робить по 10 запитів.
Тобто загалом буде створено 10 000 запитів, і наше завдання за одну секунду виконувати понад 1000 запитів. Для load test використаємо фреймворк Artillery.
Перший алгоритм
Опис
Почнемо з максимально неоптимального алгоритму.
- Елементи початкової колекції містять час виду
2019-01-01 00:10:00. Створимо нову колекцію (source), елементи якої міститимуть тільки дату виду2019-01-01 і температуру. - Тепер, коли у нас є лише дата, можна групувати за нею елементи source. Погруповані елементи збережемо у колекції groupedByDate, кожен елемент якої буде мати поля date та array. У полі array збережемо всі елементи source, які мають однакову дату.
- Групувати елементи source будемо так:
- поки колекція source не порожня, беремо перший елемент (item) і шукаємо в колекції groupedByDate елемент, де поле date рівне item.date;
- якщо такий елемент знайдено, додаємо в поле array знайденого елемента;
- якщо такого елемента не існує, то в groupedByDate додаємо новий елемент, який буде містити дату, що дорівнює item.date, а також поле array, що буде містити масив з один елементом — item;
- видаляємо перший елемент колекції source, оскільки ми його вже опрацювали, і переходимо до першого кроку.
- Залишилось знайти середнє арифметичне температур, які вже погруповані за датою. Для цього створимо нову колекцію meanTemperaturesByDate, кожен елемент якої матиме поля date і meanTemperature. В поле meanTemperature запишемо середнє арифметичне значення температур, які містяться в полі array, елементів колекції groupedByDate. Для цього їх просумуємо та поділимо на кількість.
- Повертаємо результат, який містить 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);
Результат виконання
{
"count": 8784,
"memoryUsed": "19.08Mb",
"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 вже мають вбудовані профайлери. Для інших профайлер можна встановити як плагін. Я скористався цим інструментом.
Профайлер працює так:
- Ставимо break point у тому місці, де починається процес виконання коду, який нас цікавить.
- Натискаємо кнопку Start Profiling.
- Активуємо процес, над яким відбувається профайлінг. У нашому випадку це надсилання запиту на localhost:3000/v1.
- Щойно виконання запиту закінчилося, зупиняємо профайлінг.
Після того як профайлер закінчив роботу, аналізуємо результати. Посортуємо їх за часом виконання:
Як бачимо, непомірно велику кількість процесорного часу займає виклик:
moment(item.time).format('YYYY-MM-DD')
У ньому виокремлюємо дату
Можемо прискорити виконання, передавши у функцію 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)
}));
Результат виконання
{
"count": 8784,
"memoryUsed": "23.77Mb",
"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) — тобто скільки елементів, стільки перевірок потрібно зробити в найгіршому випадку, щоб знайти заданий (або сказати, що множина його не містить в собі).
Усім відомий алгоритм сортування бульбашкою. У ньому є два цикли:
- Зовнішній, де ми визначаємо, який елемент є поточним.
- Внутрішній, де ми йдемо по всіх елементах до кінця масиву і робимо перестановку, якщо знайдемо менший елемент за поточний.
Алгоритм сортування бульбашкою має алгоритмічну складність О(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)). Він називається «бінарний пошук». Масив, у якому відбуваються пошук, має бути відсортований. Як він працює:
- Маємо відсортований масив.
- Якщо масив порожній, то елемента не знайдено.
- Беремо елемент посередині масиву:
- якщо він рівний тому, який ми шукаємо, — пошук завершено;
- якщо він більший від того, який ми шукаємо, — візьмемо лише ліву частину масиву і проводитимемо пошук тільки в ній. Виконаємо крок № 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. При цьому мають виконуватися дві умови:
- Будь-яка, навіть найменша зміна вхідного набору даних a має повністю змінювати результат функції b.
- Знаючи лише результат функції 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);
}
Результат виконання
{
"count": 8784,
"memoryUsed": "18.69Mb",
"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).
Додавання нового елемента працює так:
- Якщо додаємо новий елемент на початку списку, то next нового елемента задаємо рівному тому елементу, який зараз head, а після цього робимо новий елемент head.
- Якщо додаємо вкінці, то next елемента, який зараз tail, задаємо рівним новому елементу, а тоді новий елемент робимо tail.
- Якщо ми додаємо елемент в довільну позицію index, то нам треба зупинитися на елементі (index — 1) — previous, прочитати його поле next і записати це значення в next нового елемента, а тоді в поле next елемента previous записати новий елемент.
Видалення відбувається аналогічним чином.
Характеристики зв’язаного списку:
- пам’ять наперед не виділяється;
- довжину можна змінити: додавання або видалення нового елемента на початку або в кінці списку O(1) чи додавання або видалення елемента в довільному місці списку O(n);
- елемент зв’язаного списку можна отримати через index кроків, проходячи список від голови до потрібного елемента O(n).
Масив (array)
Масивом називають множину даних фіксованої довжини, які розміщені послідовно в пам’яті.
Основні характеристики:
- пам’ять виділяється наперед;
- довжину масиву змінити не можна;
- елемент масиву можна отримати за його індексом одразу O(1).
Те, що JavaScript називають масивом (array), насправді є списком (list), оскільки його довжина може змінюватися.
Список (list)
В основі списку лежить масив. Але довжина списку може змінюватися.
Як це працює:
- Створюється масив. У нього є дві властивості: довжина (length) і місткість (capacity). Довжина показує, скільки елементів уже заповнили виділений простір пам’яті під масив. Місткість — скільки ще може вміститися елементів до того моменту, як масив доведеться збільшувати.
- Якщо додаємо новий елемент і length > capacity, то тоді створюємо більший масив, копіюємо у нього дані з попереднього масиву і додаємо новий елемент. У різних імплементаціях новий масив має різну місткість. Він може бути більший на половину від своєї попередньої capacity, а може і подвоїти її. Ось чому корисно наперед задавати capacity, якщо вона точно відома. Розширення списку є дорогою операцією.
- Якщо ми видаляємо багато елементів зі списку, то немає змісту тримати виділеною велику ділянку пам’яті, яка не використовується. Тому якщо length < 0.75 capacity (або 0,5 залежно від імплементації), то створюється менший масив і у нього копіюються елементи з попереднього.
- Після копіювання попередній масив видаляється відразу (C, C++) або під час Garbage Collection.
Характеристики списку:
- Пам’ять виділяється наперед.
- Довжина списку може змінюватися:
- якщо новий елемент додається в кінець списку (append, push), то амортизаційна складність алгоритму буде О(1). Амортизаційна, бо в найгіршому випадку, коли список збільшуватиметься, складність буде O(n). Оскільки це дуже песимістична оцінка (ця операція відбуватиметься досить рідко), то беруть той випадок, який буде відбуватися майже весь час, а саме запис елемента у незайняте місце масиву, тобто зі складністю O(1);
- якщо новий елемент видаляється з кінця списку (pop), то амортизаційна складність дорівнює O(1);
- якщо новий елемент додається на позицію index, то складність буде O(n). Така складність зумовлена тим, що всі елементи, в яких позиція більша за позицію index, треба перенести на одну позицію далі в кінець списку. Також якщо вільного місця немає, потрібно створити новий масив і зробити копіювання;
- якщо новий елемент видаляється з позиції index, то складність буде O(n), оскільки всі елементи з позицією більшою за index треба посунути на початок масиву або скопіювати в новий масив, якщо length < 0.75 capacity.
- Елемент списку можна отримати за його індексом відразу 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
});
Результат виконання
{
"count": 8784,
"memoryUsed": "24.05Mb",
"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);
})
Результат виконання
{
"count": 8784,
"memoryUsed": "14.21Mb",
"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 запити.
Алгоритм шостий. Зведення до загального рішення. Паралельне виконання
Загальні рішення
Завдання групування елементів колекції за певним ключем є дуже поширеною. Пошук середнього арифметичного також. Для таких загальних тасків існує чимало бібліотек, які вже мають імплементовані рішення. І вони дуже ефективні. Найпростіший спосіб написати ефективне розв’язання складної задачі — це розбити її на менші задачі так, щоб кожна з них могла бути вирішена загальним способом. Далі знайти в бібліотеці метод, де цей спосіб імплементований. Тоді можемо складний алгоритм будувати блоками, комбінуючи виклики різних методів бібліотеки.
Коли розбиваємо на простіші задачі, пам’ятайте, що різні задачі будуть мати рішення різної алгоритмічної складності. Треба комбінувати так, щоб у кінцевому результаті складність алгоритму була найнижча. Не варто забувати і про пам’ять:
- Уникайте того, щоб проміжні результати залишалися після того, як алгоритм закінчив роботу. Це призводить до memory leaks (витоків пам’яті). Вони з часом забирають увесь вільний простір пам’яті, і програма аварійно припиняє роботу.
- Якщо в пам’яті є важкі об’єкти (малюнки, фрагменти відео, великі масиви даних), то намагайтеся їх передавати з методу в метод, не створюючи копій.
- Робіть сервіси так, щоб вони були stateless: не тримали в пам’яті дані про сесію між запитами.
У цьому прикладі я використав бібліотеку lodash. Вона містить методи groupBy та meanBy. Застосуймо їх і спростімо код алгоритму.
// was:
// const groupedByDate: { [date: string]: IWeatherItem[] } = {};
// data.forEach(item => {
// const date = item.time.substring(0, 10);
// groupedByDate[date] = groupedByDate[date] || [];
// groupedByDate[date].push(item);
// })
const groupedByDate: { [day: string]: IWeatherItem[] } =
_.groupBy(data, item => item.time.substring(0, 10));
const dates = Object.keys(groupedByDate);
const meanTemperaturesByDate: { date: string, meanTemperature: number }[] =
dates.map(date => {
const temperaturesInOneDay = groupedByDate[date];
return {
date,
// was:
// _.sumBy(temperaturesInOneDay, item => item.temperature) / temperaturesInOneDay.length
meanTemperature: _.meanBy(temperaturesInOneDay, item => item.temperature)
}
})
Якщо зараз знову запустити програму, то результати її виконання будуть такі самі, як у попередній версії, але код став лаконічніший і простіший для сприйняття.
Розпаралелення задач
Крім того, що можемо ділити складну задачу на простіші, можемо виділяти в алгоритмі незалежні процеси та виконувати їх паралельно. Найпростіший приклад: наш сервіс отримує дані з сервісів А та Б. Дані ніяк не залежать одні від одних. Замість того, щоб спочатку зробити запит на сервіс А, дочекатися відповіді та зробити запит на сервіс Б, краще виконати два запити одночасно і дочекатися, коли відповідь прийде від обох.
Так само варто розбивати великі об’єми даних на менші частини й паралельно проводити над ними обчислення. Далі всі часткові результати об’єднуємо в один.
Є таке поняття, як утилізація процесорного часу. Вона показує, наскільки процесор завантажений під час роботи. Наприклад, у нас вже є добре оптимізована програма. Ми її запускаємо і бачимо, що
Node.js асинхронно опрацьовує запити в одному потоці. Ми не можемо створити ще один потік, але можемо запустити ще один Node.js-процес, який паралельно буде обробляти запити.
Найпростіше це реалізувати через менеджер процесів. Він створюватиме декілька Node.js-процесів для обробки запитів, а також слугуватиме як load balancer, розподіляючи запити між цими процесами. У цьому прикладі я використав PM2, за допомогою якого запустив два паралельних Node.js-процеси.
Результат виконання з PM2 (два паралельних процеси)
{
"count": 8784,
"memoryUsed": "17.03Mb",
"processingTime": "2ms",
"pid": 21840,
"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 | 11 | 5 | 2 | 2 |
Load test
| v1 | v2 | v3 | v4 | v5 | v6 pm2 | |
| Requests completed (10 000 total) | 565 | 2380 | 3960 | 4940 | 7860 | 10 000 |
| Mean response/sec | 15.93 | 48.7 | 92.76 | 213.07 | 594.55 | 1189.06 |
Зараз у нас запущено два паралельних Node.js-процеси, навантаження між ними однаково розподіляється. Це дало змогу виконати всі 10 000 запитів, які згенерував load test. За секунду ми обробляємо понад 1 100 запитів. Ціль досягнута.
Підсумки
Як бачимо, основи алгоритмів — це не така уже й складна річ. Їхнє розуміння допоможе бачити ширше коло рішень для задач, прогнозувати споживання процесорного часу та пам’яті програмами, розробляти системи, які краще та ефективніше використовують обчислювальні ресурси. Більш глибоке розуміння алгоритмів вимагає деяких інвестицій ваших зусиль і часу. Ресурси, які я можу порекомендувати:
- лекції Принстонського університету;
- лекції на Coursera від Принстонського університету.
