1,2,3,4,5, - я иду искать! Структуры данных. Поиск и хранение.
Запись от IGPIGP размещена 02.06.2017 в 17:46
Показов 6813
Комментарии 0
Метки algo
|
Самоупорядочиваемая структура данных. Близкие по теме структуры: Деревья поиска (B-tree, binary search tree), списки с пропусками (skip lists), Джуди массивы (Judy). Всё никак не соберусь привести в порядок результат одного из моих экспериментов на тему поисковых структур и расширяющихся массивов. Цель - получить класс который бы сочетал преимущества произвольного доступа массива и самоупорядочиваемость дерева поиска плюс расширяемость списка. Такой ход мысли не нов. Сочетание принципов разряженных массивов на указателях и на списках в сочетании с идеей преобразования индексов в логическом массиве в индексы в первичном массиве (хешированием) породило такой интересный тип как хеш-таблица или хеш-массив. Он удачно сочетает экономное расходование памяти, свойственное спискам и скорость доступа свойственную массивам. Его недостатки связаны с такими вещами как: - проблема поиска хеш-функции; //отдельная мощнейшая тема, которая не имеет общего теоретического обоснования - как рехешинг при чрезмерном удлинении списков коллизий; - природная несовместимость с упорядоченностью; Последнее свойство приводит к тому, что несмотря на достаточно высокую скорость доступа по значению, делать выборки упорядоченных диапазонов элементов не получается. Зато можно быстро работать с неупорядочиваемыми данными. Предлагаемый, в качестве решения контейнер не нуждается в хешинге, как таковом. Устойчив к порядку поступления данных. Позволяет быстро и одновременно поддерживать много упорядоченных структур на одном хранилище данных. Удобен при поиске диапазонов и наложении диапазонов (фильтрации). Класс PoliSearcher, который получился в результате, представляет собой комбинацию трёх контейнеров STL: std::vector и два std::list с параметрами в виде итераторов(!), чтобы не писать велосипед на указателях. За реализацию, просьба не пинать грубо, так как я по сути не кодер, а больше изобретатель. Мне нравится обдумывать концепцию. А когда она реализована, то сама реализация меня интересует гораздо меньше. Это не лень. Просто, каждому своё. Однако я с радостью приму любые замечания по реализации. Итак имеем два списка: -список-хранилище list<T> storage -список поиска list<list<t>::const_iterator> search_list Список storage создаётся из полученных данных, добавляемых в порядке поступления и в результате, это неупорядоченная последовательность объектов типа T. Список search_list это список, содержащий итераторы на объекты в storage. Этот список упорядочен. Логично, что в нём столько же элементов сколько и в storage, но они меньше в случае, если тип T больше размера итератора списка list<T>. А это почти всегда, так и есть. Нужно понять, что итератор списка search_list это итератор на итератор, то есть подобен указателю на указатель. Третий контейнер, это std::vector<NodePointer> bin_search_vec. Он содержит структуру NodePointer. Структура NodePointer очень проста. Она содержит итератор на элементы в search_list (то есть, list<list<t>::const_iterator>::iterator) и целое число len. Фактически, элемент вектора (NodePointer) содержит итератор на итератор в хранилище storage, поскольку search_list ( list<list<t>::const_iterator>) -список итераторов этого хранилища и итераторы этого списка это "итераторы на итераторы" уже самого нижнего неупорядоченного списка-хранилища. Данные итераторы соответствуют элементам в списке, но не подряд, а на некотором расстоянии len от следующего элемента списка на который указывает следующий элемент вектора. То есть, итераторы в элементе вектора (NodePointer) содержат итераторы контейнера списка поиска (search_list) которыми вектор как расчёска как бы прикреплён к этому списку (поиска). Расстояние между прутиками расчёски - len - количество элементов по списку ( которые нужно пробежать до следующего прутика - элемента списка поиска на который указывает следующий элемент вектора). Ни чего не понятно? Мне тоже! Поехали дальше) Далее я еще несколько раз и на все лады буду повторять сказание о расчёсках, стоящих на расчёсках. Тем, кто сталкивался с Джуди массивами будет легче. Как уже говорилось, NodePointer содержит также целое число len - фактическую длину цепочки которую возглавляет итератор из данного NodePointer до следующего, такого же. То есть, обычно между элементами списка которые продублированы в элементах вектора есть цепочки элементов, итераторов на которые в элементах вектора (NodePointer) нет. Такие цепочки аналогичны спискам коллизий в хеш-массивах (реализованных на цепочках). Расстояние len между парой элементов списка которые продублированы в элементах вектора выраженное в количестве элементов не превышает максимальной длины цепочки которая является константой chain_size, - параметром шаблона PoliSearcher, о котором будет сказано позже. То есть ещё раз: len это фактическая длина цепочки элементов search_list до следующего элемента списка, который содержится в объекте структуры NodePointer следующего элемента вектора. Там также (в NodePointer) определены два оператора - присваивания и приведения к типу T. То есть, кроме указанных контейнеров класс PoliSearcher содержит константу - параметр шаблона: size_t chain_size. Она задаёт максимальное значение len для любого элемента NodePointer вектора, то есть максимальный размер цепочки. Из важного, в объекте класса PoliSearcher, есть хотя бы один указатель на предикат сравнения для типа T. Это должен быть предикат семантически аналогичный оператору сравнения на строгое неравенство (больше или меньше). Данный предикат, вектор bin_search_vec и список search_list упакованы в класс Listed. А экземпляры Listed размещаются в map<Pred, Listed> где предикат каждого Listed является ключом. Данный map позволяет работать с некоторым количеством упорядоченных структур поиска - Listed (состоящих по сути из итераторов) на одном хранилище объектов и особого интереса не представляет. Самое интересное это совместная работа bin_search_vec и search_list, то есть работа самой по себе структуры поиска, - представленной классом Listed. Вектор bin_search_vec это достаточно интересный (я надеюсь) контейнер. Его элементы содержат итераторы указывающие на элементы search_list (это его итераторы), но с некоторым шагом не превышающим chain_size. В демонстрационном примере chain_size = 4. Это маленький шаг, но это для простоты демонстрации. Понятно, что когда все цепочки содержат максимальный len = chain_size = 4, количество элементов в векторе вчетверо меньше чем в списке search_list. Логично так же, что последовательность элементов вектора упорядочена, поскольку последовательность элементов списка search_list упорядочена. При поиске элементов используется бинарный поиск по вектору (std::upper_bound, std::lower_bound), за время около log2(N/chain_size) где N общее количество элементов списка. Логично, что такой поиск проводится не только для поиска как такового, но и при операциях вставки и удаления элементов. Вот как это работает при вставке: После отыскания нужного элемента вектора (указывающего на лидера соответствующей цепочки списка) нужно проверить цепочку на готовность принять новый элемент (l < chain_size) и если она заполнена то потребуется максимум N/(chain_size), или в среднем (N/(chain_size))/2 шагов. Далее, нужно переставить все итераторы лидеров цепочек между целевой вставки и найденной свободной цепочкой что потребует добавочно ещё (N/(chain_size))/2 шагов. После чего остаётся последовательно пройти по цепочке к месту вставки, что в худшем случае даст chain_size-1 шагов. А в среднем общая сложность: log2(N/(2*chain_size)) + N/chain_size + (chain_size-1)/2 что значительно меньше N/2 - сложности последовательного перебора хранилища. Таким образом, при вставке происходит добавление элемента в storage, а затем поиск целевой цепочки списка search_list, двоичным поиском по вектору и места вставки в цепочке, последовательным проходом по ней. Затем итератор на элемент в хранилище добавляется в цепочку. Если в ней нет места (len=chain_size=4) ищется цепочка в которой оно есть (len<chain_size=4) и по цепи перемещаются итераторы вектора "транспортируя" один элемент по цепочке так, что в той что была полной появляется одно свободное место. Фактически все итераторы в векторе между целевой для вставки цепочкой и цепочкой, где есть места переставляются на 1. Далее будет на рисунках показано как растёт список. Ещё раз. Если цепочка в которую должен быть вставлен элемент заполнена до отказа, то то идёт поиск цепочки (элемента вектора который содержит итератор её начала), в которой есть свободное место. Если такая цепочка найдена, то все итераторы вектора от целевого (указывающего на начало цепочки вставки которая занята до предела) до найденного (указывающего на начало недозаполненной цепочки) переставляются на одну от найденной позиции в сторону целевой, передавая таким образом свободное место в целевую цепочку. После окончания такой перестановки - найденная цепочка удлинится на один элемент, потому что она получит один элемент в обмен на утраченное свободное место от соседней цепочки, расположенной со стороны целевой. То есть при вставке ко времени бинарного поиска по вектору, прибавится последовательное прохождение по вектору для поиска и перстановки, где в худшем случае придётся инкрементировать или декрементировать N/chain_size указанных итераторов. В среднем вдвое меньше. Зато не нужно выполнять таких процедур как балансировка, если сравнивать с BST. В случае, если заполнены все цепочки и нет места для вставки элемента, то происходит удвоение элементов вектора. Можно применить разные варианты стратегии управления вектором. Это самый простой и наглядный. После удвоения размера вектора, размер цепочки везде станет вдвое меньше chain_size. Это удобно, так как структура готова к удалению и добавлению в равной степени и заставить её реалоцироваться можно лишь добавив столько же сколько в ней есть или удалив половину того что есть. При удалении всё происходит похоже, но предел когда размер вектора уменьшается вдвое, возникает когда все цепочки равны единице, то есть, размер вектора и его списка совпадают. Это и создаёт устойчивость к реалоку. Если в бинарное дерево поиска добавлять/удалять горсточку одинаковых или следующих строго друг за другом элементов, можно легко добиться режима в котором дерево будет постоянно балансироваться, что приведёт к резкому снижению скорости. Тут не важно AVL или R&W дерево имеется ввиду. Отличаться будут лишь размеры жменьки и технические подробности. Для более полного понимания принципа работы класса PoliSearcher, посмотрим как происходит заполнение хранилища с нуля. На рисунках Pic. 1, Pic. 2, Pic. 3, показано заполнение контейнеров пустого PoliSearcher последовательностью целых чисел: 9,3,6,1,12,5,2,4,7,10,8,11,15,13,14,16 =Рисунки - see the bottom=  На рисунках, глядя снизу - вверх, расположены три структуры: list<T> storage, list<list<t>::const_iterator> search_list и vector<NodePointer> bin_search_vec Тонкими ломанными линиями изображены логические связи между элементами структур. Связь между элементом search_list и элементом storage состоит в том, что итератор хранимый в search_list, в качестве элемента, указывает на соответствующий элемент storage. Связь между элементом bin_search_vec и элементом search_list состоит в том, что структура NodePointer данного элемента вектора, содержит итератор который указывыает на элемент хранимый в search_list. Это значит, что оба итератор вектора косвенно указывают на элемент storage (как указательна указатель). Пошаговое описание работы структуры поиска с сылками на рисунки (см. Test1.cpp) В данном примере создаётся Polisearch для типа int, заполняя хранилище данными из массива. Там же, прямо в конструкторе создаётся структура поиска с предикатом "меньше". Затем в созданный экземпляр добавляется структура поиска с предикатом "больше". Наиболее интересен процесс добавления элементов, копируемых из массива. Если все контейнеры вначале пусты то добавление одного элемента приведёт к появлению этого элемента в каждом из контейнеров. Вектор отметит что единственная цепочка списка поиска, "лидером" которой является единственный его (вектора) элемент, имеет один элемент (структура NodePointer с len=1). Итератор который лежит в ней, это копия единственного элемента списка поиска, который представляет из себя итератор на единственный элемент int 9 в списке хранилища. Далее добавление ещё трех элементов 3,6 и 1 приводит к тому что в хранилище в порядке поступления располагаются элементы 9,3,6,1. В списке поиска они упорядочены 1,3,6,9 а единственный элемент структуры NodPointer вектора содержит итератор на 1 в списке поиска и длину цепочки len=4. Добавление элемента 12 приводит к удвоению элементов вектора. Чтобы понять как происходит рост вектора нужно понять что такое поле norma класса PoliSearcher. norma - положительное целое число показывающее во сколько раз (от деления нацело) стартовый размер нормализованной цепочки ch_sz=chain_size/norma меньше максимального размера chain_size. Под нормализацией понимается способ выхода из пограничных состояний для вектора. Их два: -все len=1 и нужно удалить элемент //тут вектор придётся сократить -все len=chain_size и нужно вставить ещё один элемент //тут вектор нужно увеличить После нормализации, в новом векторе, chain_size / len = norma То есть, при norma = 2 размер вектора при нормализации: - в первом случае удваивается -во втором, - ополовинивается В действии для случая тестового примера (Test1.cpp - см. файл вложений внизу всего текста), это выглядит так: Поскольку поле norma в списке поиска задано по умолчанию и равно 2 то это значит, что стартовый размер новых цепочек будет вдвое меньше чем максимальный (chain_size=4), то есть стартовый len=2 у всех новых цепочек. Их следовательно будет вдвое больше прежнего количества то есть две. Далее добавление новых элементов ведет к росту общего количества элементов (размер хранилища) до 7. Размер первой и второй цепочек в этот момент становится равным 4 и 3, соответственно. Тут возникает ситуация когда размер списка поиска ещё не достиг максимума для двух цепочек по четыре, то есть восьми, но именно та цепочка, где должен размещаться элемент 4 уже заполнена четырьмя элементами: 1,2,3,5. Далее происходит поиск по свободным цепочкам на предмет поиска цепочки с len<4. Такая цепочка находится - она всего одна и в ней 3 элемента. Далее лидер этой цепочки - итератор в векторе переустанавливается на одну позицию в сторону цепочки запросившей свободное место в обмен на лишний элемент. Теперь лидер цепочки отдающей свободное место переустановлен с 6 на 5, а в цепочке где будет размещён 4 стало три элемента: 1,2,3 и после добавления 4 становится 1,2,3,4. Это изображено на рис. Pic. 2. Левое изображение показывает состояние после добавления элемента 4. Красный цвет отражает неготовность системы принят новый элемент 7, без нормализации. Иначе говоря, добавление нового элемента 7 вызывает новое удвоение вектора, так как две цепочки по четыре элемента заполнены полностью. А после нормализации, новый вектор из четырёх элементов, готов принять ещё восемь (или отдать четыре и сократиться вдвое), после чего произойдет новое удвоение. Вид после удвоения с 4 до 8 показан на рис. Pic. 3. При удалении элементов, они извлекаются из цепочек и цепочки перестраиваются без изменения размера вектора до тех пор пока в каждой цепочке не останется по одному элементу. В такой момент количества элементов вектора и списка равны между собой. В этом случае, дальнейшее удаление без уменьшения размера вектора невозможно. Уменьшения вектора при norma=2 происходит тоже ровно вдвое. При этом новый размер каждой цепочки равен 2 и она готова как к росту так и дальнейшему удалению без изменения размера вектора пока не будет достигнут граничный размер списка по отношению к размеру вектора - условие изменения размера вектора. Файл Test2.cpp продолжает знакомство с членами класса и посвящён поддержке полиупорядочиваемости. PoliSearcher же! Там всё достаточно логично. Есть класс данных с несколькими полями и заданы несколько предикат сравнения, использующие данные поля по разному. Создаётся объект PoliSearcher, хранящий множество объектов класса данных и несколько (ровно столько, сколько предикат) структур упорядоченных ссылок (итераторов) на элементы хранилища. Показано также, как производится поиск элементов и диапазонов элементов, в соответствии с разными критериями поиска (предикатами). Краткое описание класса: Неймспейс: namespace PoliSearchering класс PoliSearcher - структура хранения и поиска элементов заданного типа, по заданным предикатам сравнения больше/меньше Конструкторы: template<typename T, size_t chain_size> class PoliSearcher { PoliSearcher ( list<T> & storage_, const string &pred_description=less_default_pred_desc ription(), Pred predicate_ =less_default, int norma_=2 ); template<typename FwdIt> PoliSearcher ( const FwdIt bg_, const FwdIt en_, const string &pred_description=less_default_pred_desc ription(), Pred predicate_=less_default, int norma_=2 ); } параметры: T - тип элемента который хранится в PoliSearcher в качестве объекта для поиска; chain_size - максимальное значение длины цепочки элементов между её начальным элементом и начальным элементом следующей цепочки, - то есть объектами, копии которых, содержат два соседних элемента вектора поиска; storage_ - список объектов для построения структуры поиска PoliSearcher. Итераторы этого списка валидны всегда, вплоть от вставки целевого элемента и до его удаления. Поэтому, данные (но константные) итераторы являются объектами хранения в списке поиска search_list и векторе поиска bin_search_vec ; pred_description - строка описывающая предикат сравнения. Желательно чтобы она содержала информацию о поле/полях по которому/которым ведётся сравнение и о способе сравнения объектов PoliSearcher Формат данной строки - дело разработчика по умолчанию соответствует предикату predicate_ по умолчанию predicate_ указатель на предикат сравнения объектов. По умолчанию он соответствует вызову оператора < на типе Т Если такой опрератор не перегружен, то предикат должен быть передан явно. Pred это: typedef bool ( *Pred )(const T &rhs, const T& lhs); norma_ - целое, положительное целое число, показывающее во сколько раз (от деления нацело): стартовый размер нормализованной цепочки ch_sz=chain_size/norma меньше максимального размера chain_size; bg_, en_, - последовательные итераторы контейнера или массива, задающие последовательность элементов для хранения. члены: ////////////////////////////Iterator вложенный класс Iterator: template<Pred predicate> class Iterator; - шаблонный класс экземплярами которого осуществляется доступ к упорядоченным структурам класса PoliSearcher конструкторы: конструктор по умолчанию создаёт не инициализированный итератор: Iterator(){}; конструктор копирования Iterator(const Iterator& rhs); члены: bool is_valid(); - проверка валидности полученного итератора int size(); - размер упорядоченной структуры по данному предикату (размеры всех структур совпадают с размером хранилища) Iterator operator[](int ind); - доступ по индексу (не рекомендуется) Iterator& operator++(); Iterator operator++(int); Iterator& operator--(); Iterator operator--(int); Iterator &operator=(const Iterator rhs); bool operator == (const Iterator rhs); bool operator != (const Iterator rhs); ////////////////////////////////Iterator template <Pred pred> Iterator<pred> begin(); - начало структуры поиска, упорядоченной по предикату Pred pred template <Pred pred> Iterator<pred> end(); - итератор на адрес расположенный за последним валидным элементом структуры поиска, упорялоченной по предикату Pred pred template<Pred predicate> Iterator<predicate> find_search_list_iter_start(const T & val ); - метод возвращающий итератор на первый элемент который равен элементу val в соответствии с предикатом predicate: равенство определяется в соответствии с: (!predicate(elem, val) && !predicate(val, elem)) == (val == elem) template<Pred predicate> Iterator<predicate> find_search_list_iter_last(const T & val );- метод возвращающий итератор на последний элемент который равен элементу val в соответствии с предикатом predicate. Если ни один val не найден - указывает на конец структуры. Для итерации по диапазону может понадобиться получить следующий (++). Предварительно нужно проверить на валидность полученный итератор, так как после увеличения он уже может смотреть на конец (быть не валидным). Замечание: Пара перечисленных методов, вызванная на значениях val1 и val2 вернёт итераторы, ограничивающий диапазон val1 и val2 (включительно). Значения val1 и val2 должны следовать друг за другом в соответствии с предикатом predicate. Логично, что если оба метода вызваны на одном и том же значении val, то будут получены итераторы на диапазон, содержащий все элементы равные друг другу по предикату predicate template<Pred predicate> Iterator<predicate> find_search_list_iter_first_by_all_pred_ equal(const T & val ); - метод возвращающий итератор на первый элемент который равен элементу val в соответствии со всеми предикатами PoliSearcher template<Pred predicate> Iterator<predicate> find_search_list_iter_first_by_copl_pred _equal(const std::vector<Pred> &vpred, const T & val ); - метод возвращающий итератор на первый элемент который равен элементу val в соответствии со всеми предикатами переданными в векторе vpred. Предполагается что все из переданных присутствуют в PoliSearcher. Если некоторые предикаты отсутствуют в PoliSearcher они будут проигнорированы. Если нет ни одного присутствующего в PoliSearcher будет возвращён итератор за конец структуры Polisearch по предикату predicate, то есть, - Iterator<predicate>end(). Замечание. При необходимости поиска диапазонов для всех или части предикат необходимо создать сложные предикаты и создать соответствующую структуру, а после этого использовать первые 2 метода поиска. void add_new_listed(Pred predicate_, std::string pred_description_); - метод добавляющий новую упорядоченную структуру указывающую на хранилище элементов PoliSearcher. predicate_ и pred_description_ - соответственно, новый предикат сравнения и его описание. Если передан предикат уже имеющийся в PoliSearcher то ничего сделано не будет. Предикаты это указатели и значит два метода которые делают, логически, одно и тоже, но определённые как самостоятельные функции, считаются различными. При передаче таких методов будут создаваться идентичные упорядоченные структуры, что не имеет никакого смысла. void remove_listed(Pred predicate); - метод удаляющий упорядоченную структуру построенную по predicate. Если таковая не найдена, ничего не будет слелано. void add(const T & val); - метод добавляющий элемент в PoliSearcher (то есть, во все его упорядоченные структуры) void erase_it(const T & val, Pred predicate_ ); - метод удаляющий элемент из PoliSearcher (то есть, из всех его упорядоченных структур). void show_search_list(Pred predicate_=less_default, const std::string &str="" ); - метод вывода структуры поиска по её предикату. void show(Pred predicate_=less_default, const std::string &str=""); - метод демонстрации и отладки. Отображает структуру так называемого класса «Listed», созданный предикатом «предикат». Этот метод предоставляет: - содержимое вектора поиска, -упорядоченного списка с выделенными элементами вектора, для демонстрации распределения элементов по цепочкам, -списка поиска в виде аналогичном результату работы show_search_list. Оба предыдущих метода, - легкий путь. В тестах показано, как имея итераторы диапазонов можно выводить содержимое. То есть, это вопрос необходимости и воображения пользователя. Исходный код PoliSearcher.h во вложении.  p.s. от 29.09.21 к предыдущей строчке: "Исходный код PoliSearcher.h во вложении. "По неизвестной причине код во вложении arh.zip сломан. Пару пустяков починить для любого "хакера", но я положу починенную версию рядом. Не хочу замещать старую, так как 200+ скачивании звучит гордо, а замена обнулит счётчик. Однако, вот что меня удивляет. Почему ни кто из тех кто скачивал уже сломанную версию не пожаловался на то, что код не компилируется? Что ж... Ладно) Посмотрим сколько проживёт новый (старый) вариант) Итак - качайте version 1.01.zip ________________________________________ ________________________________________ _________________________ Картинки к описанию заполнения и работы алгоритма перевыделения памяти для вектора: |
Метки algo
Размещено в Без категории
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Всего комментариев 0
Комментарии
