«Грокаємо алгоритми»: просто про складні задачі в програмуванні. Уривок з книги

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

«Грокаємо алгоритми»: просто про складні задачі в програмуванні. Уривок з книги / Фото: Arthuss, Depositphoto

Книга «Грокаємо алгоритми: Ілюстрований посібник для програмістів і допитливих» – результат цього поєднання. Автор обіцяє читачу: «Ти опануєш техніки розв’язування задач, які донині могли бути поза межами твого розуміння». Цю книжку написано так, щоб її було легко сприймати. Як тільки згадується новий концепт Адітья Бхаргава пояснює його або попереджає, коли дасть пояснення. Основні поняття підкріплено вправами, щоб читач завжди міг перевірити себе й упевнитися, що не втратив нитку оповіді. Усі алгоритми цієї книги – практичні. Вони будуть корисні програмістам та забезпечать основу для інших, складніших тем. Редакція MC.today публікує уривок. Замовити книгу можна тут.

Як працює пам’ять

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

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

Ти кладеш свої речі в ці дві шухляди.

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

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

Далі я говоритиму про ці масиви та списки, а також про їхні недоліки та переваги. Не існує єдиної правильної структури впорядкування на всі випадки, тому дуже важливо зрозуміти різницю між ними.

Масиви та зв’язані списки

Буває, що треба зберегти список елементів у пам’яті. Припустімо, ти пишеш додаток, щоб упорядкувати власний список справ. Ти хочеш розташувати їх у пам’яті саме у вигляді списку. Що краще використати, масив чи зв’язаний список?

Давай спершу спробуємо у вигляді масиву, так тобі буде легше зрозуміти. Якщо ти застосуєш масив, усі твої справи буде розташовано у пам’яті безперервно (одна за одною).

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

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

Якщо ви зустрінете ще одного друга, вам знову забракне місць, щоб запросити його – і всім доведеться пересідати вдруге. Оце ще клопіт! Схоже, додавання нової позиції до масиву може бути марудною справою. Коли не вистачає місця і щоразу доводиться шукати вільну ділянку пам’яті, додавання нової позиції відбувається дуже повільно. Щоб легко виправити ситуацію, можна «притримати місця»: навіть якщо у твоєму розкладі тільки 3 пункти, ти можеш забронювати в комп’ютера 10 слотів про всяк випадок. Тоді можна буде збільшити розклад до 10 позицій, не змінюючи розташування. Непоганий обхідний шлях, от тільки ти маєш усвідомлювати деякі моменти:

• Можливо, тобі взагалі не знадобляться додаткові слоти, тоді пам’ять буде витрачено даремно. Ти не використаєш цю ділянку пам’яті, і ніхто не зможе, бо вона заброньована.
• Або тобі знадобиться додати більше ніж 10 позицій, і тоді все одно доведеться все переносити.
Онлайн-курс "Computer Vision" від robot_dreams.
Застосовуйте Machine Learning / Deep Learning та вчіть нейронні мережі розпізнавати об’єкти на відео. Отримайте необхідні компетенції Computer Vision Engineer.
Дізнатись більше про курс

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

Зв’язані списки

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

Кожна позиція списку зберігає адресу наступної за нею позиції. У групі рандомні адреси пам’яті зв’язані між собою.

Це як пошук скарбів. Ти йдеш за першою адресою – і там написано: «Наступну позицію можна знайти за адресою 123». Тож ти йдеш далі за вказаною адресою, а тут повідомляється, що наступна в ланцюжку позиція знаходиться за адресою 847 тощо. Включити нову позицію до зв’язаного списку дуже легко: ти зберігаєш її де завгодно у пам’яті та пов’язуєш кожну наступну адресу з попередньою.

Зі зв’язаним списком тобі ніколи не доведеться переміщувати збережені раніше позиції. Крім того, ти уникаєш іще однієї проблеми. Скажімо, ти йдеш у кіно на популярний кінофільм разом із п’ятьома своїми друзями. Ваша компанія з шістьох намагається знайти місця, але виявляється, що кінотеатр переповнений. У ньому не знайдеться шести вільних місць, розташованих поруч. Що ж, таке часто трапляється з масивами.

Припустімо, ти намагаєшся знайти 10 000 вільних слотів для масиву. У твоїй пам’яті є 10 000 слотів, але вони не розташовані разом. Ти не можеш отримати місце для свого масиву! А зв’язаний список — це ніби ти кажеш: «Може, розсядемося по вільних місцях і нарешті подивимося фільм?».