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

{

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