Комментарии 6
Я не понял смысл происходящего. Либо у вас тут на самом деле завуалированная сортировка кучей (в коде встречается priority_queue и не встречается Merge), либо вы никак не доказали O(n log n) в худшем случае. И на самом деле там легко может быть O(n^2), как у QuickSort с фиксированным выбором медианы.
- Зачем вы вводите операцию
Merge, хотя в предоставленной реализации на C++ её нет и вместо неё используетсяpriority_queue— очередь с приоритетом, которая в стандартной библиотеке C++ реализована как обычная двоичная куча? - Если вы хотели использовать
priority_queueвместоMergeс самого начала, то зачем вообще вводить декартово дерево? Асимптотику это никак не улучшает — в худшем случае в очереди будет лежать O(n) элементов, получаем в точности сортировку кучей, но в которую зачем-то добавили O(n) лишней памяти. - Если вы всё-таки хотите использовать стандартный
Merge, который проходит по двум деревьям сверху вниз и склеивает их, то откуда вы взяли оценку в O(log n) на операцию в среднем и уж тем более в худшем варианте?
Это точно не декартово дерево в обычном смысле: для любых классических вариантов декартова дерева (в том числе по неявному ключу) требуется рандом (случайные величины). Обычно его ставят как раз в приоритеты (высоты) вершин, которые вы взяли из входных данных. У вас рандома нет вообще.
И именно из рандома во всех оценках берутся разумные слова "в среднем": в среднем по случайно сгенерированным приоритетам вершин, то есть в среднем по нескольким запускам программы на одних и тех же входных данных. Но у вас "в среднем" получается по входным данным. Примерно как детерминированный QuickSort — на случайных данных работает, на специально подогнанных — O(n^2).
Спасибо автору статьи за ссылку на (вероятно) исходный пост в комментарии ниже.
Там как раз автор не использует никакой Merge в объяснении времени работы и чётко говорит, что это именно оптимизация для сортировки кучей почти отсортированных массивов, а декартово дерево тут вообще побоку. И оценки на время работы к декартову дереву не относятся никак.
Там же автор ссылается на исходную статью Heapsort—Adapted for presorted files 1989 года, в которой этот алгоритм (улучшение сортировки кучей) изучают, придумывают метрику для оценки "отсортированности" массива (называют Osc) и показывают интересную границу времени работы через эту метрику. Это оказывается лучше, чем O(n log n), для некоторых отсортированных массивов. И заодно авторы доказывают, что по этой метрике быстрее сортировать невозможно.
Но из текущего поста это понять решительно невозможно.
Хаб "Совершенный код" тоже выглядит странновато. Реализация выглядит "по-олимпиадному" в плохом смысле этого слова. Кажется, что автор кода C++ знает плохо или зачем-то решил убрать все детали, но для этого лучше вообще на питоне писать.
- Полное отсутствие освобождения памяти. Использование чистых указателей и
new. На контестах окей, в любом долгоживущем коде не окей. Хоть быunique_ptrдля владения детьми добавили. CartesianTree(std::vector<int> ar)— передача по значению вместо константной ссылки. Лишнее копирование вектора целиком.NULLвместо принятого с C++11nullptr.- Присваивания в конструкторе вместо объявления поля
int value = 0(default member initializer) или хотя бы member initialization list в конструкторе (Node() : value(0) {}).
Для своих задач пользую активно. Класстческий SkipList с расширением в виде виртуального номера элемента (т.е. поиск можно проводить не только по ключу, но и по позиции элемента в списке), который фактически является вторым ключом — алгоритм поиска по нему аналогичен алгоритму поиска по ключу.
На базе этого алгоритма у меня созданы сортированный список (вместо пары ключ-данные есть только данные, которые одновременно являются ключом) и «набор» — список однотипных элементов.
Дополнительно реализовал такие методы как поиск по частичному (первые n байт) ключа, переход к следующему/предыдущему элементу, у которого первые n байт ключа совпадают/не совпадают с первыми n байт ключа текущего элемента.
Основная работа у нас с БД — использую для кеширования записей (в частности) чтобы лишний раз не дергать таблицу, по которой уже прошелся.
Иногда для сортировки использую. Была одна задачка, где нужно было получить выборку, отсортированную по набору полей. Причем, поля эти неиндексированы. Решение в лоб, с использованием ORDER BY в SQL запросе давало время порядка минуты-полторы на выполнение всей задачи (там выборки по 50-60 и более тысяч записей). Убрал ORDER BY из запроса, а результаты выборки занес в SkipList с ключом из комбинации этих самых полей. Время выполнения той же задачи на тех же данных сократилось до 10-15 секунд
Поскольку это список, то обход от наименьшего элемента к наибольшему и наоборот там выполняется очень быстро — как в обычном двусвязном списке.
Вставка-удаление тоже в среднем быстрее чем для деревьем т.к. не требует периодической перебалансировки дерева.
Система IBM i (AS/400), 1 процессор IBM PowerS924, 18 ядер SMT8 (144 потока). 16Гб ОЗУ на задачу.
При заполнении списка засечки времени делались по последним 100 000 элементам.
При удалении — по первым 100 000 элементам.
Поиск — максимальное и среднее время считалось по 100 000 элементам
Сортировка декартовым деревом