Про культурні традиції українського IT та найважливіше в алгоритмах — розповідає Іван Петрушенко

В Україні багато талановитих програмістів і дата-саєнтистів, але класний програміст — це не завжди класний викладач. Мало кому вдається пояснити алгоритмічні концепції на пальцях для програмістської авдиторії.

Розробник й Engineering Lead Іван Петрушенко вирішив займатися саме цим. Він започаткував школу, де вже сформовані фахівці опановують хардкорний фундамент Сomputer Science. Ми поспілкувалися з Іваном про традиції українського IT і про те, що все ж важливо розуміти про математику.

— Іване, розкажи трохи про себе.

Я з Херсона, а навчався в КНУ ім. Шевченка на кібернетика. З навчання запам’яталося дві речі: круті викладачі та одногрупники. В університеті справді класно викладали курс з алгоритмів. Один з лекторів був тренером команди з України, яка не раз виступала на фінальній першості ICPC (International Collegiate Programming Contest). Крім того, на факультеті була сильна кафедра теорії програмування. Один з предметів викладав академік НАН України Володимир Редько, це було неймовірно цікаво.

Я хоч і почав програмувати ще до університету, з самого початку навчання створювалося враження, що всі розумніші та краще програмують. Пам’ятаю яскравий момент, коли я тиждень бився над розв’язанням однієї алгоритмічної задачі. І от на парі з матаналізу вирішив запитати поради у товариша, який тепер працює в Google. Той подивився на неї і розв’язав за кілька хвилин. У мене був шок. Пізніше я дізнався, що він посилено тренується на Topcoder.com вже не перший рік.

У мене звичайна українська родина. Моя мати лікарка за фахом, родом з Житомирської області, тато з Херсонської області, працює викладачем. Попри щоденні обстріли, продовжують жити в Херсоні й не хочуть переїздити до Києва. Тато щотижня на день приїжджає до Києва, викладає пари в університеті й повертається додому. Батьки завжди разом. Власне російську окупацію разом пережили. Хоча перші тижні були порізно, бо тато обороняв Херсон як доброволець.

«Пам’ятаю, яким був щасливим, коли залишив один з перших важливих коментарів в пул-реквесті»

— Розкажи, як почався твій професійний шлях програміста.

Мені пощастило з першою роботою — це було на третьому курсі університету, проєкт компанії Dell. Викладач з програмування розповів, що компанія, в якій він працює, проводить набір на інтернатуру. Я пройшов відбір і став Junior C# розробником. Ми розробляли систему зі 100-відсотковою безпекою даних. Тобто це алгоритми, які пов’язані з бекапом, дедуплікацією та експортом величезних об’ємів даних.

Тоді вперше зіткнувся з величезною кодовою базою, написаною на С, C++ і C#, де були реалізовані всі ті алгоритми, які ми обговорювали в університеті. Пам’ятаю, яким був щасливим, коли залишив один з перших важливих коментарів в пул-реквесті, де запропонував рішення з O(n*n) до О(n) простим кешуванням даних. Чи коли довелося написати аналог Bloom-фільтра, щоб зменшити кількість звертань до бази даних.

Зрештою я пропрацював у цій компанії понад чотири роки. Але одного разу вирішив піти на відкриту лекцію в Projector, де виступав мій знайомий, на той час CTO Squad. Після неї поспілкувалися, після чого він запропонував пройти інтерв’ю до них. Ось так я й потрапив у світ AWS, Python та Machine Learning. Ще працював у Fiverr і консультував інші міжнародні компанії як Senior Software Engineer.

— Machine Learning нині досить хайпова, трендова річ. Як ти ознайомлювався з ML? Можеш назвати ютуб-канали, книжки, з якими варто ознайомитися?

Читайте також 👇Я б порадив пройти два курси від Стенфордського університету, які є у відкритому доступі. Перший це вступ до Machine Learning від Andrew Ng, там чудово пояснюють базові речі, такі як лінійна регресія або лінійна алгебра. А другий — це CS231N від Andrej Karpathy, зверніть увагу на завдання, опубліковані на сайті курсу. Вам доведеться реалізувати з нуля KNN, Softmax classifier, Convolutional Neural Networks та багато іншого.

Щодо книжок — це Deep Learning від Йошуа Бенгіо та Probabilistic Machine Learning від Кевіна Мерфі. Вони не про конкретні фреймворки, а радше про засади Machine Learning, тому не втратять актуальність.

— Очевидно, алгоритми відіграють важливу роль у професійній підготовці будь-якого інженера, зокрема ML Engineer. Яке було твоє перше знайомство з алгоритмами? Що найбільше запам’яталося?

