Введение Здравствуйте, Хабравяне.
Это моя первая публикация, в которой я хочу поделиться структурой данных SMAS. В конце статьи будет предоставлен класс C++ предлагаемой структуры данных.
Реализация рекурсивная, но моя цель — передать идею.
Реализация нерекурсивной версии — дело второе.
Важно «слышать» мнения.
Что не так с деревом?
Да, всё, можно заканчивать статью, всем спасибо.Это была бы трата значительных накладных расходов памяти на вспомогательные данные в виде ссылок на левое-правое поддеревья и флага балансировки (разного в зависимости от используемой методики - красно-черные, AVL и т.п.
деревья).
Еще один, не такой уж и минус, — постоянная модификация дерева при вставке для балансировки (здесь особенно важна сложность и трудоемкость методов для новичков).
На этом недостатки заканчиваются и сложно представить что-то лучшее и универсальное (хеш-таблицы, ИМХО, еще круче, но ОХ МОИ СТОЛКНОВЕНИЯ).
Почему не отсортированные массивы?
Бинарный поиск в отсортированном массиве реализован с той же логарифмической сложностью, что и в бинарном дереве поиска, но нет необходимости вытаскивать ссылки на меньшие-большие поддеревья, как в бинарном дереве поиска.Но что не так с отсортированными массивами? Да, все верно, мы можем закончить статью и использовать отсортированные массивы вместо бинарных деревьев поиска и наслаждаться сэкономленными ресурсами, если только нам не нужно добавлять или удалять элементы из такого массива, потому что если мы добавим новые элементы (удалим старые), тогда массив скажет: «сломи меня, пересортируй меня» полностью».
Но беда сортировки в том, что она медленная, если нужно вставить новый элемент где-то между остальными, особенно в начале.
Но есть и идеальный случай — когда новый элемент больше остальных и его достаточно просто добавить в конец.
Это идеально — всего одна операция, но вероятностная оценка такого идеального случая заставляет нас использовать бинарные деревья или хэш-таблицы, или огромное множество других действительно красивых и умных механизмов.
С точки зрения теории вероятностей, такая ситуация встречается редко — только если все элементы добавляются в массив в порядке возрастания (ироничная аналогия с двоичным деревом поиска, когда отсортированные входные данные — это как раз худший случай, когда дерево вырождается в связанный список с линейная сложность).
Частный случай или закономерность?
Но давайте рассмотрим массив, состоящий всего из одного элемента.Неважно, какое значение введено — оно всегда укладывается в начало ранее пустого массива и одноэлементный массив, естественно, всегда сортируется.
Что, если мы хотим вписать второй элемент в нашу структуру данных? Давайте просто создадим еще один одноэлементный массив и получим два отсортированных одноэлементных массива.
Получить новый отсортированный массив из двух отсортированных — задача простая, хотя и не очень быстрая.
Но в этом случае нам уже нужно сортировать массив не при каждой вставке, а при каждой второй вставке.
Мы используем «отложенную сортировку».
Что делать, если мы хотим добавить более двух элементов? Захотеть не помешает - напишем где-нибудь новый 2-х элементный массив и продолжим добавлять элементы в одноэлементные массивы, а также на 4-м элементе у нас будет 2 2-х элементных отсортированных массива, которые мы сможем объединить таким же образом в один 4-х элемент и так до тех пор, пока не выскочит синий экран смерти и процессор не взорвется с сопутствующим образованием черной дыры, втягивающей в себя все окружающее пространство-время (что-то меня унесло.
) пока наша память это позволяет.
Распределение нагрузки
Понятно, что этот алгоритм уже значительно сокращает количество сортировок относительно сортировки обычного массива, поскольку первый уровень массивов нужно сортировать через раз, 2-й уровень - каждую 4-ю вставку, 3-й уровень - каждую 8-ю вставку - по сути, это логарифмическая сложность.На этом можно было бы успокоиться, но для слабаков попробуем распределить нагрузку равномерно при каждой вставке, дополняя нашу «отложенную сортировку» пошаговым подходом и выполняя каждый шаг при вставке очередного элемента для всех уровней — это позволит нам равномерно распределить нагрузку по всем вставкам — что и требуется.
Поиск
Поиск представляет собой классический бинарный поиск по отсортированному массиву, с той лишь разницей, что массивов много и перебирать их нужно поочередно.Поэтому логарифмическая сложность поиска оспаривается (если не ошибаюсь, это двойная логарифмическая сложность).
Но для поставленной задачи это вполне приемлемо, учитывая сэкономленную память.
Выполнение
Пока чайник кипел, я вспомнил, что еще хочу писать, но тут чайник закипел, и его свист заставил меня забыть, что я еще хотел написать.Реализация была довольно запутанной, потому что в голове было лишь поверхностное представление о том, как будет ездить вся эта машина - код был написан практически наугад, так что пойду спать с горем, заодно Программная структура класса алгоритма содержит всего 3 метода (не считая конструктора и деструктора).
В коде нет ничего, кроме работы с массивами, циклами и идеологией ООП — все безумно просто и, надеюсь, понятно.
Фактический код
Теги: #SMAS #структуры данных #упорядоченные массивы #двоичный поиск #Алгоритмы#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <windows.h> #define
-
Планшет С Мультитачем.
19 Oct, 24 -
Bbc Запускает Видеосервис Iplayer
19 Oct, 24 -
Server Core R2 Для Веб-Разработки
19 Oct, 24
