Реферат: Создание эффективной реализации сортированного списка с использованием generics

PLeafPage=^ TLeafPage;

TLeafPage = Record

// количество задействованных элементов в массиве KeyItems

Count:Integer;

// массив ссылок на пары «ключ-значение»

KeyItems:Array[0..63] of Tobject;

End;

TLeafPageArray = Array of PleafPage;

LeafPageArray : TLeafPageArray;

(LeafPageArray[j].KeyItems[0] <= Key)

AND (LeafPageArray[j+1].KeyItems[0] > Key)

ПРИМЕЧАНИЕ

И не удивительно, т.к. количество переносимых элементов стало равно (N / 64) * 642 / 4 + (N / 64)2 / 4 = N * k / 4 + (N / k)2 / 4. Здесь к – емкость страницы, но учитывая, что страницы заполняются не полностью, смело можно составить приблизительную формулу расчета общего количества операций копирования: N * k / 2 + (N / k)2 / 2, оптимальное значение К будет K(N) = (2N)-3, и соответственно, 643 – вполне приемлемый размер страницы для хранения данных в этом классе. Отношение количества копируемых элементов в одномерном массиве к двухуровневому составило N / (k + N / k2) / 2. В любом случае это отношение очень велико. Единственный минус этого алгоритма в замедлении поиска, так как доступ к ключу производится через дополнительную ссылку. Для исправления этого недостатка достаточно включить нулевой элемент KeyItems в структуру родительского массива.

TNodeItem = Record

Key : Tobject;

LeafPage : PLeafPage;

End;

TNodeArray= Array of TNodeItem;

ПРИМЕЧАНИЕ

Таким образом, при поиске нужной листовой страницы нет необходимости обращаться к ее содержимому:

(NodeArray[j].Key <= Key) AND (NodeArray[j + 1].Key > Key)

Таким образом можно убить сразу двух зайцев – сохранить скорость поиска и резко увеличить скорость вставки.

internal struct KeyValuePair<K, V>

{

internal K Key;

internal V Value;

public KeyValuePair(K key, V value)

{

Key = key;

Value = value;

}

}

internal class PageBase

{

public int Count;

}

internal class LeafPage<K, V> : PageBase

{

public KeyValuePair<K, V>[] PageItems; // массивэлементов

public LeafPage<K, V> PriorPage; // ссылканапредыдущуюстраницу

public LeafPage<K, V> NextPage; // ссылка на следующую страницу

public LeafPage()

{

Count = 0;

PageItems = new KeyValuePair<K, V>[BTConst.MaxCount];

}

}

using Generic = System.Collections.Generic;

public class TwoLevelSortedDictionary<K,V>: Generic.IDictionary<K,V>

{

internal LeafPage<K,V> CurrentLeafPage; // Текущаястраницасданными

internal struct NodeItem // Структура элементов верхнего уровня

{

internal K Key;

internal LeafPage<K,V> ChildPage;

}

internal NodeItem[] NodeArray; // Массивэлементов 2 уровня

internal int _pageCount; // Количество страниц 1 уровня

internal int _currentPageIndex; // Текущий индекс элемента в массиве 2 уровня

internal int _currentElementIndex; // Текущийиндексв CurrentLeafPage

internal Generic.IKeyComparer<K> _comparer; // Пользовательскийкомпаратор

internal int _count; // Количествоэлементоввобъекте

bool _selected; // Выбранлиэлемент

internal int version=1; // Нужендляперечислителей

public TwoLevelSortedDictionary(Generic.IKeyComparer<K> Comp)

{

this._comparer = Comp;

CurrentLeafPage = new LeafPage<K,V>(); // Выделяемстраницу 1 уровня

_pageCount = 1;

}

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<K,V> NewPage = new LeafPage<K,V>();

// ...исправляем ссылки в полях 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<K,V> 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 < MoveCount)

{

_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;

}

}

}

}

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;

}

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