Чому алгоритми важливі? Розберемо на прикладі

Як зробити код швидшим?
Чому індекси прискорюють базу даних?
Що таке алгоритмічна складність?
Про це все з прикладами коду.
Приклади коду з відео - github.com/koorchik/jabascrip...
Станьте спонсором цього каналу: / @aboutprogramming
Допоможіть каналу розвиватися й отримуйте доступ до ексклюзивного контенту.
Зміст відео:
0:00 - Вступ
1:02 - Задача про юзерів
5:30 - Алгоритмічна складність
10:55 - Задача з пошуком
19:21 - Як індекси допомогають базі даних
21:34 - Задача про юзерів (бенчмарк)
23:06 - Що ще цікаво почути?
🏠 Мої соцмережі:
Жабаскрипт в телеграмі - t.me/jabascript
Я в Твітер - / viktorturskyi
Мій Linkedin - / turskyi
#programming #javascript #codereview #програмування #українською

[@arthur_white30]

Готовий дивитись далі про алгоритми та архітектуру. Дуже корисно, тому що пояснюєшь на пальчях, а не на 100 сторінок тексту

[@viloker5347]

Дуже класно пояснюєте, більше би таких відео про алгоритми

[@milabibik9318]

Дякую за такий корисний контент! Дуже класна подача

[@yehorishtvan3802]

дуже круто цікаво що саме практичні приклади.

[@lev_vasyok]

В тебе дар пояснювати все дуже доступно, відразу помітно що розумієш все зсередини, а не поверхнево, окремо респект за Український контент🔥 Підписався і друзям пошерив твій канал, так тримати, все буде Україна💛💙

[@AboutProgramming]

Дякую! Мотивує розвивати канал :)

[@user-rm7oz4xu3k]

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

[@user-fy5ei7im3p]

Те, що треба👍 Дякую!

[@user-gywunrl]

Оце вже пішла жара! Крутий контент, дякую. Хочется бачити якісний контент по алгоритмах, бо для багатьох це складна тема.

[@user-ke2on2ju8m]

супер ) дякую за чітке та наглядне пояснення!

[@vladyslavkarpenko9372]

Чудові лаконічні приклади з дійсних ситуацій, без foo/bar🤝🏻 Успіху в розвитку каналу та досягнення цілей що собі ставили при його започаткуванні!

[@turbosega]

Дуже гарний контент. Цікаво! Дякую.

[@oleksandrlesiuk6239]

Класний контент, дякую

[@user-fu5ff6zq7m]

Хоч вивчаю Python, але все зрозуміло, дуже гарно подається інформація, дякую за контент))

[@etniqa3638]

Да, круто. Ніколи це не вчив ніде, але з якихось інших відосіків шарю в цьому. Круть )

[@user-fb2hw9jo1m]

Клас згадав, що вчив колись, дякую.

[@pavel7930]

Формат подачі матеріалу легкий і зрозумілий! Дякую! Продовжуйте канал буде дуже крутий!

[@oleksiiderkach4840]

Дякую за відео!

[@MykhSerh]

Дуже класне відео! Продовжуй, так тримати!

[@voltstas]

Дякую! Чекаю на більше таких відео

[@p00ps1q]

Шок контент, я тепер зміню те як я код пишу. Дякую!

[@AdminAdmin-sl2qf]

❤❤❤❤❤❤❤❤

[@SuperBogdanek]

супер доступно.

[@nicknick8884]

Дякую

[@zhen1asemen1uk]

Прикольно і цікаво

[@OleksandrKorshunov]

Дуже жирний контент! Дякую! Так тримати! Ще як варіант, хотілося б побачити порівняння різних алгоритмів і послухати де краще які використовувати.

[@vovabortnyak721]

Тема про алгоритми прям топ

[@user-di5sk7td9m]

Спасибо большое за видео

[@howtosimple_]

Чувак, ти так круто розказуєш, дай я тебе обніму)))

[@AboutProgramming]

😁

[@user-wp3qp3zu6p]

Дуже подобається формат подачі та конент. Цікаво було б послухати від тебе про архітектурні паттерти та приклади реалізації. Дякую)

[@mashin4777]

Ввважаю, що ти геній, там де потрібно надихати та пояснювати

[@Deto4k]

Комент для підтримки українського контенту. Більше алгоритмів богу алгоритмів!

[@KuzyoYaroslav]

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

[@oleksandrkazimirov]

крута робота та подача матеріалу, дякую

[@andriyleliv4608]

Спасибі велике! Все зрозуміло - не треба деталізувати. Цікаво більше почути про структури даних та інші відомі алгоритми і їх рішення на JS.

[@AboutProgramming]

Зроблю ще пару відео по алгоритмах точно. Й спробую на реальних прикладах розібрати

