Дерево ван Эмде Боаса: Швидкий Пошук на Обмежених Цілих Числах

Чому порівняльно-орієнтовані дерева мають обмеження швидкості

Стандартне збалансоване дерево пошуку, таке як дерево червоного-чорного кольору або дерево AVL, працює шляхом повторного порівняння цільового ключа з ключами, що зберігаються в дереві, та розгалуження наліво або направо. Оскільки кожен порівняльний крок дає лише одну біт інформації (чи є цільовий ключ меншим чи більшим), а дерево повинно мати можливість розрізняти серед n збережених елементів, аргументи теорії інформації показують, що будь-яка структура на основі порівняння потребує щонайменше кількість порівнянь пропорційна логарифму n у найгіршому випадку. Це не є недоліком жодної конкретної реалізації; це фундаментальний бар’єр для алгоритмів, які ніколи не запитують, чи цей ключ менший, дорівнює чи більший. Довгий час цей логарифмічний ліміт розглядалося як природний потолок для операцій з упорядкованих наборів, і величезні зусилля були спрямовані на побудову дерев, які надійно досягали його, такі як дерева червоного-чорного кольору, дерева AVL та B-дерева для зберігання даних на диску. Дерево ван Эмде Боаса повністю обходить цей бар’єр, відмовляючись грати в гру порівнянь. Воно припускає, що ключі є цілими числами з фіксованого, відомого всесвіту розміром U, тобто будь-який можливий ключ є цілим числом між нулем і U мінус один, і воно використовує фактичний бітовий шаблон кожного ключа для визначення того, як організувати зберігання. Оскільки алгоритм дивиться всередину представлення ключів, а не розглядає їх як чорні скриньки, які можна порівнювати лише між собою, інформаційно-теоретичний нижній ліміт для сортування та пошуку за допомогою порівняння просто не застосовується. Це той самий концептуальний крок, який дозволяє радіксалтному сортуванню обігнати нижній ліміт сортування за допомогою порівнянь: обидва обмінюються обмеженням (ключі повинні бути цілими числами в межах обмеженого діапазону) на значне збільшення швидкості. Дерево ван Эмде Боаса виносить цю ідею до логічного кінця, досягаючи часу запиту, який росте з логарифмом логарифма U, функція, яка так повільно зростає, що вона майже не змінюється навіть при астрономічному збільшенні U.

Рекурсивна Структура Кластеризації та Підсумовування

Елегантність дерева ван Эмде Боаса повністю полягає в його рекурсивній структурі. Дерево ван Эмде Боаса, побудоване над універсальним простором розміру U, не є однією великою плоской структурою; воно складається з приблизно з квадратного кореня від U менших дерев ван Эмде Боаса, названих кластерами, кожне з яких відповідає за безперервний блок приблизно з квадратного кореня від U можливих ключів, а також додаткову структуру підсумовування, яка сама є деревом ван Эмде Боаса зменшеного розміру, приблизно з квадратного кореня від U. Будь-який ключ у діапазоні від нуля до U мінус один може бути розділений на високу та нижню частини: висока частина ідентифікує кластер, до якого належить ключ, а нижча частина ідентифікує положення ключа в цьому кластері. Вставлення ключа означає рекурсивне вставлення нижньої частини у відповідний кластер і також рекурсивне вставлення високої частини в структуру підсумовування, щоб дерево запам'ятало, що цей конкретний кластер не порожній. Структура підсумовування таким чином діє як компактний індекс над кластерами саміми, відповідаючи на питання, які кластери зараз містять принаймні один елемент, без необхідності безпосередньо перевіряти кластери. Цей шаблон «половинчастого зменшення кількості бітів» (оскільки квадратний корінь від U відповідає приблизно меншій кількості бітів, ніж U) створює подвойно-логарифмічну часову складність: кожен рекурсивний виклик працює з універсальним простором з приблизно половиною кількості бітів свого батька, тому після лише логарифмічної кількості бітів «половин» (виміряної в логарифмі логарифма від U) рекурсія закінчується. Базовий випадок — це невеликий універсум, часто розміром 2, який можна обробити безпосередньо з кількома бітами та константним часом обліку, що завершує рекурсію. Кожен вузол у цій рекурсивній ієрархії також зберігає свій власний мінімум і максимум безпосередньо, невеликий, але важливий оптимізація, яка запобігає одному повному непотрібному рекурсивному кроку в багатьох операціях і дозволяє знайти найменші та найбільші елементи миттєво.

Знаходження сусідів: перестрибування замість сканування

