Создание эффективной реализации сортированного списка с использованием generics
//
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;
}
}
}
}
Процедуру удаления элемента из двухуровневого массива я здесь приводить не буду. Ее код можно найти в файле, приложенном к статье. Больший интерес представляет функция поиска индекса в двухуровневом массиве.
Существуют ситуации, когда нужно найти значение, ассоциированное с ключом, и если его нет, то вставить некоторое значение, ассоциированное с этим ключом. Если для решения этой задачи воспользоваться отдельными процедурами поиска и вставки, то общее время удвоится, так как процедура вставки (перед непосредственной вставкой значения) производит поиск места вставки, т.е. имеет место повторное (непродуктивное) выполнение по сути одной и той же операции (поиска). В принципе, если при поиске запоминать найденную позицию, то процедура вставки могла бы воспользоваться результатами функции поиска (при условии, что между поиском и вставкой не было никаких действий). Однако это привело бы к тому, что пользователя класса пришлось допустить в дебри реализации данной коллекции, и надежность работы алгоритмов, построенных по такому принципу, была бы крайне низка. С целью оптимизации я решил создать метод, который пытался бы найти ключ и, если не нашел, вставлял бы некоторое значение «по умолчанию» и позиционировался на него (а если нашел, то просто позиционировался). Это позволяет избавиться от лишней операции поиска в описанных выше случаях, так как после этой операции пользователь получает возможность работать с текущим значением (значением, на которое произошло позиционирование). При этом для чтения или модификации значения не требуется производить повторный поиск. Функцию, производящую позиционирование (или вставку и позиционирование), я решил назвать 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<T>).
«QuickDictionary (прямой доступ)» – то же, что и предыдущее, но с прямым доступом к содержимому хеш-таблицы.
«Dictionary» – это generic-реализация абстракции Dictionary на базе хеш-таблицы. Входит в стандартную библиотеку .NET Framework.
«TLSD (через индексатор)» – TwoLevelSortedDictionary, generic-реализация двухуровневого сортированного массива. Доступ к данным осуществляется через индексатор (реализацию интерфейса IDictionary<T>). При вставке производится повторный поиск.
«TLSD (прямой доступ)» – то же, что и предыдущее, но вставка производится в позицию. найденную при поиске и доступ к содержимому коллекции производится напрямую.
«Б+-дерево (прямой доступ)» – generic-реализация Б+-дерева.
Из этих тестов видно, что если у Влада Чистякова в
статье
«Коллекции
в .NET Framework Class Library» (из этого же номера журнала) хеш-таблица и
сортированный список различаются по скорости примерно в 4 раза, то здесь – аж в
16 раз. Если же сравнивать Dictionary и TwoLevelSortedDictionary, то их
скорость различается менее чем в 3 раза.
Деревья выигрывают у MySortedDictionary только за счет времени вставки, так как при вставке в MySortedDictionary осуществляется сдвижка памяти, тогда как время, затрачиваемое на вставку в Б+-дерево и двухуровневый массив, пренебрежимо мало.
Алгоритм Б+-деревьев интересен еще и тем, что при больших объемах скорость поиска в них становится даже больше, чем в массиве, за счет использования кэша процессора, куда попадают элементы высших уровней. Все зависит от объема. Чем больше объем хранящихся данных, тем большие преимущества дают Б+-деревья. Ну а явное их преимущество начинается с объемов, превышающих миллион элементов.