[@user-gc1up4yy2h]

Про мердж двох масивів дуже цікаво! І практично. Дякую Бінарний та інтерполяційний пошук вже знав, тому просто повторив матеріал. А мердж, це прям відкриття

[@asholok]

Вікторе Віталійовичу, це нереально крутий безкоштовний контент. Дякую. В свій час я платив не малі гроші на курсах за таку інформацію. Хай квітне український youtube! P.S Можна ще зауважити що в оптимізованому варіанті збільшиться N по пам'яті.

[@AboutProgramming]

Дякую дякую) Так, те часто обмін CPU на RAM

[@usertyfoon]

Клас!!! Розклав дуже наочно і зрозуміло!! Індекси в БД це бінарний пошук, принцип роботи бінарного пошуку - стали для мене відкриттям)

[@Feasull]

Дуже цікаво і зрозуміло по алгоритмам, вже йду шукати чи є ще таке на каналі)) якщо нема то треба додати ;)

[@velichkoivan]

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

[@AleksanderBabayev]

Мені подобається. Продовжуй. Можна занурюватися ще глибше :).

[@Vladyslav_Sliusar]

Було цікаво та все зрозуміло, дяка)

[@alexeylysenko7380]

Дякую за відео! Було б цікаво почути про різні алгоритми та структури данних!

[@zoryamba]

Чудово! Дякую.

[@olehhryshchuk4189]

Дуже дякую за контент.

[@leetcodeUA]

Дякую! Простими і та доступними словами із наведенням прикладів для перевірки теорії! Круто!

[@razbeykoff]

дякую за корисний контент! Підписався

[@andrew_kit]

Це дуже гарне відео та пояснення. Також дякую за мотивацію грокати алгоритми

[@mrart5498]

Класс! Дякую за випуски :)

[@urchuk2006]

Дуже цікаво, дякую! Продовжуйте в тому ж дусі

[@MrPotapovV]

Дякую за відео

[@levmisiliuk6436]

Йооо, це дуже круто, дякую тобі зараз стало зрозуміло чому навіть frontend розробники мають вивчати алгоритми

[@user-nc6ji1tj7k]

Дуже класний контент, продовжуйте , у Вас все вийде) Хоч не знаю JS, але наче зрозуміло)

[@user-ux8yp3si4d]

Дякую за контент. Пропоную тему для відео таку як дебагінг, з зануренням в стек виклику та особливості дебагінгу асинхронних функцій. В ідеалі на прикладі хром дев тулзів 🦾

[@AboutProgramming]

Тут головне підібрати гарний приклад, що не так просто)

[@user-ux8yp3si4d]

Згоден, взагалі цю тему всі оминають але вона досить важлива, бо багато з нас дебажать на рівні console.log )

[@AboutProgramming]

@@user-ux8yp3si4dта я сам в більшості випадків дебажу через console.log, тільки часом запускаю дебагер 😄 але звісно бувають ситуації, коли без дебагера нікуди

[@average-user9]

ех, крутий канал, дякую:) здається я починаю розуміти, як вимірюється складність моїх пошуків по масивам на фронтенді і що означають ці O(n), дякую!)

[@this_is_data]

Наскільки ж я радий, що я потрапив на Вас у Доу Подкасті❤❤❤

[@alexanonymous5823]

ого оце контент, велике спасибі! дуже дуже дякую

[@ihor-pidhornyi]

Круто пояснюєте, дуже приємно вас слухати. Думаю, що варто ще окрім Time Complexity нагадати про Space Complexity, тобто незважаючи на те, що в нас Time Complexity в другому варіанті мерджа стала O(n+m), то ми використовуємо O(n) Space Complexity, для того щоб отримати мапу юзерів.

[@AboutProgramming]

Дякую за відгук! 🙂 Так, гарне доповненя. По суті, це обмін time complexity на space complexity

[@yuriinadilnyi3029]

Просто, зрозуміло і круто)

[@user-lc7cz2ks6i]

👍👍👍👍

[@yuliasereda5671]

відео суперове. якщо хтось хоче почитати книжечку, то "Грокаєм алгоритми" непогано описує про О від н (там правда приклади на пайтоні здається, але то нічьо)

[@DenKondratiuk]

Це просто першокласний контент! Респект! Так тримати!

[@romkalily]

Дуже круто, було б круто почути за індекси і дерева подробніше Бо це те що дійсно зустрічається:) Круті відео!!!

[@AboutProgramming]

Дякую! Вже навіть план для відео накидав 🙂

[@user-fq4pc7fm2z]

Очень информативно! Лайк в поддержку канала! Ждем новые выпуски.

[@AboutProgramming]

Дякую!

[@Bohdan-Venhrenovych]

