Создание эффективной реализации сортированного списка с использованием generics. Реферат. Информатика, ВТ, телекоммуникации.
👉🏻👉🏻👉🏻 ВСЯ ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻
Вы можете узнать стоимость помощи в написании студенческой работы.
Помощь в написании работы, которую точно примут!
Похожие работы на - Создание эффективной реализации сортированного списка с использованием generics
Скачать Скачать документ
Информация о работе Информация о работе
Нужна качественная работа без плагиата?
Не нашел материал для своей работы?
Поможем написать качественную работу Без плагиата!
Создание эффективной реализации сортированного списка
с использованием generics
Так случилось, что я стал программистом 1С. Все
прекрасно в этой среде, за исключением скорости. Эту проблему можно решить
только одним способом: прямым доступом к файлам и обработкой результатов на
компилируемом языке в памяти.
Так, для группирования данных нужны алгоритмы поиска и
вставки. И мое сознание, отягощенное бухгалтерским учетом, не нашло ничего
лучшего, чем использовать аналог TList (SortedList), представляющий собой
динамический массив со свойствами «емкость» и «количество элементов».
Упорядоченность в этом массиве поддерживается с помощью
компараторов, а при поиске используется алгоритм половинного деления с поиском
нужной позиции i по ключу с условием (Items[i]>=Key) AND
(Items[i-1] Key)
Алгоритм поиска на нижнем уровне аналогичен поиску в
одномерном массиве. При полном заполнении KeyItems выделяется новый PLeafIPage,
в который копируется половина данных. Ссылка на новый массив вставляется в
массив LeafPageArray в позицию на 1 больше текущей. При этом количество кода
было менее 100 строк.
Такой подход позволил резко сократить объем копируемой
памяти – так как количество копируемых элементов никогда не превышает 64. Тем
самым удалось избежать замедления работы массива при его росте.
И не удивительно, т.к. количество
переносимых элементов стало равно (N / 64) * 642 / 4 + (N / 64)2 / 4 = N * k
/ 4 + (N / k)2 / 4. Здесь к – емкость страницы, но учитывая, что страницы
заполняются не полностью, смело можно составить приблизительную формулу
расчета общего количества операций копирования: N * k / 2 + (N / k)2 / 2,
оптимальное значение К будет K(N) = (2N)-3, и соответственно, 643 – вполне
приемлемый размер страницы для хранения данных в этом классе. Отношение
количества копируемых элементов в одномерном массиве к двухуровневому составило
N / (k + N / k2) / 2. В любом случае это отношение очень велико. Единственный
минус этого алгоритма в замедлении поиска, так как доступ к ключу
производится через дополнительную ссылку. Для исправления этого недостатка
достаточно включить нулевой элемент KeyItems в структуру родительского
массива.
Таким образом, при поиске
нужной листовой страницы нет необходимости обращаться к ее содержимому:
(NodeArray[j].Key
<= Key) AND (NodeArray[j + 1].Key > Key)
Таким образом можно убить
сразу двух зайцев – сохранить скорость поиска и резко увеличить скорость
вставки.
Когда объем группировок начал подходить к миллионам
записей, этот алгоритм начал «тормозить» из-за увеличения размера массива
верхнего уровня. Проблемы с копированием больших объемов данных вернулись.
Чтобы избавиться от этой проблемы, можно применить тот же самый механизм, и
разбить массив верхнего уровня на несколько подмассивов. Это приведет к
созданию трехуровневого массива, а когда-нибудь, возможно, и четырехуровневого.
Так что в принципе есть резон сразу создавать универсальный алгоритм,
автоматически увеличивающий количество уровней и строящий дерево. Структура этого
дерева включает страницы двух типов – узловые, содержащие массивы ссылок на
нижележащие страницы, и листовые, содержащие отсортированные списки данных.
Такое дерево называется B+-деревом. Однако разбирать подробно реализацию
B+-деревьев в этой статье я не буду.
На практике в большинстве случаев достаточно
двухуровневых массивов. К тому же, их намного проще описывать. Они используют
те же подходы, что и в Б+-деревьях. Так что рассмотрим реализацию именно
двухуровневых массивов.
Вначале нужно определить структуру, которая будет
хранить пары ключ + значение (для листовых страниц) и ключ + ссылка на страницу
(для узловых страниц). В принципе, ссылку можно рассматривать как частный
случай данных. Так что с помощью generic-ов можно описать единую структуру. Вот
эта структура:
public
KeyValuePair(K key, V value)
Определим класс PageBase, с единственным полем Count.
Описание страницы, находящейся на нулевом уровне:
internal class
LeafPage : PageBase
public
KeyValuePair[] PageItems; // массив элементов
public
LeafPage PriorPage; // ссылка на предыдущую страницу
public LeafPage NextPage; // ссылка на
следующую страницу
PageItems =
new KeyValuePair[BTConst.MaxCount];
PriorPage, NextPage нужны для навигации по дереву.
Основную функциональность двухуровневого массива
реализует класс TwoLevelSortedDictionary:
using Generic =
System.Collections.Generic;
public class
TwoLevelSortedDictionary: Generic.IDictionary
internal struct NodeItem // Структура элементов
верхнего уровня
internal
LeafPage ChildPage;
internal
NodeItem[] NodeArray; // Массив элементов 2 уровня
internal int _pageCount; // Количество страниц 1
уровня
internal int
_currentPageIndex; // Текущий индекс элемента в массиве 2 уровня
internal int _currentElementIndex; // Текущий индекс в
CurrentLeafPage
internal
Generic.IKeyComparer _comparer; // Пользовательский компаратор
internal int
_count; // Количество элементов в объекте
bool
_selected; // Выбран ли элемент
internal int
version=1; // Нужен для перечислителей
public
TwoLevelSortedDictionary(Generic.IKeyComparer Comp)
CurrentLeafPage = new LeafPage(); // Выделяем страницу 1 уровня
Двухуровневый массив позволяет осуществлять навигацию
по находящимся в нем элементам. При этом возникает понятие текущего элемента, у
которого можно считывать или устанавливать значение, и читать значение ключа.
Для позиционирования на запись с некоторым ключом используется функция
NavigateKey.
Алгоритм работы этой функции таков. Поскольку
информация в массиве всегда упорядочена, то поиск можно осуществлять с помощью
алгоритма бинарного поиска (то есть половинного деления). Единственная
проблема, не позволяющая использовать классический алгоритм напрямую – это то,
что, что массив состоит из двух уровней. Поэтому алгоритм поиска разделяется на
два этапа. На первом этапе проверяется, есть ли массив верхнего уровня. Если
есть, то в нем ищется страница, на которой может находиться искомый элемент.
Если массива верхнего уровня нет, в качестве страницы, на которой будет
производиться дальнейший поиск, используется единственная существующая
страница.
На втором этапе производится классический бинарный
поиск по ключу в сортированном массиве.
// Устанавливаем индекс
элемента в 0.
int result
= _comparer.Compare(NodeArray[i].Key, key);
// Ключ найден на
2 уровне. Устанавливаем текущую
// страницу
CurrentLeafPage.
CurrentLeafPage =
NodeArray[_currentPageIndex].ChildPage;
// Проверяем на
возможность того, что искомый ключ –
// наименьший из
имеющихся в объекте.
// Данный ключ меньше
наименьшего хранимого ключа.
// Встаем на самый
первый элемент двухуровневого массива
CurrentLeafPage = NodeArray[_currentPageIndex].ChildPage;
// Возвращаем
информацию о том, что ключ не найден.
// Данный ключ
попадает в диапазон ключей нижележащей страницы.
// Изменяем текущую
страницу CurrentLeafPage на найденную дочернюю
// Устанавливаем текущий индекс ключа на листовой
странице в 1,
// Пытаемся найти индекс
искомого ключа или индекс, в котором он должен
int result =
_comparer.Compare(CurrentLeafPage.PageItems[i].Key, key);
// Помещаем в
_currentElementIndex позицию в которую
// можно добавить элемент с искомым ключом.
// Процедура вставки в текущую
позицию
// Вставляем ключ в
текущую позицию, расширяя тем самым массив на 1 элемент.
// Сдвигаем элементы,
чтобы освободить место для вставляемого.
Array.Copy(CurrentLeafPage.PageItems,
_currentElementIndex,
CurrentLeafPage.PageItems,
_currentElementIndex + 1,
CurrentLeafPage.Count - _currentElementIndex);
// Увеличиваем количество хранимых элементов на
странице и вставляем ключ.
CurrentLeafPage.PageItems[_currentElementIndex].Key = Key;
NodeArray[_currentPageIndex].Key = key;
version++; // Произошли изменения, увеличиваем
текущую версию.
// Если текущая страница
листовая полностью заполнена,
// то существуют 2
варианта. Можно либо перенести элемент с текущей
// страницы на соседнюю,
либо разбить страницу на 2.
if
(CurrentLeafPage.Count == BTConst.MaxCount)
// Страница полностью
заполнена.
// ... то создаем
второй уровень.
// Для этого делим
текущую страницу пополам...
LeafPage NewPage = new
LeafPage();
// ...исправляем ссылки в полях NextPage и PriorPage
// чтобы можно было
осуществлять сквозную навигацию
CurrentLeafPage.NextPage = NewPage;
NewPage.PriorPage =
CurrentLeafPage;
// Перемещаем
половину элементов исходного массива в новый.
Array.Copy(CurrentLeafPage.PageItems,
BTConst.MidlCount,
Array.Clear(CurrentLeafPage.PageItems, BTConst.MidlCount, BTConst.MidlCount);
// Создаем массив второго уровня и помещаем в него
ссылки
NodeArray = new
NodeItem[BTConst.MaxCount];
_pageCount = 2; // Теперь страниц две.
NodeArray[0].Key = CurrentLeafPage.PageItems[0].Key;
NodeArray[0].ChildPage = CurrentLeafPage;
NodeArray[1].Key = NewPage.PageItems[0].Key;
NodeArray[1].ChildPage = NewPage;
// Задаем количество
элементов на страницах.
CurrentLeafPage.Count =
BTConst.MidlCount;
NewPage.Count = BTConst.MidlCount;
// Если текущий элемент переместился на новую
страницу...
if (_currentElementIndex
>= BTConst.MidlCount)
// Изменяем
значение текущей страницы на новое...
// ... и текущего
индекса на ней.
_currentElementIndex -= BTConst.MidlCount;
// Если второй
уровень уже существует.
// Если есть страница
слева от текущей...
LeafPage LeftPage =
CurrentLeafPage.PriorPage;
// ... и она
заполнена менее, чем на MaxFill (3/4)...
if (LeftPage.Count <= BTConst.MaxFill)
// можно
перекинуть значения на левую страницу.
// Находим нужное
количесво элементов для переброски.
int MoveCount = (BTConst.MaxCount -
LeftPage.Count) / 2;
// Перемещаем начальные элементы из текущей страницы
// в конец левой
страницы...
Array.Copy(CurrentLeafPage.PageItems, 0,
LeftPage.PageItems, LeftPage.Count,
MoveCount);
// И сдвигаем оставшиеся элементы страницы в начало.
Array.Copy(CurrentLeafPage.PageItems,
MoveCount,
CurrentLeafPage.PageItems, 0, CurrentLeafPage.Count - MoveCount);
// Затираем перемещенные элементы.
Array.Clear(CurrentLeafPage.PageItems,
CurrentLeafPage.Count - MoveCount, MoveCount);
// Так как
нулевой элемент на странице изменился, необходимо
//
откорректировать значение ключа, ссылающегося на эту страницу
// в массиве
верхнего уровня.
// Исправляем
значение ключа в верхнем уровне так, чтобы его
// значение было
равным значению ключа нулевого элемента
//
соответствующей листовой страницы.
NodeArray[_currentPageIndex].Key = CurrentLeafPage.PageItems[0].Key;
// Текущий ключ
был перемещен.
// Если он
переместился на левую страницу, изменяем значение
// текущей
страницы и текущего индекса на ней так, чтобы они
// указывали на вставленный ключ.
if
(_currentElementIndex < MoveCount)
_currentElementIndex += LeftPage.Count;
CurrentLeafPage.Count -= MoveCount;
LeftPage.Count += MoveCount;
CurrentLeafPage = LeftPage;
_currentElementIndex -= MoveCount;
CurrentLeafPage.Count -= MoveCount;
LeftPage.Count += MoveCount;
// Если с левой
страницей не получилось, попробуем с правой.
// Код этого шага
аналогичен вышеприведенному.
// Его можно найти в
файле, сопровождающем статью.
// Не получилось
перебросить элементы на соседние страницы,
// Выделяем новую
страницу аналогично тому, как это делалось выше,
// при выделении
верхнего уровня, за тем исключением, что нужно
// скорректировать
ссылки на близлежащие листовые страницы.
// Этот код пропущен
для краткости.
// Вставляем ссылку
на новую страницу в массив верхнего уровня
Array.Copy(NodeArray, _currentPageIndex +
1, NodeArray,
_currentPageIndex + 2, _pageCount - _currentPageIndex - 1);
NodeArray[_currentPageIndex + 1].Key = NewPage.PageItems[0].Key;
NodeArray[_currentPageIndex + 1].ChildPage = NewPage;
CurrentLeafPage.Count = BTConst.MidlCount;
NewPage.Count = BTConst.MidlCount;
// Проверяем текущую
позицию вставляемого элемента (код пропущен)
// Если массив верхнего
уровня полностью заполнен просто увеличиваем
// его емкость в 2
раза (в Б+деревьях в этом случае выстраивается
if
(_pageCount == NodeArray.Length)
NodeItem[] NewNodeArray = new NodeItem[2 * _pageCount];
Array.Copy(NodeArray, 0, NewNodeArray, 0, _pageCount);
Процедуру удаления элемента из двухуровневого массива
я здесь приводить не буду. Ее код можно найти в файле, приложенном к статье.
Больший интерес представляет функция поиска индекса в двухуровневом массиве.
Существуют ситуации, когда нужно найти значение,
ассоциированное с ключом, и если его нет, то вставить некоторое значение,
ассоциированное с этим ключом. Если для решения этой задачи воспользоваться
отдельными процедурами поиска и вставки, то общее время удвоится, так как
процедура вставки (перед непосредственной вставкой значения) производит поиск
места вставки, т.е. имеет место повторное (непродуктивное) выполнение по сути
одной и той же операции (поиска). В принципе, если при поиске запоминать
найденную позицию, то процедура вставки могла бы воспользоваться результатами
функции поиска (при условии, что между поиском и вставкой не было никаких
действий). Однако это привело бы к тому, что пользователя класса пришлось
допустить в дебри реализации данной коллекции, и надежность работы алгоритмов,
построенных по такому принципу, была бы крайне низка. С целью оптимизации я
решил создать метод, который пытался бы найти ключ и, если не нашел, вставлял
бы некоторое значение «по умолчанию» и позиционировался на него (а если нашел,
то просто позиционировался). Это позволяет избавиться от лишней операции поиска
в описанных выше случаях, так как после этой операции пользователь получает
возможность работать с текущим значением (значением, на которое произошло
позиционирование). При этом для чтения или модификации значения не требуется
производить повторный поиск. Функцию, производящую позиционирование (или
вставку и позиционирование), я решил назвать NavigateOrInsertDefault. Вот ее
код:
public bool
NavigateOrInsertDefault(K Key)
bool result =
this.NavigateKey(Key);
// Нет такого элемента.
Вставляем в текущую позицию.
// Помещаем в текущую
позицию значение по умолчанию.
CurrentLeafPage.PageItems[_currentElementIndex].Value
= V.default;
Кроме точного позиционирования, можно производить
позиционирование на элемент, ключ которого больше, меньше, больше или равен и
меньше или равен некоторому значению. Этим занимается функция Navigate. В
качестве параметров она получает значение ключа и тип поиска. Тип поиска
задается следующим перечислением:
public bool
Navigate(K Key, NavigateFlag flag)
bool result =
this.NavigateKey(Key);
case
NavigateFlag.GreaterThanOrEqval:
goto case
NavigateFlag.GreaterThan;
if
(CurrentLeafPage.Count == _currentElementIndex)
if
(CurrentLeafPage.NextPage == null)
CurrentLeafPage = CurrentLeafPage.NextPage;
_currentElementIndex = 0;
case
NavigateFlag.LessThanOrEqval :
goto case
NavigateFlag.LessThan;
return
this.GetPriorRecord();
Вот, в общем-то, и все. По скорости поиска
двухуровневый массив превосходит своего более могучего собрата (Б+-дерево), но по
вставке начинает проигрывать где-то в районе миллиона элементов (а может, и
раньше, если хранимые значения или ключи имеют большой размер). Если сравнивать
по тестам поиска количества одинаковых слов в тексте, то получается такая
картина:
Заполнение
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).
«QuickDictionary (прямой доступ)» – то же, что и
предыдущее, но с прямым доступом к содержимому хеш-таблицы.
«Dictionary» – это generic-реализация абстракции
Dictionary на базе хеш-таблицы. Входит в стандартную библиотеку .NET Framework.
«TLSD (через индексатор)» – TwoLevelSortedDictionary,
generic-реализация двухуровневого сортированного массива. Доступ к данным
осуществляется через индексатор (реализацию интерфейса IDictionary).
При вставке производится повторный поиск.
«TLSD (прямой доступ)» – то же, что и предыдущее, но
вставка производится в позицию. найденную при поиске и доступ к содержимому
коллекции производится напрямую.
«Б+-дерево (прямой доступ)» – generic-реализация
Б+-дерева.
Из этих тестов видно, что если у Влада Чистякова в
статье «Коллекции в .NET
Framework Class Library» (из этого же номера журнала) хеш-таблица и
сортированный список различаются по скорости примерно в 4 раза, то здесь – аж в
16 раз. Если же сравнивать Dictionary и TwoLevelSortedDictionary, то их
скорость различается менее чем в 3 раза.
Деревья выигрывают у MySortedDictionary только за счет
времени вставки, так как при вставке в MySortedDictionary осуществляется
сдвижка памяти, тогда как время, затрачиваемое на вставку в Б+-дерево и
двухуровневый массив, пренебрежимо мало.
Алгоритм Б+-деревьев интересен еще и тем, что при
больших объемах скорость поиска в них становится даже больше, чем в массиве, за
счет использования кэша процессора, куда попадают элементы высших уровней. Все
зависит от объема. Чем больше объем хранящихся данных, тем большие преимущества
дают Б+-деревья. Ну а явное их преимущество начинается с объемов, превышающих
миллион элементов.
Для подготовки данной работы были использованы
материалы с сайта http://www.rsdn.ru/
Похожие работы на - Создание эффективной реализации сортированного списка с использованием generics Реферат. Информатика, ВТ, телекоммуникации.
Почему Так Сложно Изменить Себя Декабрьское Сочинение
Государственное Регулирование Экономического Роста Курсовая
Сочинения Цыбулько 2022 Егэ 36 Вариантов
Курсовая работа: Государственная власть как институт конституционного права
Курсовая работа: Понятие "жизнь" в "Евгении Онегине" А.С. Пушкина
Сочинение Про Молодого Киевлянина
Реферат по теме О категории репрезентации русского глагола
Реферат: Особенности правового статуса женщин, детей, рабов и душевнобольных по римскому праву
Широкополосный усилитель с подъемом АЧХ
Контрольная работа по теме Аудиторські послуги. Аудит матеріальних засобів. Аудиторська перевірка показників "незавершеного виробництва"
Абзац Для Курсовой По Госту
Контрольная Работа На Тему Систематизація Факторів Розміщення Залежно Від Їх Специфіки І Особливостей Впливу На Територіальну Організацію Виробництва
Реферат На Тему Всероссийское Общество Слепых
Сочинение Про Смелость 9.3 Огэ
Эссе На Тему Бухгалтер
Реферат: Архитектурно-планировочные и конструктивные решения постройки
Отчет По Практике На Тему Прохождение Практики В Оздоровительном Лагере "Волженка"
Доклад по теме Особенности методов современного экспериментально-математического естествознания. Системный подход как его важнейшая парадигма
Дипломная работа по теме Управление персоналом в сфере здравоохранения на примере косметологического центра ООО 'Лелея'
Реферат: Когнитивные процессы в психологии
Похожие работы на - Геополитическая характеристика Кавказско-Каспийского региона
Реферат: A People
Реферат: Auto bazes materiali tehniska sagade