З алгоритмами я вперше ознайомився у математичних журналах. Там, наприклад, вперше стикнувся з рекурсією через задачу про Ханойські вежі. Було трохи лячно, що від монаха у В’єтнамі, який перекладає кільця, залежить доля світу, але аналіз алгоритму допоміг зрозуміти, що не все так погано :) Далі були перші спроби реалізації тих чи інших алгоритмів, і це було не просто. Я вдячний, що в університеті мені порадили книжку Programming Pearls Джона Бентлі, де вводиться поняття інваріанта циклу і як через нього можна реалізувати складний код коректно та більш красиво, без зайвих ± одиниць чи додаткових розгалужень (if-statements).

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

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

Пробач за тавтологію, перед тим як відповісти на це питання, треба вичерпно відповісти на наступні: а хто такий Віктор Глушков? Чому в Блечлі-Парк у Лондоні (так, тому самому, де працював Алан Тюрінг над «Енігмою») при вході в Музей комп’ютерної техніки висить портрет українки? Відповідь проста: вона 65 років тому створила першу у світі мову програмування високого рівня. Вона перша у світі ввела поняття «вказівник». Це учениця Глушкова. Я навмисно не називаю її ім’я, кому цікаво хай погуглить. (DOU випускав біографічний матеріал про українську науковицю і програмістку Катерину Ющенко зі спогадами її сина — ред.).

Український вплив в ІТ — це важлива тема, бо мене зачіпає ситуація, яка деколи складається в цій галузі. Я про покоління молодих, амбітних хлопців і дівчат, які закінчують УКУ, КНУ, КПІ, здобувають висококласну освіту, знають декілька іноземних мов, декілька мов програмування, мріють працювати у FAANG та загалом почуваються інтелігенцією першого покоління. Чому? Бо вони добре заробляють і можуть ввечері прийти додому після мітингів, послухати в оригіналі виступ Сема Альтмана або Джона Кармака на каналі Лекса Фрідмана.

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

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

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

— До речі, а що можна вважати ключовими властивостями ефективного алгоритму?

Будь-яка книжка з теорії алгоритмів скаже, що це приблизна кількість елементарних операцій і кількість використаної пам’яті. Але на практиці важливо звертати увагу, наскільки алгоритм добре лягає на «залізо», на якому він буде виконуватися. Наприклад, наскільки він cache-friendly? Це може зіграти ключову роль. У HFT (high-frequency trading) компаніях або ігровій індустрії на це особливо зважають, бо кожна наносекунда на вагу золота.

Тут варто виділити напрям, який нині дуже популярний — Data-oriented programming (DOP). На відміну від об’єктноорієнтованого програмування, де акцент зазвичай робиться на об’єктах і їхній поведінці, DOP ставить у центр оптимізацію обробки даних. Це часто означає, що ви маєте розмістити ваші дані в пам’яті так, щоб вони були поруч, що дає змогу CPU виконувати операції швидше, оскільки доступ до даних стає більш послідовним.

— Скажи, будь ласка, які алгоритми найбільш складні для реалізації?

Я б виділив алгоритми, в яких закладена складна логіка з велику кількістю винятків, які програмісту потрібно обробити окремо. Тобто алгоритми, які не є інтуїтивними, а більше на уважну реалізацію — запрограмував і забув. До таких може належати червоно-чорне дерево, ця структура ніколи не здавалася мені інтуїтивною, на противагу АВЛ-дереву.

— Чи є такі алгоритми, які вплинули на розвиток програмування?

На розвиток програмування вплинуло визначення поняття алгоритм. Бо якби такі люди, як Тюрінг, Черч, Кліні, Гедель у 30-х роках не загадувалися над питанням формального визначення того, що є алгоритм, ми би тут з тобою не сиділи.

А щодо самих алгоритмів, то я б виділив задачу пошуку, сортування та теорію графів. Цікаво, що нові алгоритми та структури даних активно виникають і сьогодні. Наприклад, skip list доволі молода структура, утім активно використовується в базах даних. Або ж якщо подивитися на класичні алгоритми, як-от binary search, quick select або побудову priority queue, то вони були суттєво пришвидшені за останні 10 років, не асимптотично, але в декілька разів точно.

— Не можна не запитати, які алгоритми програмісту варто знати, от як табличку множення. Без чого серйозному програмісту не обійтися?

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

Водночас Grammarly давали tech-talk про те, як реалізували свою хеш-таблицю, аби не витрачати зайвий час на пошук у зв’язному списку при вирішенні колізій методом ланцюжків.