Топчик !!!!

[@andrewb3790]

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

[@AboutProgramming]

Гарне питання. Спробую зробити відео на цю тему

[@SS-bo9yt]

Дуже класна подача, дякую. Ще було ю цікаво розбирати все на більш низькорівневому рівні, на зразок С. Ще по Rust можна спробувати запустити цикл відео.

[@AboutProgramming]

Дякую. На прикладі з C щось зможу показати, а от з Rust взагалі досвіду немає - тільки робив різні proof of concepts для себе. Але є плани зробити пару відео про роботу опецаційної системи всередені

[@taraslife3028]

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

[@AboutProgramming]

Є одна з моїх доповідей (правда ще російською) про реальний проект, де ці знання дуже допомогли. Й часто знання алгоритмів допомогають зрозуміти властивості існуючої системи, а тут довелося й самому багато чого реалізовувати - kzbin.info/www/bejne/ZmnFnHqQiayroK8 Але віде на каналі про реальні кейси ще теж буде :)

[@RomanRoman-bh8wu]

Крутий відос! Лайк + підписка :)

[@dmytrokucheriavyi605]

Супер, дякую! Цікавить використання структур даних та алгоритмів з точки зору вирішення практичних завдань, як на початку відео. Також цікавить мриклад створення DSL на JS та компілятора/інтерпритатора для нього.

[@AboutProgramming]

Доводилося писати пару разів компілятор/інтерпретатори, але це були досить специфічі задачі. Ось робив доповідь про один кейс - kzbin.info/www/bejne/ZmnFnHqQiayroK8, інші кейси це були транспайлер (де користували екосистему babel, але писали власні граматики) та парсер для query language, де теж розбирали за допомогою peg.js. Й ще був кейс, де дозволяли користувачу описати математичну модель й виконати її в безпечний спосіб. Відносно DSL, то частіше це просто набір бібліотек з domain specific api, або опис в декларативному форматі в конфігах. Якщо підкажете, яку саме проблему хочете вирішити за допомогою DSL (й поділитесь прикладом) й чому не підходить просто JS API, то можливо зможу ще якійсь кейс згадати. Зараз бачу тільки кейс, коли нам потрібно дати можливість користувачам описувати певну логіку, яку треба безпечно виконати. Й тут стандартне рішення приходить на думку - пишемо граматику на ANTLR або PEG.js для парсингу DSL в абстрактне синтаксичне дерево (AST), а потім просто пишем інтерпретатор або генератор коду для дерева. Сам інтепретатор написати для AST досить просто, оскільки дерево це по суті набір операторів й операндів, які можна замапити на виклики функцій Але ідея для відео гарна :)

[@j.d.3890]

вау! дякую! я хоч і тестувальник але дуже цікаво дивитися і розбирати ці речі. Не зовсім зрозумів що значить "пайтон без джита" 22:40 Хотілося б ще почути про різні методи аусентикацій зрозумілою мовою (oauth, oauth2, особливості типу колбек урл, грант тайпів, authorization code, pkce, можще ще про sso як під капотом працює)

[@AboutProgramming]

Дяку за відгук ) Відносно пайтона, то це про JIT (just in time compilation), якої немає в cpython (стандартному інтерпрететорі), але є в PyPy. Також JS V8 має потужних механіз JIT компіляції. Відносно авторизації, то дуже гарна тема. Колись навіть SAML бібліотеку повністю руками реалізоував. Думаю, що варто зробити відео, але не стільки про деталі oauth, скільки взагалі про концептуальні нюанси різних механізмів аунтентифікації (SSO й не тільки) й підтрими сессії (JWT, Signed cookies, серверні сесії й так далі) .

[@j.d.3890]

@@AboutProgramming Згоден, буде дуже цікаво послухати. Часто стикаюсь з цим по роботі, бо маємо багато різних аус механізмів на різних сервісах, які іноді треба тестувати автоматично і без ЮІ.

[@bohdanartiukhov7238]

Nice :)

[@user-io6tm9ns6g]

Дякую за контент! Дуже пізнавально) А чи плануєте (або порадите) відео по тому як правильно рахувати складність алгоритму? Щоб так просто і доступно як це робите Ви)

[@AboutProgramming]

Є книга "Cracking the Coding Interview. 189 Programming Questions and Solutions" Gayle Laakmann McDowell. Й там мені сподобався розділ цьому присвячений - "Big O", в якому різні приклади є й набір вправ по розрахунку алгоритмічної складності

[@PhotographerRoman]

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

[@AboutProgramming]

Так)) Складність то ключове. Але мені доводилося повертатися до алгоритмів не один раз - й дерева, й інвертований індекс реалізувати, й топологічну сортировку. Й все це давало значну цінність бізнесу. Ще зроблю пару відео на цю тему

