Видавництво ArtHuss готує до публікації книгу «Грокаємо алгоритми: Ілюстрований посібник для програмістів і допитливих». Публікуємо уривок з неї

Видавництво ArtHuss найближчим часом випустить книгу «Грокаємо алгоритми: Ілюстрований посібник для програмістів і допитливих» Адітьї Бхаргави. Це практичний гайд, який має навчити читача працювати з поширеними алгоритмами та застосовувати їх для реальної роботи. З дозволу видавництва публікуємо частину книжки, що стосується поняття стек-викликів.

Адітья Бхаргава — випускник Чиказького університету та штатний інженер в Etsy. У «Грокаємо алгоритми» він починає з легких прикладів та тем, а потім поступово переходить до складніших задач. При цьому книга охоплює широкий спектр питань: сортування, бінарний пошук, хеш-таблиці, динамічне програмування, рекурсія тощо.

«Моя ціль — спростити візуалізацію концептів, а не заплутати нагромадженням незрозумілих символів». Кажучи загалом, коли дочитаєш книжку, ти вже будеш знати деякі з найрозповсюдженіших алгоритмів. Надалі ти зможеш застосувати ці знання для глибшого вивчення конкретних алгоритмів для роботи з ШІ, базами даних і таке інше. Або ти зможеш випробувати себе у розв’язанні складніших задач на роботі«, — додає Адітья.

На сайті ArtHuss можна скористатися промокодом gamedevdou, який дає знижку 15% на будь-які купівлі через кошик.

Уривок з книги «Грокаємо алгоритми: Ілюстрований посібник для програмістів і допитливих»

Стек

У цьому розділі описано поняття стек-викликів. Це важлива концепція у програмуванні. Ця структура даних у вигляді стека важлива для узагальненого програмування, а також для розуміння застосування рекурсії.

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

Повернися назад і пригадай, коли ми говорили про масиви та списки на прикладі переліку справ?

Ти міг додавати пункти будь-де у списку — або видаляти будь-які з них. Стек із наліпок набагато простіший.

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

Подивімось на список справ у дії.

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

Стек викликів

Твій комп’ютер усередині використовує стек, який називається стеком викликів. Подивимося, як це працює. Ось тобі проста функція:

def greet(name):
    print "hello, " + name + "!"
    greet2(name)
    print "getting ready to say bye..."
    bye()

Ця функція вітає тебе, а потім викликає дві інші функції. Ось який вони мають вигляд:

def greet2(name):
    print "how are you, " + name + "?"

def bye():
    print "ok, bye!"

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

Примітка: print— це функція мовою Python, але щоб не ускладнювати цей приклад, удамо, що це не так. Просто підіграй мені.

Припустімо, ти викликаєш функцію greet («maggie»). Спершу комп’ютер виділяє блок пам’яті для цієї функції.

Тепер використаємо цю пам’ять. Змінній name задаємо значення «maggie». Це має бути збережено у пам’яті.

Кожного разу, коли ти викликаєш функцію, комп’ютер зберігає значення всіх змінних для виклику з пам’яті, як цей. Далі ти друкуєш hello, maggie! Потім ти даєш ім’я greet2("maggie«). І знову комп’ютер викликає блок пам’яті для цього виклику функції.

Твій комп’ютер використовує стек для цих блоків. Другий блок додається поверх першого. Ти вводиш how are you, maggie? Потім повертаєш керування з виклику функції. Коли це відбувається, верхній блок стека видаляється з нього.

Тепер верхнім у стеку буде блок із функцією greet, а це значить, що ти повернувся до цієї функції. Коли ти викликав функцію greet2, функцію greet було лише частково завершено. Це і є основна ідея цього розділу: коли ти викликаєш функцію з іншої функції, викликаюча функція зупиняється у частково завершеному стані. Усі значення перемінних цієї функції все ще зберігаються у пам’яті. А коли виконання функції greet2 буде завершено, ти повертаєшся до функції greet і продовжуєш із місця, де зупинився. Щойно ти вводиш getting ready to say bye... Ти викликаєш функцію bye.

Блок із цією функцією додано на верхівку стека. Тоді ти друкуєш ok bye! і виходиш із виклику функції.

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

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

Підписуйтеся на Telegram-канал @gamedev_dou, щоб не пропустити найважливіші статті і новини