();// Виділяємо сторінку 1 рівня
_pageCount = 1;
)
Дворівневий масив дозволяє здійснювати навігацію
по знаходилися в ньому елементів. При цьому виникає поняття поточного елемента, у
якого можна зчитувати або встановлювати значення, і читати значення ключа.
Для позиціонування на запис з деяким ключем використовується функція
NavigateKey.
Алгоритм роботи цієї функції такий. Оскільки
інформація в масиві завжди упорядкована, то пошук можна здійснювати за допомогою
алгоритму бінарного пошуку (тобто половинного поділу). Єдина
проблема, що не дозволяє використовувати класичний алгоритм прямо - це те,
що, що масив складається з двох рівнів. Тому алгоритм пошуку розділяється на
два етапи. На першому етапі перевіряється, чи є масив верхнього рівня. Якщо
є, то в ньому шукається сторінка, на якій може знаходитися шуканий елемент.
Якщо масиву верхнього рівня немає, як сторінки, на якій буде
проводитися подальший пошук, використовується єдина існуюча
сторінка.
На другому етапі проводиться класичний бінарний
пошук по ключу в сортованого масиві.
public bool NavigateKey (K key)
(
// Встановлюємо індекс елемента в 0.
_currentElementIndex = 0;
// Якщо є другий рівень ...
if (_pageCount> 1)
(
// перебираємо межі
int hi = _pageCount - 1;
int lo = 0;
while (lo <= hi)
(
int i = (lo + hi)>> 1;
int result =
_comparer.Compare (NodeArray [i]. Key, key);
if (result <0)
lo = i + 1;
else
(
hi = i - 1;
if (result == 0)
(
// Ключ знайдений на 2 рівні.
Встановлюємо поточну
// сторінку CurrentLeafPage.
_currentPageIndex = i;
CurrentLeafPage =
NodeArray [_currentPageIndex]. ChildPage;
_selected = true;
return true;
)
)
)
// Ключ не знайдено на 2 рівні.
// Перевіряємо на можливість того, що
шуканий ключ -
// найменший з наявних в об'єкті.
if (hi <0)
(
// Даний ключ менше найменшого
зберігається ключа.
// Встаємо на самий перший елемент
дворівневого масиву
_currentPageIndex = 0;
CurrentLeafPage =
NodeArray [_currentPageIndex]. ChildPage;
_selected = false;
// Повертаємо інформацію про те, що
ключ не знайдено.
return false;
)
else
(
// Даний ключ потрапляє в діапазон
ключів нижележащий сторінки.
// Змінюємо поточну сторінку CurrentLeafPage
на знайдену дочірню
// сторінку
CurrentLeafPage =
NodeArray [_currentPageIndex]. ChildPage;
// Встановлюємо поточний індекс ключа на листовий
сторінці в 1,
// тому що 0 вже перевіряли.
_currentElementIndex = 1;
)
)
// Намагаємося знайти індекс шуканого ключа або
індекс, в якому він повинен
// був знаходитися.
hi = CurrentLeafPage.Count - 1;
lo = _currentElementIndex;
while (lo <= hi)
(
int i = (lo + hi)>>
1;
int result =
_comparer.Compare (CurrentLeafPage.PageItems [i]. Key, key);
if (result <0)
lo = i + 1;
else
(
hi = i - 1;
if (result == 0)
(
// Знайшли!
_currentElementIndex =
i;
_selected = true;
return true;
)
)
)
// Не знайшли ...
_selected = false;
// Поміщаємо в
_currentElementIndex позицію в яку
// можна додати елемент з потрібним ключем.
_currentElementIndex = lo;
return false;
)
// Процедура вставки в поточну
позицію
private void Insert (K Key)
(
// Вставляємо ключ в поточну позицію,
розширюючи тим самим масив на 1 елемент.
// Зрушуємо елементи, щоб звільнити
місце для вставляється.
Array.Copy (CurrentLeafPage.PageItems,
_currentElementIndex,
CurrentLeafPage.PageItems,
_currentElementIndex + 1,
CurrentLeafPage.Count --
_currentElementIndex);
// Збільшуємо кількість збережених елементів на сторінці та вставляємо
ключ.
CurrentLeafPage.Count ++;
CurrentLeafPage.PageItems [_currentElementIndex]. Key = Key;
if (_currentElementIndex == 0)
NodeArray [_currentPageIndex]. Key = key;
version + +;// Відбулися зміни, збільшуємо поточну версію.
//
// Якщо поточна сторінка листова повністю
заповнена,
// то є 2 варіанти. Можна або
перенести елемент з поточною
// сторінки на сусідню, або розбити
сторінку на 2.
//
if (CurrentLeafPage.Count ==
BTConst.MaxCount)
(
// Сторінку повністю заповнена.
// Якщо другого рівня немає ...
if (_pageCount == 1)
(
// ... то створюємо другий рівень.
//
// Для цього ділимо поточну сторінку
навпіл ...
LeafPage NewPage
= New LeafPage ();
// ... виправляємо посилання в полях NextPage і PriorPage
// щоб можна було здійснювати наскрізну
навігацію
// по листовим сторінок.
CurrentLeafPage.NextPage = NewPage;
NewPage.PriorPage = CurrentLeafPage;
// переміщаємо половину елементів
вихідного масиву в новий.
Array.Copy (CurrentLeafPage.PageItems,
BTConst.MidlCount,
NewPage.PageItems, 0,
BTConst.MidlCount);
Array.Clear (CurrentLeafPage.PageItems, BTConst.MidlCount,
BTConst.MidlCount);
// Створюємо масив другого рівня і поміщаємо в нього
посилання
// на листові сторінки.
NodeArray = new
NodeItem [BTConst.MaxCount];
_pageCount = 2;// Тепер сторінок два.
NodeArray [0]. Key =
CurrentLeafPage.PageItems [0]. Key;
NodeArray [0]. ChildPage =
CurrentLeafPage;
NodeArray [1]. Key =
NewPage.PageItems [0]. Key;
NodeArray [1]. ChildPage = NewPage;
// Задаємо кількість елементів на
сторінках.
CurrentLeafPage.Count =
BTConst.MidlCount;
NewPage.Count =
BTConst.MidlCount;
// Якщо поточний елемент перемістився на нову
сторінку ...
if (_currentElementIndex> =
BTConst.MidlCount)
(
// Змінюємо значення поточної сторінки
на нове ...
CurrentLeafPage = NewPage;
// ... та поточного індексу на ній.
_currentElementIndex -=
BTConst.MidlCount;
)
)
else
(
// Якщо другий рівень вже існує.
// Якщо є сторінка ліворуч від
поточної ...
LeafPage LeftPage
= CurrentLeafPage.PriorPage;
if (LeftPage! = null)
(
// ... і вона заповнена менш, ніж на
MaxFill (3/4 )...
if (LeftPage.Count <= BTConst.MaxFill)
(
// можна перекинути значення на
ліву сторінку.
// Знаходимо потрібне колічесво
елементів для перекидання.
int MoveCount =
(BTConst.MaxCount - LeftPage.Count)/2;
// переміщаємо початкові елементи з поточної сторінки
// в кінець лівої сторінки ...
Array.Copy (CurrentLeafPage.PageItems, 0,
LeftPage.PageItems,
LeftPage.Count, MoveCount);
// І Зрушуємо залишилися елементи сторінки в початок.
Array.Copy (CurrentLeafPage.PageItems,
MoveCount,
CurrentLeafPage.PageItems, 0, CurrentLeafPage.Count - MoveCount);
// затираємо переміщені елементи.
Array.Clear (CurrentLeafPage.PageItems,
CurrentLeafPage.Count - MoveCount, MoveCount);
// Так як нульовий елемент на
сторінці змінився, необхідно
// відкоригувати значення ключа,
що посилається на цю сторінку
// в масиві верхнього рівня.
// Виправляємо значення ключа у верхньому
рівні так, щоб його
// значення було рівним значенню
ключа нульового елементу
// відповідної листовий
сторінки.
NodeArray [_currentPageIndex]. Key =
CurrentLeafPage.PageItems [0]. Key;
// Поточний ключ був переміщений.
// Якщо він перемістився на ліву
сторінку, змінюємо значення
// поточної сторінки і поточного
індексу на неї так, щоб вони
// вказували на вставлений ключ.
if
(_currentElementIndex
(
_currentElementIndex
+ = LeftPage.Count;
CurrentLeafPage.Count -= MoveCount;
LeftPage.Count + =
MoveCount;
CurrentLeafPage =
LeftPage;
)
else
(
_currentElementIndex
-= MoveCount;
CurrentLeafPage.Count -= MoveCount;
LeftPage.Count + =
MoveCount;
)
return;
)
)
// Якщо з лівого сторінкою не
вийшло, спробуємо з правого.
// Код цього кроку аналогічний
вищенаведеного.
// Його можна знайти у файлі,
супроводжує статтю.
...
// Не вийшло перекинути елементи
на сусідні сторінки,
// так як вони заповнені.
// Виділяємо нову сторінку аналогічно
тому, як це робилося вище,
// При виділенні верхнього рівня, за
винятком того, що потрібно
// скорегувати посилання на
прилеглі листові сторінки.
// Цей код пропущений для стислості.
...
// Вставляємо посилання на нову сторінку в
масив верхнього рівня
Array.Copy (NodeArray,
_currentPageIndex + 1, NodeArray,
_currentPageIndex + 2,
_pageCount - _currentPageIndex - 1);
NodeArray [_currentPageIndex + 1]. Key = NewPage.PageItems [0]. Key;
NodeArray [_currentPageIndex + 1]. ChildPage = NewPage;
CurrentLeafPage.Count =
BTConst.MidlCount;
NewPage.Count = BTConst.MidlCount;
// Перевіряємо поточну позицію
вставляється елементу (код пропущено)
...
// Якщо масив верхнього рівня
повністю заповнений просто збільшуємо
// його ємність у 2 рази (в Б + деревах у
цьому випадку вибудовується
// новий рівень).
if (_pageCount ==
NodeArray.Length)
(
NodeItem [] NewNodeArray
= New NodeItem [2 * _pageCount];
Array.Copy (NodeArray, 0,
NewNodeArray, 0, _pageCount);
NodeArray = NewNodeArray;
)
)
)
)
Процедуру видалення елемента з дворівневого масиву
я тут наводити не буду. Її код можна знайти в файлі, доданому до статті.
Більший інтерес представляє функція пошуку індексу в дворівневому масиві.
Існують ситуації, коли потрібно знайти значення,
асоційоване з ключем, і якщо його немає, то вставити деяке значення,
асоційоване з цим ключем. Якщо для вирішення цього завдання скористатися
окремими процедурами пошуку і вставки, то загальний час подвоїться, так як
процедура вставки (перед безпосереднім вставкою значення) здійснює пошук
місця вставки, тобто має місце повторне (непродуктивний) виконання по суті
однієї і тієї ж операції (пошуку). У принципі, якщо при пошуку запам'ятовувати
знайдену позицію, то процедура вставки могла б скористатися результатами
функції пошуку (за умови, що між пошуком і вставкою не було ніяких
дій). Однак це призвело б до того, що користувача класу довелося
допустити в нетрі реалізації даної колекції, і надійність роботи алгоритмів,
побудованих за таким принципом, була б украй низка. З метою оптимізації я
вирішив створити метод, який намагався б знайти ключ і, якщо не знайшов, вставляв
б деяке значення «за замовчуванням» і позиціонувався на нього (а якщо знайшов,
то просто позиціонувався). Це дозволяє позбутися від зайвої операції пошуку
в описаних вище випадках, тому що після цієї операції користувач отримує
можливість працювати з поточним значенням (значенням, на яке відбулося
позиціонування). При цьому для читання чи модифікації значення не потрібно
проводити повторний пошук. Функцію, що виробляє позиціонування (або
вставку і позиціонування), я вирішив назвати NavigateOrInsertDefault. Ось її
код:
public bool NavigateOrInsertDefault (K Key)
(
bool result =
this.NavigateKey (Key);
if (! result)
(
// Немає такого елемента. Вставляємо в
поточну позицію.
Insert (Key);
// Поміщаємо в поточну позицію значення по
замовчуванням.
CurrentLeafPage.PageItems [_currentElementIndex]. Value
= V.default;
_count ++;
)
// Стоїмо на потрібній позиції.
_selected = true;
return result;
)
Крім точного позиціонування, можна виробляти
позиціювання на елемент, ключ якого більше, менше, більше або дорівнює і
менше або дорівнює деякому значенню. Цим займається функція Navigate. У
Як параметри вона отримує значення ключа і варіант пошуку. Тип пошуку
задається наступним перерахуванням:
public
enum NavigateFlag: byte
(
Eqality,// ==
LessThan,// <
GreaterThan,//>
LessThanOrEqval,// <=
GreaterThanOrEqval//> =
)
А от реалізація цієї функції:
public bool Navigate (K Key, NavigateFlag flag)
(
bool result =
this.NavigateKey (Key);
switch (flag) (
case NavigateFlag.Eqality:
return result;
case NavigateFlag.GreaterThanOrEqval:
if (result)
return true;
goto case
NavigateFlag.GreaterThan;
case NavigateFlag.GreaterThan:
if (result)
_currentElementIndex ++;
if (CurrentLeafPage.Count
== _currentElementIndex)
(
if
(CurrentLeafPage.NextPage == null)
(
_selected = false;
return false;
)
else
(
CurrentLeafPage =
CurrentLeafPage.NextPage;
_currentElementIndex =
0;
)
)
_selected = true;
return true;
case
NavigateFlag.LessThanOrEqval:
if (result)
return true;
goto case
NavigateFlag.LessThan;
case NavigateFlag.LessThan:
return
this.GetPriorRecord ();
)
return result;
)
Ось, загалом-то, і все. За швидкістю пошуку
дворівневий масив перевершує свого більш могутнього побратима (Б +-дерево), але за
вставці починає програвати десь в районі мільйона елементів (а може, і
раніше, якщо зберігаються значення або ключі мають великий розмір). Якщо порівнювати
за тестами пошуку кількості однакових слів у тексті, то виходить така
картина:
Кількість слів у тексті = 528124
Кількість слів 20359
Заповнення
SortedDictionary
1.53828656994115
Заповнення QuickDictionary
(через індексатор) 0.189289700227264
Заповнення Dictionary 0.309536826607851
Заповнення TLSD (через індексатор) 0.860960541074354
Заповнення QuickDictionary
(прямий доступ) 0.08363381379477
Заповнення TLSD (прямий
доступ)
0.368364694395517
Заповнення Б +-дерева
(прямий доступ)
0.461643030049909
Заповнення MySortedDictionary 0.984015566224199
«SortedDictionary» - це generic-реалізація абстракції
Dictionary на базі масиву. Входить в стандартну бібліотеку. NET Framework.
Більш докладно див статтю 
«Колекції ст. NET Framework
Class Library ».
«MySortedDictionary»
- Аналог SortedDictionary, написаний мною. Відрізняється від оригіналу тим, що доступ до масиву
здійснюється безпосередньо. Я привів її, щоб порівняти швидкість її роботи з
тестами «TLSD (прямий доступ)» і «Б +-дерева (прямий доступ)», тому що в цих
тестах також здійснюється прямий доступ до вмісту колекцій. Ці
колекції відрізняються тільки використовуваними алгоритмами, і їх порівняння дозволить
побачити чистий різницю між алгоритмами.
«QuickDictionary (через індексатор)» - це моя
generic-реалізація хеш-таблиці. Доступ до даних здійснюється через індексатор
(реалізацію інтерфейсу IDictionary ).
«QuickDictionary (прямий доступ)» - те ж, що й
попереднє, але з прямим доступом до вмісту хеш-таблиці.
«Dictionary» - це generic-реалізація абстракції
Dictionary на базі хеш-таблиці. Входить в стандартну бібліотеку. NET Framework.
«TLSD (через індексатор)» - TwoLevelSortedDictionary,
generic-реалізація дворівневого сортованого масиву. Доступ до даних
здійснюється через індексатор (реалізацію інтерфейсу IDictionary ).
При вставці проводиться повторний пошук.
«TLSD (прямий доступ)» - те ж, що і попереднє, але
вставка проводиться у позицію. знайдену в процесі пошуку та доступ до вмісту
колекції здійснюється прямо.
«Б +-дерево (прямий доступ)» - generic-реалізація
Б +-дерева.
З цих тестів видно, що якщо у Влада Чистякова в
статті «Колекції
в. NET Framework Class Library »(з цього самого номера журналу) хеш-таблиця і
Сортувати список розрізняються за швидкістю приблизно в 4 рази, то тут - аж у
16 разів. Якщо ж порівнювати Dictionary і TwoLevelSortedDictionary, то їх
швидкість розрізняється менш ніж у 3 рази.
Дерева виграють у MySortedDictionary тільки за рахунок
часу вставки, тому що при вставці в MySortedDictionary здійснюється
сдвіжка пам'яті, тоді як час, що витрачається на вставку в Б +-дерево і
дворівневий масив, дуже мале.
Алгоритм Б +-дерев цікавий ще й тим, що при
великих обсягах швидкість пошуку в них стає навіть більше, ніж у масиві, за
рахунок використання кешу процесора, куди потрапляють елементи вищих рівнів. Всі
залежить від об'єму. Чим більше обсяг збережених даних, тим більші переваги
дають Б +-дерева. Ну а явне їх перевага починається з обсягів, що перевищують
мільйон елементів.
Список літератури
Для підготовки даної роботи були використані
матеріали з сайту http://www.rsdn.ru/