[@muomieg]

Приємно, коли розумієш шо Вітя розказував тобі про це, ще до запису відео роки 2 назад :D

[@AboutProgramming]

Інфа, яка не встаріває - була корисна два роки тому, зараз корисна, буде корисна й через п'ять років 🙂

[@muomieg]

@@AboutProgramming сто відсотків)

[@padwallproduction]

Дякую за відео. Я взагалі нічого про алгоритми не читав хоча давно в індустрії. Можливо книгу порадиш?

[@Epic0n]

"Грочуємо алгоритми" класика

[@AboutProgramming]

@@Epic0n Не чув до цього про цю книгу. Глянув й книга виглядає класно - базові алгоритми й без хардкору - те, що треба для ознайомлення з темою

[@padwallproduction]

@@Epic0n дякую. Замовив.

[@sviat_d]

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

[@AboutProgramming]

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

[@sviat_d]

@@AboutProgramming дякую за відповідь. Тоді бажаю тобі наснаги, щоб випустити усі ці відео) було б круто побачити приклади, які змусять подивитись на цю тему інакше. Приклади з поточного відео точно круті і подібні задачки під час співбесіди дуже допомагають перевірити джунів. Але коли мова заходить про більш серйозні задачки для умовно сеніорів, то я можу уявити тільки дуже специфічні напрямки розробки, де дійсно можуть знадобитись серйозні знання алгоритмів. На більшості проектів може буде 1-2 місця, де доведеться заюзати якусь більш хитру структуру. Тобто далеко не кожному розробнику пощастить долучитись до челенджа))

[@oleksiiborovykov6306]

порадьте, будь ласка, книгу або курс по алгоритмах. Дякую за контент

[@AboutProgramming]

Якщо так, щоб потренуватися задачі писати для підготовки для співбесід, то найкраще www.algoexpert.io/questions . Якщо книгу для початківців (базові алгоритми), то в коментарях радили, то Grokking Algorithms. Якщо саме курс, то ніколи не проходив й тут складно щось порадити конкретне

[@AboutProgramming]

З більш повного є "The Algorithm Design Manual"

[@oleksiiborovykov6306]

@@AboutProgramming дякую

[@gradient8516]

+

[@shchekavytsia]

Було б дуже непогано відео по архітектурі. Де краще моноліт, а де мікросервіси…. І по тулзам який рушій БД в яких проектах доцільніше. Чи є життя для php в нових проектах… Ще купа питань, але то наглість з мого боку😂 Може у Вас планується освітній проект? Чи може вже є, а я відстав від життя.

[@AboutProgramming]

Відео по архітектурі будуть й багато)

[@shchekavytsia]

@@AboutProgramming дуже буду чекати! Дякую! Хоч я і не програміст, але дуже потрібно розібратись з тим, що накипіло за час роботи🤣🤣.

[@shchekavytsia]

Виявилось, що треба передивитись все, а потім питати🤣🤣🤣 трохи про мікросервіси і моноліт вже є: kzbin.info/www/bejne/g3SpfoSIa76pmpIsi=M2cUwKma4NFK5v_V

[@anndroidek]

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

[@AboutProgramming]

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

[@mityabor]

B-Tree замість массиву як раз під зовнішню пам'ять розраховане. Індекс, це структура данних для пошуку, не обов'язково в контексті MongoDB чи SQL.

[@AboutProgramming]

Так, є відео на каналі про дерева

[@IhorVyshniakov]

Омг, я поставив 2й лайк, відео 4.9к переглядів. Тобі точно варто про це нагадувати 😂

[@blazheiko777]

цікаво а в js якщо object дуже великий (ну наприклад 1 млн ключів) то наскільки швидкий доступ по ключу в обїекті? під капотом js самі ключі теж тримає в якійсь відсортованій структурі?

[@AboutProgramming]

В v8 реалізація трохи хітріша, але в цілому 1млн не сильно має відрізнятися від 1тис елементів по швидкості (при читанні), а от пам'яті звісно вимагатиме. Ну й залежить від того , наскільки V8 зможе заоптимізує все. В v8 використовується щось по типу сішного struct (просто масив) й в рантаймі на об'єкти чипляються класи (типу внутрішній ідентифікатор типу). Й коли відомий тип, то можна використати inline caching для швидкого доступу до специфічних ключів (inline cache додається не в місце ініціалізації об'єкту, в кожне місце, де ми читаємо дані по конкретному ключу). Якщо в об'єкт додається новий ключ, то відбувається зміна класу й новий клас описує, що з'явилося нове поле й вказує на попередній клас. Якщо у нас буде багато ключів й ключі будут адресуватися через змінні, то скоріше за все буде фолбек на хешмапу. Але в цілому, можна очікувати поведінки хеш-таблиці

[@andriyleliv4608]

Оце б відео мені років 5 тому побачити або комусь хто починає розбиратися з O notation і алгоритмами - розцілував би.

[@agony4181]

Але дивний цей ДЖС. А я на дарті пишу, більш схожої мови на ДЖС ніж дарт мабуть немає)

