Создание эффективной реализации сортированного списка с использованием generics
Сергей Смирнов (Serginio1)
Так случилось, что я стал программистом 1С. Все прекрасно в этой среде, за исключением скорости. Эту проблему можно решить только одним способом: прямым доступом к файлам и обработкой результатов на компилируемом языке в памяти.
Так, для группирования данных нужны алгоритмы поиска и вставки. И мое сознание, отягощенное бухгалтерским учетом, не нашло ничего лучшего, чем использовать аналог TList (SortedList), представляющий собой динамический массив со свойствами «емкость» и «количество элементов».
Упорядоченность в этом массиве поддерживается с помощью компараторов, а при поиске используется алгоритм половинного деления с поиском нужной позиции i по ключу с условием (Items[i]>=Key) AND (Items[i-1]<Key). Если такого ключа нет, то все данные с позиции i переносятся на одну позицию в большую сторону. При этом используются процессорные команды MOVSW и MOVSB, которые выполняются очень быстро. При полном заполнении массива его размер увеличивается либо за счет свободных адресов, следующих за конечным адресом в массиве, либо с помощью выделения нового массива большей емкости с копированием данных из оригинала.
Но время шло, и объем группировок вышел за 10000 записей. Мой AMD K6 200 (мощный по тем временам компьютер) начал работать слишком меленно. И не удивительно – количество сдвигаемых элементов в среднем стало равно N2/4, то есть 108.
И вот как-то, после очередного обучения бухгалтеров бухгалтерии, пришла мысль. Зачем держать один большой массив, если можно его разбить на множество маленьких? Сказано – сделано. В течение двух минут я создал двухуровневый массив. Первый (верхний) уровень – это массив, элементами которого являются ссылки на массивы нижнего уровня. Второй из уровней (нижний) по сути, состоит из простых динамических массивов. Под простыми понимается то, что память под них выделяется заранее и впоследствии не перезанимается. Фактически этот массив представляет собой структуру, хранящую счетчик элементов и массив пар «ключ-значение». В дальнейшем я буду называть эти динамические массивы листовыми страницами (LeafPage).
| PLeafPage=^ TLeafPage; TLeafPage = Record // количество задействованных элементов в массиве KeyItems Count:Integer; // массив ссылок на пары «ключ-значение»KeyItems:Array[0..63] of Tobject;End;TLeafPageArray = Array of PleafPage;LeafPageArray : TLeafPageArray; |
Поиск проходил в 2 этапа. Сначала производится поиск массива, в котором может находиться искомый ключ. Для этого с искомым значением сравниваются значение ключей нулевых элементов массивов KeyItems с таким условием, чтобы значение ключа нулевого элемента массива было меньше или равнялось искомому, а значение нулевого элемента следующего массива превышало искомое.
Это можно выразить так:
| (LeafPageArray[j].KeyItems[0] <= Key) AND (LeafPageArray[j+1].KeyItems[0] > 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 в структуру родительского массива. |
| TNodeItem = Record Key : Tobject; LeafPage : PLeafPage;End;TNodeArray= Array of TNodeItem; | ||
| ПРИМЕЧАНИЕТаким образом, при поиске нужной листовой страницы нет необходимости обращаться к ее содержимому:(NodeArray[j].Key <= Key) AND (NodeArray[j + 1].Key > Key)Таким образом можно убить сразу двух зайцев – сохранить скорость поиска и резко увеличить скорость вставки. | ||
Когда объем группировок начал подходить к миллионам записей, этот алгоритм начал «тормозить» из-за увеличения размера массива верхнего уровня. Проблемы с копированием больших объемов данных вернулись. Чтобы избавиться от этой проблемы, можно применить тот же самый механизм, и разбить массив верхнего уровня на несколько подмассивов. Это приведет к созданию трехуровневого массива, а когда-нибудь, возможно, и четырехуровневого. Так что в принципе есть резон сразу создавать универсальный алгоритм, автоматически увеличивающий количество уровней и строящий дерево. Структура этого дерева включает страницы двух типов – узловые, содержащие массивы ссылок на нижележащие страницы, и листовые, содержащие отсортированные списки данных. Такое дерево называется B+-деревом. Однако разбирать подробно реализацию B+-деревьев в этой статье я не буду.
Реализация двухуровневого массива
На практике в большинстве случаев достаточно двухуровневых массивов. К тому же, их намного проще описывать. Они используют те же подходы, что и в Б+-деревьях. Так что рассмотрим реализацию именно двухуровневых массивов.
Вначале нужно определить структуру, которая будет хранить пары ключ + значение (для листовых страниц) и ключ + ссылка на страницу (для узловых страниц). В принципе, ссылку можно рассматривать как частный случай данных. Так что с помощью generic-ов можно описать единую структуру. Вот эта структура:
| internal struct KeyValuePair<K, V>{ internal K Key; internal V Value; public KeyValuePair(K key, V value){ Key = key; Value = value; }} |
Определим класс PageBase, с единственным полем Count.
| internal class PageBase{ public int Count;} |
Описание страницы, находящейся на нулевом уровне:
| internal class LeafPage<K, V> : PageBase{ public KeyValuePair<K, V>[] PageItems; // массивэлементов public LeafPage<K, V> PriorPage; // ссылканапредыдущуюстраницуpublic LeafPage<K, V> NextPage; // ссылка на следующую страницуpublic LeafPage() { Count = 0; PageItems = new KeyValuePair<K, V>[BTConst.MaxCount];}} |
PriorPage, NextPage нужны для навигации по дереву.
Основную функциональность двухуровневого массива реализует класс TwoLevelSortedDictionary:
| using Generic = System.Collections.Generic; public class TwoLevelSortedDictionary<K,V>: Generic.IDictionary<K,V> { internal LeafPage<K,V> CurrentLeafPage; // Текущаястраницасданнымиinternal struct NodeItem // Структура элементов верхнего уровня{ internal K Key; internal LeafPage<K,V> ChildPage; } internal NodeItem[] NodeArray; // Массивэлементов 2 уровняinternal int _pageCount; // Количество страниц 1 уровня internal int _currentPageIndex; // Текущий индекс элемента в массиве 2 уровняinternal int _currentElementIndex; // Текущийиндексв CurrentLeafPage internal Generic.IKeyComparer<K> _comparer; // Пользовательскийкомпаратор internal int _count; // Количествоэлементоввобъекте bool _selected; // Выбранлиэлемент internal int version=1; // Нужендляперечислителей public TwoLevelSortedDictionary(Generic.IKeyComparer<K> Comp) { this._comparer = Comp; CurrentLeafPage = new LeafPage<K,V>(); // Выделяемстраницу 1 уровня_pageCount = 1; } |
Двухуровневый массив позволяет осуществлять навигацию по находящимся в нем элементам. При этом возникает понятие текущего элемента, у которого можно считывать или устанавливать значение, и читать значение ключа. Для позиционирования на запись с некоторым ключом используется функция NavigateKey.
Алгоритм работы этой функции таков. Поскольку информация в массиве всегда упорядочена, то поиск можно осуществлять с помощью алгоритма бинарного поиска (то есть половинного деления). Единственная проблема, не позволяющая использовать классический алгоритм напрямую – это то, что, что массив состоит из двух уровней. Поэтому алгоритм поиска разделяется на два этапа. На первом этапе проверяется, есть ли массив верхнего уровня. Если есть, то в нем ищется страница, на которой может находиться искомый элемент. Если массива верхнего уровня нет, в качестве страницы, на которой будет производиться дальнейший поиск, используется единственная существующая страница.
На втором этапе производится классический бинарный поиск по ключу в сортированном массиве.
| public bool NavigateKey(K key){ // Устанавливаем индекс элемента в 0. _currentElementIndex = 0; // Если есть второй уровень... if (_pageCount > 1) { // Перебираем грани int hi = _pageCount - 1;int lo = 0; while (lo <= hi) { int i = (lo + hi) >> 1; int result = _comparer.Compare(NodeArray[i].Key, key); if (result < 0) lo = i + 1; else {hi = i - 1; if (result == 0) { // Ключ найден на 2 уровне. Устанавливаем текущую // страницу CurrentLeafPage. _currentPageIndex = i;CurrentLeafPage = NodeArray[_currentPageIndex].ChildPage; _selected = true;return true; } } } // Ключ не найден на 2 уровне. // Проверяем на возможность того, что искомый ключ – // наименьший из имеющихся в объекте. if (hi < 0) { // Данный ключ меньше наименьшего хранимого ключа. // Встаем на самый первый элемент двухуровневого массива _currentPageIndex = 0; CurrentLeafPage = NodeArray[_currentPageIndex].ChildPage;_selected = false; // Возвращаем информацию о том, что ключ не найден. return false; } else { // Данный ключ попадает в диапазон ключей нижележащей страницы. // Изменяем текущую страницу CurrentLeafPage на найденную дочернюю// страницу CurrentLeafPage = NodeArray[_currentPageIndex].ChildPage;// Устанавливаем текущий индекс ключа на листовой странице в 1, // т.к. 0 ужепроверяли. _currentElementIndex = 1;} } // Пытаемся найти индекс искомого ключа или индекс, в котором он должен // был находиться. hi = CurrentLeafPage.Count - 1;lo = _currentElementIndex; while (lo <= hi) { int i = (lo + hi) >> 1; int result = _comparer.Compare(CurrentLeafPage.PageItems[i].Key, key); if (result < 0) lo = i + 1; else { hi = i - 1; if (result == 0) { // Нашли! _currentElementIndex = i; _selected = true; return true; } } } // Ненашли... _selected = false; // Помещаемв _currentElementIndex позициювкоторую// можно добавить элемент с искомым ключом. _currentElementIndex = lo; return false;}// Процедура вставки в текущую позициюprivate void Insert(K Key){ // Вставляем ключ в текущую позицию, расширяя тем самым массив на 1 элемент. // Сдвигаем элементы, чтобы освободить место для вставляемого.Array.Copy(CurrentLeafPage.PageItems, _currentElementIndex, CurrentLeafPage.PageItems, _currentElementIndex + 1, CurrentLeafPage.Count - _currentElementIndex);// Увеличиваем количество хранимых элементов на странице и вставляем ключ.CurrentLeafPage.Count++; CurrentLeafPage.PageItems[_currentElementIndex].Key = Key; if (_currentElementIndex==0) NodeArray[_currentPageIndex].Key = key;version++; // Произошли изменения, увеличиваем текущую версию. // // Если текущая страница листовая полностью заполнена, // то существуют 2 варианта. Можно либо перенести элемент с текущей // страницы на соседнюю, либо разбить страницу на 2.// if (CurrentLeafPage.Count == BTConst.MaxCount){ // Страница полностью заполнена. // Если второго уровня нет... if (_pageCount == 1) { // ... то создаем второй уровень. // // Для этого делим текущую страницу пополам...LeafPage<K,V> NewPage = new LeafPage<K,V>();// ...исправляем ссылки в полях NextPage и PriorPage // чтобы можно было осуществлять сквозную навигацию // по листовым страницам. CurrentLeafPage.NextPage = NewPage; NewPage.PriorPage = CurrentLeafPage; // Перемещаем половину элементов исходного массива в новый.Array.Copy(CurrentLeafPage.PageItems, BTConst.MidlCount, NewPage.PageItems, 0, 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) { // Изменяем значение текущей страницы на новое... CurrentLeafPage = NewPage; // ... и текущего индекса на ней. _currentElementIndex -= BTConst.MidlCount; } } else { // Если второй уровень уже существует. // Если есть страница слева от текущей...LeafPage<K,V> LeftPage = CurrentLeafPage.PriorPage;if (LeftPage != null) { // ... и она заполнена менее, чем на 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; } else { _currentElementIndex -= MoveCount; CurrentLeafPage.Count -= MoveCount; LeftPage.Count += MoveCount;} return; } } // Если с левой страницей не получилось, попробуем с правой. // Код этого шага аналогичен вышеприведенному. // Его можно найти в файле, сопровождающем статью.... // Не получилось перебросить элементы на соседние страницы, // так как они заполнены. // Выделяем новую страницу аналогично тому, как это делалось выше, // при выделении верхнего уровня, за тем исключением, что нужно // скорректировать ссылки на близлежащие листовые страницы. // Этот код пропущен для краткости.... // Вставляем ссылку на новую страницу в массив верхнего уровня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);NodeArray = NewNodeArray; } } } } |
Процедуру удаления элемента из двухуровневого массива я здесь приводить не буду. Ее код можно найти в файле, приложенном к статье. Больший интерес представляет функция поиска индекса в двухуровневом массиве.