Структури даних: Форми, що визначають швидкість вашої програми

Форма визначає операцію, а не навпаки

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

Стіки та черги: дві дисципліни на одній послідовності

Стік додає або видаляє елементи лише з одного кінця — останній у першому (LIFO). Це природна структура для будь-чого з вкладеними обсягами: стека викликів, який відстежує, яка функція повертається до якої, історії скасування, відповідності дужок та глибинного пошуку. Черга додає елементи на одному кінці та видаляє їх з іншого — перший у першому (FIFO) — що потрібно для обробки елементів у порядку прибуття: планування завдань, черги друку та ширини-першого пошуку, де кордон необхідно досліджувати в порядку виявлення.

stack: push(x), pop()      → both O(1), always at the same end (top)
queue: enqueue(x), dequeue() → both O(1), at opposite ends (back, front)

Both are typically built on an array (with a moving head/tail index,
or a ring buffer) or a linked list — either backing store gives O(1)
push/pop as long as you never need to reach into the middle.

Масиви проти зв’язних списків: безперервне збереження даних проти покажчиків

Масив зберігає елементи безперервно, тому будь-який індекс можна отримати безпосередньо за допомогою арифметики – O(1) випадковий доступ – але вставлення або видалення посередині означає зміщення кожного наступного елемента, що займає O(n). Зв’язний список зберігає кожен елемент у власному вузлі з покажчиком на наступний, тому вставлення або видалення є O(1), якщо ви вже маєте посилання на потрібне місце, але доступ до будь-якого заданого елемента означає перебіг ланцюга від голови, що займає O(n), і кожен вузол є окремим виділеним блоком пам’яті, розкиданим по оперативній пам’яті замість їх компактного розташування. Цей розкид має більше значення на практиці, ніж вказує Big-O: сучасні процесори отримують доступ до пам'яті порціями, розмір яких відповідає розміру кеш-лінії, тому безперервне розташування масиву означає, що багато елементів отримуються «задармо» в одній операції отримання, тоді як переслідування покажчиків у зв’язному списку запускає нове, повільне отримання пам'яті майже на кожному кроці – тому масиви зазвичай виграють у реальних бенчмарках навіть коли зв’язний список має таку ж асимптотичну складність.

Хеш-таблиці: перетворення пошуку на арифметику

Пошук значення у невідсортованому масиві займає O(n) – потрібно перевіряти кожен елемент у найгіршому випадку. Хеш-таблиця майже повністю обходить процес пошуку: хеш-функція перетворює ключ на число, яке потім зменшується за модулем відносно розміру таблиці для вибору бакета, і значення зберігається (або шукається) безпосередньо в цьому бакеті. Завдяки хорошій хеш-функції, яка рівномірно розподіляє ключі, вставка, пошук та видалення займають у середньому O(1). Колізії – два різних ключа потрапляють у один і той же бакет – обробляються або за ланцюговим методом (кожен бакет містить невеликий зв’язний список), або за відкритим адресуванням (проводиться пошук вперед до наступного вільного слота); будь-яким чином, продуктивність падає до O(n) лише тоді, коли таблиця стає надто повною, що й є причиною автоматичного перерозміщення та повторного хешування хеш-таблиці, коли коефіцієнт завантаження перевищує певний поріг, зазвичай близько 0.7.

Вибір між ними

Практичне правило полягає в тому, щоб назвати домінуючу операцію у вашому програмі та обрати структуру, яка робить її O(1) або близькою до цього: якщо потрібне збереження порядку та відкат з використанням вкладених операцій — використовуйте стек; якщо потрібно обробляти дані за принципом прибуття — використовуйте чергу; якщо необхідно часто вставляти елементи посередині, маючи посилання на конкретну позицію — використовуйте зв’язаний список; якщо потрібен швидкий пошук за ключем без вимоги до порядку — використовуйте хеш-таблицю; якщо потрібно як швидкий пошук, так і збереження відсортованого порядку — зверніться до збалансованого дерева, обміняючи O(1) пошук на O(log n) в обмін на підтримку даних у відсортованому стані.

Frequently asked questions

Спробуйте наживо

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