[@AboutProgramming]

А що саме пишеш? Flutter апки чи web? Й чи можна вже нормально писати бекенд на dart? А то вже давно дивився на нього. Ось думаю, що може варто ще раз поглянути 🙂

[@agony4181]

@@AboutProgramming апки усілякі, невеликі. Бек на дарте чув що можна але власноруч не робив. Фаербейс/супабейс. Або апішку на дотнет можу підняти, якщо нема бажання до усіляких сервісів звертатись.

[@Jesus_On_Extasy]

І чому всі розказують про binary search виключно на числах, адже саме з простими даними ми не так часто працюємо. Частіше у нас саме об'єкт адже даних багато і ми їх групуємо. Тож як ефективно шукати в масиві об'єктів?

[@shchekavytsia]

Наочний приклад всім користувачам «всього готового». Без знання алгоритмів в програмуванні нічого буде робити років за 3-5. Бо звичайний щіткод краще і дешевше буде генерити умовний gpt-6.0. Критикам нагадаю, що вже зараз sql запити chatgpt формує коректніше і краще ніж більшість джунів, яких я бачив за останні 3-4 роки.

[@Andrii1728]

Не зрозумів, чому 2-га функція сказано що на плюсах, якщо в JS теж є метод includes?

[@AboutProgramming]

Тут про те, що V8 реалізований на плюсах й відповідно вбудований метод includes написаний на плюсах. Ми викликаємо його с JS, але реалізації на C++

[@SerhiiZhydel]

доброго дня, Вікторе. я unity developer, тож маю інший стек і можливо через це меня турбують декілька речей з відео, не могли б ви пояснити мені їх? 1. ви кажете шо алгоритмічна складніть пошуку в хеш таблиці це О(1). я не знаю як побудовані алгоритми в JS але в C# хеш таблиця складається с бакетів (масивів) і данні кладуться в ці бакети в залежності від їх хешкоду. тож для того щоб знайти дані в таблиці, потрібно порахувати хешкод - О(1), далі знайти бакет в який цей хешкод мав кластися - О(кількість бакетів) або О(log(кількість бакетів)) і далі всередині бакета знайти елемент який нам потрібен О(кількість елементів в бакеті) або О(log(кількість елементів в бакеті)). тоже в залежності від того на скільки бакетів поділена таблиця і скільки елементів знаходиться в конкретному бакеті, складніть може бути дуже різна. навіть в ідеальному випадку це О(1) + О(log(кількість бакетів)) + О(log(кількість елементів в бакеті)). та й взагалі, на базовому рівні хештаблиця - це данні відсортовані по хешу і задача пошуку в ній аналогічна до пошук числа в сортованому массиві, тобто О(log(n)). чому ви (ну і ще в кількох містях я про це чув) кажете что пошуку в хеш таблиці це О(1)? 2. якщо казати про пошук юзера по Id, то мабуть правильніще було б казати про пошук в базі данних, тому що Object.FromEntries(users.map(...)) (знову ж таки я не знаю JS, але якщо я правильно зрозумів) це створення нової, відсортованної коллекції данних. тобто якби щось подібне мало б місце в проді, то це б означало що я б повинен був запулити всю таблицю с користувачами, а потім іще її пресортувати и лище потім шукати юзера. хіба ORM якії ми передаємо запит не повинна сама сформувати найоптимальніший запит до БД? в такому разі ваш перший приклад з users.find має набагато більше сенсу і потрібно зосередитись над тим щоб в БД приходили оптимізовані запити. 3. чи часто вам доводиться писати такі алгоритми власноруч? бо з мого досвіду знання алгоритмів зводиться до правильного використання типів данних і їх комбінацій, а не до безпосереднього їх написання.

[@AboutProgramming]

