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

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

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

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

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

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

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

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

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