Бази даних і структури даних / крок 02
Чому алгоритми важливі — розберемо на прикладі
Про що це відео
Замість сухої теорії автор наживо кодить буденну задачу — злиття масиву повідомлень із масивом користувачів, щоб додати кожному повідомленню username, — і аналізує її крізь призму алгоритмічної складності. Наївна версія викликає users.find() усередині циклу по повідомленнях, тобто O(M × U); оптимізована спершу будує хеш-мапу за id користувача і зводить усе до O(M + U). Далі він бенчмаркає пошук по масиву на 100 000 елементів (код на його GitHub, посилання в описі): Array.find проти Array.includes проти бінарного пошуку, написаного ним на чистому JavaScript, — і бінарний пошук на чистому JS обганяє навіть includes, реалізований на C++, бо O(log n) завжди перемагає O(n), щойно дані виростають. Наприкінці він проєктує це прямо на індекси в базах даних: запит без індексу — це той самий лінійний перебір, а індекс дає поведінку на кшталт бінарного пошуку по відсортованій структурі (на практиці — збалансоване B-дерево / B+ дерево, а не відсортований масив).
Головне
- Алгоритмічна складність — про те, як обсяг роботи росте з розміром вхідних даних, а не про «сиру» швидкість мови: функція O(n²) залишається квадратичною і на JavaScript, і на C++ — при 10× більших даних отримуєш ~100× більше операцій, «і з коду не очевидно, чому все стало повільним».
- Приклад злиття в цифрах: 2 000 повідомлень × 100 користувачів ≈ 200 000 операцій для версії з вкладеним
findпроти ~2 100 для версії з хеш-мапою (побудова мапи за O(U), потім O(1) на кожне повідомлення завдяки мапам на основі хешування). Виправлення додало лише ~6 рядків коду. - Бенчмарк-сюрприз №1:
includes(нативний цикл на C++) швидший заfind(який викликає JS-колбек на кожен елемент) приблизно у 23 рази — константи теж мають значення. - Бенчмарк-сюрприз №2: бінарний пошук на чистому JS обганяє C++-ний
includes, бо він O(log n). На 100 мільйонах елементів лінійні перебори повзуть, а бінарний пошук відповідає за частки мілісекунди — «на ~100 мільярдах елементів лінійному перебору треба ~100 мільярдів операцій; бінарному пошуку — приблизно один додатковий крок на кожне подвоєння даних». - Бінарний пошук вимагає відсортованого масиву, а сортування дороге — але якщо відсортувати один раз і шукати 100 разів, це окупається з лишком.
- Саме це робить база даних: без індексу MySQL/PostgreSQL лінійно сканують усі рядки; індекс — це відсортована структура, по якій рушій може шукати бінарно. Реальні бази використовують збалансоване B-дерево (B+ дерево, бо воно ще й підтримує range-сканування), яке зберігає O(log n) на пошук — 1 000 рядків чи 10 мільйонів, запит тримається близько мілісекунди.
- Фінальний бенчмарк злиття на 1 000 користувачів × 1 000 повідомлень показав приблизно 60× різниці — і це важливо навіть на фронтенді; у Python без JIT повільна версія боліла б ще ~у 10 разів сильніше.