Гарні моменти підмічені, але є нюанси. 1. Відносно алгоритмічної складності хеш-таблиці, то я кажу в відео про "середньому, якщо немає колізій" й там буде константний час пошуку. Час пошуку бакету насправді не "О(кількість бакетів) або О(log(кількість бакетів))" , а O(1), оскільки це просто доступ по індексу в масиві. Відносно пошуку в бакеті, то він виникає тільки, коли у нас є колізії (тому в середньому у нас константа, а найгірший варіант це коли у нас всі значення потрапляють в один бакет й отримуємо пошук по звʼязаному списку за O(n)). 2. >"Object.FromEntries(users.map(...)) це створення нової, відсортованної коллекції данних". Тут немає сортування, але так це стоврення щось типу хештаблиці (в JS це обʼєкт, який працєє трохи по інакшому, там є inline caching й більше на struct тоді схоже). Чи треба тягнути всі дані - ні. Наприклад, я витягаю список банківських операцій, а потім збираю список користувачів, які згадувалися там й потім роблю запит лише на список потрібних користувачів. Але після цього мені треба додати інформацію про користувачів в таблицю за банківльськими операціями. Це можна вирішити через JOIN на бекенді, але часом база не вміє джойн(MongoDB), або дані з різних джерел тягнуться, або таке API у бекенда й треба робити на клієнті або ще щось. 3. Померджети дані часто буває треба. Й звіти різні, й просто в UI, коли апіха тільки так вміє. Але якщо говорити взагалі про стуктури даних й алгоритми, то значно частіше це про використання, а не написання. Й розуміння структур даних це більше для того, щоб розуміти їх властивості, а не щоб їх безпосередньо реалізовувати ці структури (але буває й таке :) Колись робив доповідь про цікавий проект kzbin.info/www/bejne/ZmnFnHqQiayroK8 (російською)

[@SerhiiZhydel]

@@AboutProgramming дуже дякую вам за таку швидку та детальну відповідь! 1. Дуже гарне зауваження щодо пошуку бакета. Справді, якщо їх кількість фіксована, то простіше використовувати остачу від ділення хешкоду на кількість бакетів як індекс в масиві і мабуть саме так це і робиться) Проте все ж, як я розумію, при значній кількості даних (або гарантовано - якщо елементів більша ніж кількість бакетів), колізій не можна уникнути, тому у результаті все одно потрібно буде виконувати перебір, тож всеодно це не O(1). У випадку коли ми маємо 200к елементів в таблиці і додавали їх поштучно (не вказали одразу скільки бакетів потрібно), алгоритмічна складність буде значно гіршою ніж навіть O(log(n)), бо нехай там буде стандартних 16 бакетів (нагуглив це число для Java, для інших мов мабуть щось схоже), це все ще ~12500 елементів в бакеті, правильно? Або ж ця таблиця буде перераховуватися кожен раз коли кількість елементів буде наближатися до кількості бакетів (тобто разів 10 щонайменше) і тоді цей тип даних теж важко назвати оптимальним для подібних задач (пошуку елементів всередині локальної функції), краще вже віддати це в БД з індексами) 2.1 Може розгатка до попереднього пункту полягає у вашій відповіді на цей. Бо якщо в JS існує якесь магічне рішення для проблем з хеш таблицею, то воно мало б працювати і тут. Створення і заповнення таблиці теж доволі важка операція (як мінімум, це вже обхід початкового массиву, щоб покласти його в цю таблицю), а якщо вона ще й це відбувається локально, то й генеруюча багато сміття, яке щоб потім прибрати, треба теж тратити процесорний час. 2.2 А якщо у нас небагато елементів у масиві (як у випадку з кількістю юзерів у транзакції), то пошук перебом у 95% випадків виглядає як найбільш оптимальне рішення. Звичайно, якщо масив великий і уже відсортований, то можна придумати і щось інше, проте я таких випадків на своїй роботі майже не пам'ятаю) 2.3 Інші зауваження про MongoDB і багато запитів на зовнішні сервіси звучать як проблеми вищого рівня і навряд проблема саме в процесорному часі. Тут автору цього рішення скоріше треба було б спочатку дивитися відео про архітектуру)) Проте я розумію що інколи таке має місце і тоді треба просто писати костиль, бо швидко цю проблему не вирішити і тоді можна вклеїти сюди ваш код) Але навіть так, мабуть більше часу буде витрачено на чекання відповіді від зовнішніх сервісів і парсення їх в обьекти. 3. Думаю ви самі про це чудово знаєте і просто упустили цей момент і не підкреслили у відео, що передчасна оптимізація така ж небезпечна як і її відсутність. Звістно, кожен программіст повинен розуміти як використовувати різні структури даних, проте у мене складається враження що основна аудиторія яка буде дивитися це відео і брати його на озброєння, будуть джуни. І через їх оптимізацію, їх і без того важкий до читання код, стане іще важчим, а заодно доведеться розгрібати конфлікти у команді щодо того коду)) 4. Я б іще доповнив відео правильним вибором інструментів для рішення різних проблем. Може якийсь алгоритм можна написати на c++, щоб він виконувався на стеці, щоб не було кеш місів? А потім зверху іще запакувати це у векторні операції? Або переписати алгоритм, щоб він виконувався на шейдері, якщо річ йде про клієнський код? А може все ж простого перебору буде достатньо)

