Рефераты | Рефераты по информатике, программированию | Создание эффективной реализации сортированного списка с использованием generics
Создание эффективной реализации сортированного списка с использованием genericsКатегория реферата: Рефераты по информатике, программированию Теги реферата: реферат мова, изложение язык Добавил(а) на сайт: Bajdavletov. Предыдущая страница реферата | 7 8 9 10 11 12 13 14 15 16 17 | Следующая страница реферата 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 осуществляется сдвижка памяти, тогда как время, затрачиваемое на вставку в Б+-дерево и двухуровневый массив, пренебрежимо мало.