Операція, яка найкраще демонструє мету структури підсумків, – це пошук наступника або попередника заданого ключа, тобто наступного більшого чи меншого збереженого елемента. Наївна структура повинна була б сканувати вперед або назад через сусідні ключі до тих пір, поки не знайдеться той, що дійсно присутній, що могло бути повільним, якщо збережені елементи рідкісні. Дерево ван Эмде Боаса уникає цього сканування повністю, консультуючись з підсумком. Припустимо, ми хочемо знайти наступник ключа x. Алгоритм спочатку обчислює високу частину ключа x для визначення того кластера, в якому він знаходиться, і перевіряє, чи містить той самий кластер будь-який елемент більший за нижню частину x; це робиться одним рекурсивним викликом до цього одного кластера. Якщо такий елемент існує, наступник знаходиться всередині того ж кластера, і пошук виконується після цього одного рекурсивного кроку. Якщо ні, алгоритм не сканує кожен наступний кластер по одному, шукаючи порожній. Замість цього він безпосередньо запитує структуру підсумків щодо наступника індексу поточного кластера, яку сама структура підсумків знаходить за подвійним логарифмом часу. Це миттєво визначає наступний не порожній кластер без торкання будь-яких міжкластерних порожніх кластерів і потім остаточний рекурсивний виклик знаходить мінімальний елемент, що зберігається в цьому кластері, який доступний миттєво, оскільки кожен кластер кешує свій власний мінімум. Це ключова хитрості, яка відрізняє дерево ван Эмде Боаса від простіших структур: підсумок дозволяє алгоритму безпосередньо перейти до точно потрібного сусіднього регіону одним рекурсивним викликом, а не платити вартість, пропорційну тому, скільки порожніх кластерів випадково знаходиться між точкою запиту та фактичною відповіддю. Оскільки як внутрішній перевірка кластера, так і пошук підсумків є операціями дерева ван Эмде Боаса на всесвіті приблизно квадратного кореня від початкового розміру, загальна рекурсивна вартість на рівні залишається обмеженою, і подвійний логарифмічний ліміт зберігається в усіх випадках.

Торгівля пам'яттю: Швидкість за рахунок простору

Унікальна швидкість дерева ван Эмде Боаса не безкоштовна. Її споживання пам’яті пропорційне розміру всесвіту U, тобто загальному діапазону можливих цілочисельних ключів, а не кількості елементів, які зберігаються, n. Наївна рекурсивна реалізація, яка неохоче виділяє масив кластерів і структуру підсумків для кожного можливого розміру всесвіту, навіть до вставлення будь-яких ключів, використовуватиме пам’ять, яка зростатиме з U незалежно від того, наскільки розрідженими є фактичні дані. Це контрастує зі структурами з порівнянням, якій споживання пам'яті завжди пропорційне лише n, кількості дійсно присутніх елементів, і ніколи не залежить від розміру простору ключів, з якого беруться ці елементи. Якщо всесвіт величезний, наприклад, якщо ключі мають 32-бітну або 64-бітну довжину, наївне дерево ван Эмде Боаса спробує виділити місце для мільярдів або квінтильйонів потенційних кластерів, що є повністю непрактичним. У реальності цю проблему пом’якшують більш обережне проектування, особливо за допомогою заміни неохоче виділених масивів хеш-таблицями, які створюють місце лише для кластерів, що містять елементи, що призводить до варіанту, часто званого y-fast trie або хешованою структурою ван Эмде Боаса, споживання пам’яті якої пропорційне n, а не U, за незначного постійного коефіцієнта уповільнення та додаткової складності хешування. Навіть з цими оптимізаціями структура має значно більший постійний коефіцієнт накладних витрат на операцію порівняно зі простим збалансованим деревом, оскільки кожна операція передбачає багатошарову рекурсивну виклик та перебіг структури. Ця торгівля — надзвичайно хороша асимптотична складність, придбана за рахунок значного споживання пам’яті та складності реалізації — є визначальним інженерним напруженням навколо цієї структури даних і пояснює, чому вона займає спеціалізовану нішу, а не замінює загального призначення відсортовані карти.

Де саме використовуються дерева ван Эмде Боаса

Враховуючи свою «кушність» у споживанні пам’яті, дерево ван Эмде Боаса рідко використовується як щоденна, загальнодоступна карта або словник. Завдання звичайного програмного забезпечення майже завжди віддають перевагу таким структурам, як червоні-чорні дерева, B-дерева чи прості хеш-таблиці, які забезпечують чудову практичну продуктивність без необхідності пропорційного споживання пам’яті всьому простору ключів. Дерево ван Эмде Боаса справді сяє там, де ключі гарантовано є цілими числами з невеликого, добре визначеного обмеженого діапазону, а кількість елементів достатньо велика, щоб подвоювання логарифмічного часу забезпечувало реальну виміркову перевагу над звичайним логарифмічним часом. Класичним застосуванням є черги пріоритетів, керовані цілими числами, наприклад, системи планування, де пріоритети або часові мітки є невеликими цілими числами, або маршрутизатори мереж, які виконують операції, такі як найдовший префіксний збій та підтримка наборів активних ідентифікаторів з’єднань або номерів портів, усі вони природно є областями цілих чисел, де швидкість справді має значення при великих обсягах трафіку. Воно також помітно виступає в якості навчального інструменту в курсах просунутих алгоритмів, оскільки воно так чітко демонструє, як структури на основі цілих чисел можуть уникнути нижньої межі, заснованої на порівняннях, роблячи його улюбленим прикладом у університетських курсах з проектування алгоритмів та в дослідженнях щодо цілочисельних структур даних. Деякі спеціалізовані області обчислювальної геометрії та обробки рядків також запозичують ідею рекурсивного розбиття, навіть якщо вони не використовують дерево ван Эмде Боаса доречно. Коротше кажучи, ніша реального застосування цієї структури вузька, але справжня: коли всесвіт можливих ключів обмежений і відомий заздалегідь, елементи складають тисячі або мільйони, а зменшення часу запиту до подвоєного логарифмічного дійсно має значення для застосування, дерево ван Эмде Боаса є серйозною та іноді необхідною опцією, незважаючи на те, що воно ніколи не замінить простіші загального призначення структури для повсякденної розробки.

Часті запитання

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

Усе, що вище, працює прямо у вашому браузері — відкрийте Van Emde Boas Tree: Blazing-Fast Search on Bounded Integers і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.