[@AboutProgramming]

@@SerhiiZhydel хеш таблиця в середньому має константний час доступу й більшість реалізацій забезпечують завдяки динамічній зміні розміру й рехешингу. Відносно кількості бакетів, то нормальний load factor на рівні 0.6-0.7. Тобто бакетів має бути більше ніж значень

[@SerhiiZhydel]

@@AboutProgrammingЗараз передивився іще раз відрізок про цю оптимізацию з хеш таблицею, а також прогнав бенчмарки. Дійсно, навіть при відностно малій кількості елементів (5 юзерів і 100 месседжів, 1000 ітерацій), другий варіант відпрацьовує майже в 2 рази швидше, а коли кількість елементів зростає (1000 юзерів, 20_000 месседжів, 1000 ітерацій), то різниця доходить 100 разів. Проте і споживання пам'яті теж значно зростає. В першому випадку різниця також в 2 рази, а в другому за 1000 ітерацій другий варіант від'їдає 30 мб, в той час як перший 0.1мб. Я закешував таблицю (очищав її перед кожним запитом) і тоді споживання пам'яті впало до 1кб. Я просто в шоці, в мене розрив шаблонів, ніколи не думав що можна перекладати дані з одніеї колекції в іншу для якоїсь локальної обробки і що це даватиме такий буст.

[@yuriyfse6555]

1:43 Хіба тільки усерНейм?)

[@AboutProgramming]

Щось пропустив? :)

[@user-mh5up7ft5u]

то вчити Пайтон чи ні?

[@AboutProgramming]

А чому ні?)

[@MiiDosvid]

Є нюанси: - В більшості випадків це не потрібно. - Більшість бібліотек вже має це все під капотом. - Джуна не будуть саджати за алгоритмічні системи. - Коли тобі треба щось зоптимізувати це легко гуглиться. - Робота з алгоритмами набагото складніше того що ти показав, це не одна книжечка "алгоритми", це глибокі знання математики, вміння читати та розуміти научні пейпери, та вміня це все юзати для розробки того що тобі треба. Фактично це або РнД або дослідницька діяльніть, але аж ніяк everyday practice. - Я дуже не рекомендую запам'ятовувати те що не потрібно кожень день.

[@AboutProgramming]

Дякую. Цікава думка, але не можу погодитися. Спробую пройтися по всім пунктам. >В більшості випадків це не потрібно. Алгоритмічна складність це основа й досить важлива. Регулярно опираюся на це в щоденній роботі, що просто в написанні коду, що в проектуванні складних підсистем. Відносно алгоритмів й структур даних, то теж бачу багато випадків, коли розробникі не розумають властивостей індексів в базах даних, оскільки не розуміють, що там B-Tree всередені. Аналогічно з інвертованими індексами. Робив відео на каналі "Навіщо глибоко розбиратися в речах й як менше забувати те, що вивчили?" - kzbin.info/www/bejne/rKbRkoaZaJx1a9E Знати в деталях неможливо, але розуміти принципи дуже корисно. > Більшість бібліотек вже має це все під капотом. Але треба розуміти, що там, що розуміти властивості, щоб можна було обрати відповідно бібліотеку. Банальний приклад LinkedList vs Array. >Джуна не будуть саджати за алгоритмічні системи. Так, а мідла чи сеніора вже можна. Тобто, мідл/сеніор знають, як працюють алгоритми, а джун - ні. Тобто, якщо джун хоче вирости, то йому теж доведеться це знати. >Коли тобі треба щось зоптимізувати це легко гуглиться. Зазвичай можна нагуглити, як поміряти перфоманс, а оптмізації можуть займати місяці. Декілька прикладів з життя: 1. Система перевірка пермішенів для IoT проекту. Треба чітко розуміти алгоритмічну складність було й стурктури даних, щоб отримати достатній рівень масштабованості систем. 2. В Гуглі оптимізуємо latency веб-інтерфейсу й ця робота більше ніж на рік. Але так, часом буває й простіше кейси. Наприклад переписати 3 вкладених цикли на 3 цикли один за одним. Й замість O(n^3) отримати O(n). Але це часто видно на код-ревʼю, якщо є розуміння алгоритмічної складності. >Робота з алгоритмами набагото складніше ...це або РнД або дослідницька діяльніть. Буває й таке, але в таких проектах не доводилося приймати участь. >Я дуже не рекомендую запам'ятовувати те що не потрібно кожень день. Просто запамʼтовувати не працює, але працює підхід, коли інженер намагається сформувати у себе в голові систему. Тоді все йде набагато легше. Окрім того, це дозволяє інженеру зростати. Є є про це в тому відео вище. Чи можна без цього - так можна. Чи є велика користь від знань алгоритмів й структур даних? Тут діє закон спадної граничної корисності - з кожним додатковим алгоритмом й структурою даних додаткова корисність падає. Але зовсім без цього буде складно. В Гуглі алгоритми й структури це те, що очікують від джунів, як найпростіше, що можна знати. Від мідлів й сеніорів очікують вже вміння проектувати.

