Создание эффективной реализации сортированного списка с использованием generics (стр. 2 из 2)

Существуют ситуации, когда нужно найти значение, ассоциированное с ключом, и если его нет, то вставить некоторое значение, ассоциированное с этим ключом. Если для решения этой задачи воспользоваться отдельными процедурами поиска и вставки, то общее время удвоится, так как процедура вставки (перед непосредственной вставкой значения) производит поиск места вставки, т.е. имеет место повторное (непродуктивное) выполнение по сути одной и той же операции (поиска). В принципе, если при поиске запоминать найденную позицию, то процедура вставки могла бы воспользоваться результатами функции поиска (при условии, что между поиском и вставкой не было никаких действий). Однако это привело бы к тому, что пользователя класса пришлось допустить в дебри реализации данной коллекции, и надежность работы алгоритмов, построенных по такому принципу, была бы крайне низка. С целью оптимизации я решил создать метод, который пытался бы найти ключ и, если не нашел, вставлял бы некоторое значение «по умолчанию» и позиционировался на него (а если нашел, то просто позиционировался). Это позволяет избавиться от лишней операции поиска в описанных выше случаях, так как после этой операции пользователь получает возможность работать с текущим значением (значением, на которое произошло позиционирование). При этом для чтения или модификации значения не требуется производить повторный поиск. Функцию, производящую позиционирование (или вставку и позиционирование), я решил назвать 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 осуществляется сдвижка памяти, тогда как время, затрачиваемое на вставку в Б+-дерево и двухуровневый массив, пренебрежимо мало.

Алгоритм Б+-деревьев интересен еще и тем, что при больших объемах скорость поиска в них становится даже больше, чем в массиве, за счет использования кэша процессора, куда попадают элементы высших уровней. Все зависит от объема. Чем больше объем хранящихся данных, тем большие преимущества дают Б+-деревья. Ну а явное их преимущество начинается с объемов, превышающих миллион элементов.