Образовательный портал Claw.ru
Всё для учебы, работы и отдыха
» Шпаргалки, рефераты, курсовые
» Сочинения и изложения
» Конспекты и лекции
» Энциклопедии

Вот, в общем-то, и все. По скорости поиска двухуровневый массив превосходит своего более могучего собрата (Б+-дерево), но по вставке начинает проигрывать где-то в районе миллиона элементов (а может, и раньше, если хранимые значения или ключи имеют большой размер). Если сравнивать по тестам поиска количества одинаковых слов в тексте, то получается такая картина:

Число слов в тексте=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. Более подробно см. статью Claw.ru | Рефераты по информатике, программированию | Создание эффективной реализации сортированного списка с использованием generics«Коллекции в .NET Framework Class Library».

«MySortedDictionary» – аналог SortedDictionary, написанный мною. Отличается от оригинала тем, что доступ к массиву осуществляется напрямую. Я привел ее, чтобы сравнить скорость ее работы с тестами «TLSD (прямой доступ)» и «Б+-дерева (прямой доступ)», так как в этих тестах также осуществляется прямой доступ к содержимому коллекций. Эти коллекции отличаются только используемыми алгоритмами, и их сравнение позволит увидеть чистую разницу между алгоритмами.

«QuickDictionary (через индексатор)» – это моя generic-реализация хеш-таблицы. Доступ к данным осуществляется через индексатор (реализацию интерфейса IDictionary<T>).

«QuickDictionary (прямой доступ)» – то же, что и предыдущее, но с прямым доступом к содержимому хеш-таблицы.

«Dictionary» – это generic-реализация абстракции Dictionary на базе хеш-таблицы. Входит в стандартную библиотеку .NET Framework.

«TLSD (через индексатор)» – TwoLevelSortedDictionary, generic-реализация двухуровневого сортированного массива. Доступ к данным осуществляется через индексатор (реализацию интерфейса IDictionary<T>). При вставке производится повторный поиск.

«TLSD (прямой доступ)» – то же, что и предыдущее, но вставка производится в позицию. найденную при поиске и доступ к содержимому коллекции производится напрямую.

«Б+-дерево (прямой доступ)» – generic-реализация Б+-дерева.

Из этих тестов видно, что если у Влада Чистякова в статье Claw.ru | Рефераты по информатике, программированию | Создание эффективной реализации сортированного списка с использованием generics«Коллекции в .NET Framework Class Library» (из этого же номера журнала) хеш-таблица и сортированный список различаются по скорости примерно в 4 раза, то здесь – аж в 16 раз. Если же сравнивать Dictionary и TwoLevelSortedDictionary, то их скорость различается менее чем в 3 раза.

Деревья выигрывают у MySortedDictionary только за счет времени вставки, так как при вставке в MySortedDictionary осуществляется сдвижка памяти, тогда как время, затрачиваемое на вставку в Б+-дерево и двухуровневый массив, пренебрежимо мало.


Рекомендуем скачать другие рефераты по теме: сочинения по русскому языку, личные сообщения.


Категории:




Предыдущая страница реферата | 7  8  9  10  11  12  13  14  15  16  17 |


Поделитесь этой записью или добавьте в закладки

   



Рефераты от А до Я