[@MiiDosvid]

@@AboutProgramming у гугла очень не очень подход к найму, изза чего такое огромное количество мертвых проектов и никакая прибыль от них. Гугл очень плохой пример того как надо особенно сейчас. Да и сори но таких обьемных контор раз два и обчелся, ориентироваться на 1 из ярдов так себе решение. Помню ли я как работает б-три индекс - нет, надо ли мне это помнить - нет, могу ли я за 5 мин прочитать и вспомниить - да. следовательно ценность памяти ничего не стоит. А вот место в буфере очень сильно позволяет не тупить. ты не можешь запомнить все аспекты разработки. это физически нереально, а следовательно и пытаться это делать не стоит. А вот уметь быстро искать инфу и в ней разбираться надо.

[@MiiDosvid]

@@AboutProgramming вот смотри вы оптимизируете латенси год. а вы считали насколько эти затраты эффективны? оптимизация это крайне дорогая штука которая в 99.9% не окупается, я именно про оптимизацию а не правки за косолапыми девами

[@AboutProgramming]

@@MiiDosvidта ніби Гугл нормально заробляє) Відносно людей, які працюють в Гуглі, то виключно позитивно оцінюю їх професіоналізм й бізнес орієнтованість. Багато людей, які успішно запускали бізнеси й стартапи й благо людей після Гугла запускають бізнеси й стартапи. Відносно b-tree, то багато джунів взагалі не знають про індекси, а хто знає, то дивує чому LIKE '%searchstr%'. Відносно закритих проектів, то не закривають ті, які не приносять користі бізнесу, що ок. Віднесено питання про latency, то настільки є запитів від продактів, що доводиться дуже зважено підходити до пріоритетів й робити тільки те, що максимально важливо. Задачі по latency теж не виникли з порожнього місця

[@MiiDosvid]

@@AboutProgramming у гугл зарабатывает реклама и клауд, остальное почти все убытики

[@chuabaka864]

ок, перший приклад ОК... швидше. але шо по памяті? збільшилась, бо масив згенерував ще один. на тисячах ОК... а як про 100к, 1000к??

[@AboutProgramming]

Памʼяті треба більше. Hashtable вимагає O(n) памʼяті. Але тут потрібна памʼять не під весь обʼєкт, оскільки ми можемо тримати референс на нього

[@chuabaka864]

@@AboutProgramming ok, тобто створюючи новий ми робимо асоціативний масив. якщо так то може й не в два рази. але якщо це буде новий, то біда. можливо я помилився. бо це ж не клонування...

[@AboutProgramming]

@@chuabaka864 так, але тут обираємо де менша біда. по пам'яті ми будемо умовно 2x, а от по CPU зростання може бути квадратичним. Припустимо, що у нас по одному юзерів й повідомлень й нам потрібно додатково пам'яті на одного юзера. А тепер припустимо, що у нас 10k юзерів й повідомлень, то пам'яті нам треба тепер в 10k більше або CPU в 10млн разів більше. По цій самій причині й індекси в базах існують хоч й займають додаткове місце

[@chuabaka864]

@@AboutProgramming індекси, то трохи інше. у вас не індекси у вас нова структура. індекси мають фізичні оффсети. а у вас дані.

[@sergiig9336]

Але навіщо питати про балансування В+ дерева на співбесіді на роботу, яка передбачає зміну кольорів кнопочек, питання відкрите 😃

[@AboutProgramming]

У мене жодного разу не питали)

[@sergiig9336]

@@AboutProgramming в мене питали, при чому не на сеньорну (як потім виявилось) позицію 😃

[@AboutProgramming]

@@sergiig9336 в Гуглі зазвичай кодінг інтерв'ю це база, яка для всіх - й джуни й менеджери проходять. Там не вимагається зазвичай прям реалізувати якійсь відомий алгоритм, а дається задача, де знання алгоритму можу бути корисним, щоб зробити більш оптимальне рішення. На старші позиції вже додається system design interview

[@bohdanmarynushkin7630]

краще бути вже не може

[@MasterSergius]

Як хтмл-програміст згідний на всі сто

[@AboutProgramming]

Особливо, якщо робити складні анімації на канвасі)

[@livepege8409]

Цікаво, дак! Але... багато тошноти. Щоб не було тошноти потірібні дублі і монтаж, а не все робити в один захід.

[@AboutProgramming]

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