Тобто моя порада — у деталях розібратися з тими алгоритмами та структурами, які ви вже зараз використовуєте в роботі, бо вони і є наразі для вас обов’язковими. Так ви станете тією людиною в команді, яка зможе пофіксити проблеми раптом що.

— Я часто чую від різних «гуру», що загалом для програміста математика і не зовсім потрібна. Чи потрібне розуміння математики на якомусь рівні?

Мені нещодавно довелося оптимізовувати вузьке місце в коді — це був цикл, в якому обрахунок кожної наступної операції залежав від результатів попередніх обрахунків. Компілятор зробив loop unrolling, щоб зменшити оверхед на виконання циклу, — але цей код все одно погано паралелився, у нього був низький рівень instruction level parallelism. Але коли ми переписали код так, щоби він у циклі виконував додавання, то все запрацювали набагато швидше. Адже додавання не лише асоціативне, а й комутативне. Це означає, що не має значення порядок групування чисел і порядок їхньої обробки, а отже у нас код добре паралелиться навіть на одному ядрі.

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

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

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

— Чи можна зробити умовний план для вивчення алгоритмів? З чого варто починати, з чого не варто?

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

— Чи матиме машинне навчання взагалі якийсь вплив на розвиток алгоритмів? Чи це дві паралельних площини?

100% матиме. Уже має. На одному з наборів курсу з алгоритмів ми розбирали статтю Джефа Діна The Case for Learned Index Structures, де автори пропонують ідею замінити традиційні структури даних, такі як B-дерева чи хеш-таблиці, навченими моделями. У статті аргументують, що за допомогою машинного навчання можна створити індекси в БД, які будуть працювати ефективніше за класичні структури даних. Але потім прийшли інженери зі Stanford DAWN і розкритикували цю ідею, показавши, що зарано викидати Кормена.

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

— Коли ти казав, що працюєш з ML у Squad, чи потрібні тобі знання алгоритмів?

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

Нещодавно потрібно було реалізувати структуру даних, якої немає в Python і яка містить в собі плюси зв’язних списків та хеш-таблиць. Бо в нас виникла потреба підтримувати порядок на елементах, мати швидку вставку та видалення з обох кінців та водночас швидкий пошук за структурою.

«LLM не справляються із задачами із зірочкою»

— Це питання випливає з попереднього — про LLM-моделі — чи так вже важливо програмісту самому володіти алгоритмічною базою? Бо зараз достатньо написати якийсь промпт, і все, завдання виконано. Як ти вважаєш?

База сто відсотків має бути, бо LLM не справляються із задачами із зірочкою. Тобто так, вони можуть вам допомогти розв’язати простеньку задачу або допомогти згенерувати ідеї, накидати варіанти рішення. Але щойно завдання складнішає — вони не справляються. І тут вже варто покладатися суто на власні сили.

— В нашій розмові ти кілька разів згадував про свою школу програмування. Розкажи про неї.

У СS Osvita ми навчаємо фундаментальних напрямів Computer Science не через теорію, а шляхом написання складних програм. До нас приходять досвідчені спеціалісти, деякі з них вже працюють у Netflix, Facebook, Google тощо.

Чому саме напрям фундаментальних наук? Зверни увагу на те, що радять читати топові програмісти світу, наприклад Джо Даффі.

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

А подивіться на SICP: книжка, написана майже 30 років тому, досі вважається найкращою для вивчення програмування. Бо вона вчить, як бути самодостатнім інженером, який може розібратися в складних речах. Цього принципу дотримуємося і ми.

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

— Ну й на завершення цікаво дізнатися, які персоналії вплинули на тебе останнім часом найбільше, окрім Computer Science світу.

Не з Computer Science світу я б виділив двох людей. Перша людина — це командир полку «Азов» Денис Прокопенко. Ніколи не забуду одне з його нечисленних інтерв’ю на початку війни, коли полк ще перебував у повному оточенні на «Азовсталі». На запитання в кінці інтерв’ю «що би він хотів передати близьким та всім тим, хто його зараз чує» він відповів: «Вам за нас не буде соромно». Тут нема чого додати, просто в цей момент усвідомлюєш неспівмірність себе і цієї людини. Ніколи не знайду слів, достатніх для подяки нашим воїнам.

А друга людина — це Оксана Забужко. Усе те, що вона нині робить у сфері культури — це просто неймовірно. Чого лише вартує її виступ на Берлінале, а її роман «Музей покинутих секретів», який вже отримав нагороду як найкращий роман в Європі і згодом, впевнений, отримує Нобелівську премію, — це моя рекомендація всім до прочитання.

Все про українське ІТ в телеграмі — підписуйтеся на канал DOU