Что быстрее: вставка в приоритетную очередь или ретроспективная сортировка?

Вставка n элементов в приоритетную очередь будет иметь асимптотическую сложность O(n log n), поэтому с точки зрения сложности это не более эффективно, чем использование sort один раз, в конце.

Действительно ли это более эффективно на практике, зависит. Вам нужно проверить. Фактически, на практике даже продолжение вставки в линейный массив (как при сортировке вставками без создания кучи) может быть наиболее эффективным, хотя асимптотически оно хуже время выполнения.

Это, вероятно, приходит к вам немного позже в игре, что касается вашего вопроса, но давайте закончим.

Тестирование — лучший способ ответить на этот вопрос для конкретной компьютерной архитектуры, компилятора и реализации. Кроме того, есть обобщения.

Во-первых, приоритетные очереди не обязательно равны O(n log n).

Если у вас есть целочисленные данные, есть приоритетные очереди, которые работают за время O (1). Публикация Бойхера и Мейера 1992 года «Морфологический подход к сегментации: преобразование водораздела» описывает иерархические очереди, которые работают довольно быстро для целочисленных значений с ограниченным диапазоном. Публикация Брауна 1988 года «Очереди календаря: быстрая реализация очереди с приоритетом 0 (1) для задачи набора событий симуляции» предлагает другое решение, которое хорошо работает с большими диапазонами целых чисел — два десятилетия работы после публикации Брауна дали некоторые хорошие результаты для решения целочисленных задач. очереди с приоритетом быстро. Но механизм этих очередей может усложниться: сортировка ведрами и сортировка по основанию могут по-прежнему обеспечивать операцию O(1). В некоторых случаях вы можете даже квантовать данные с плавающей запятой, чтобы воспользоваться преимуществами очереди с приоритетом O(1).

Даже в общем случае данных с плавающей запятой значение O(n log n) немного вводит в заблуждение. В книге Эделькампа «Эвристический поиск: теория и приложения» есть следующая удобная таблица, показывающая временную сложность для различных алгоритмов очереди с приоритетом (помните, очереди с приоритетом эквивалентны сортировке и управлению кучей):

Как видите, многие очереди с приоритетом требуют затрат O(log n) не только на вставку, но и на извлечение и даже на управление очередью! Хотя коэффициент обычно не используется для измерения временной сложности алгоритма, эти затраты все же стоит знать.

Но все эти очереди по-прежнему имеют сравнимую временную сложность. Что лучше? Этот вопрос рассматривается в статье Криса Л. Луенго Хендрикса 2010 года, озаглавленной «Пересмотр приоритетных очередей для анализа изображений».

В ходе теста Хендрикса приоритетная очередь была заполнена N случайными числами в диапазоне [0,50]. Затем самый верхний элемент очереди удалялся из очереди, увеличивался на случайное значение в диапазоне [0,2], а затем помещался в очередь. Эта операция повторялась 10^7 раз. Накладные расходы на генерацию случайных чисел вычитались из измеренного времени. Лестничные очереди и иерархические кучи показали себя в этом тесте достаточно хорошо.

Также было измерено время инициализации и очистки очередей для каждого элемента --- эти тесты очень важны для вашего вопроса.

Как видите, разные очереди часто по-разному реагировали на постановку в очередь и удаление из очереди. Эти цифры подразумевают, что, хотя могут существовать алгоритмы очереди с приоритетом, которые лучше подходят для непрерывной работы, нет лучшего выбора алгоритма для простого заполнения, а затем опустошения очереди с приоритетом (операции, которую вы выполняете).

Давайте вернемся к вашим вопросам:

Что быстрее: вставка в приоритетную очередь или ретроспективная сортировка?

Как показано выше, очереди с приоритетами можно сделать эффективными, но затраты на их вставку, удаление и управление все же остаются. Вставка в вектор выполняется быстро. Это O (1) в амортизированном времени, и нет никаких затрат на управление, плюс вектор O (n), который нужно прочитать.

Сортировка вектора будет стоить вам O(n log n) при условии, что у вас есть данные с плавающей запятой, но на этот раз сложность не скрывает такие вещи, как очереди с приоритетами. (Тем не менее, вы должны быть немного осторожны. Быстрая сортировка очень хорошо работает с некоторыми данными, но в худшем случае она имеет временную сложность O (n ^ 2). Для некоторых реализаций это серьезная угроза безопасности.)

Боюсь, у меня нет данных о затратах на сортировку, но я бы сказал, что ретроактивная сортировка отражает суть того, что вы пытаетесь сделать лучше, и поэтому является лучшим выбором. Основываясь на относительной сложности управления приоритетной очередью по сравнению с пост-сортировкой, я бы сказал, что пост-сортировка должна быть быстрее. Но опять же, вы должны проверить это.

Я создаю некоторые элементы, которые мне нужно отсортировать в конце. Мне было интересно, что быстрее с точки зрения сложности: вставлять их прямо в приоритетную очередь или аналогичную структуру данных или использовать алгоритм сортировки в конце?

Мы, вероятно, рассмотрели это выше.

Однако есть еще один вопрос, который вы не задали. И, возможно, вы уже знаете ответ. Это вопрос стабильности. C++ STL говорит, что приоритетная очередь должна поддерживать "строгий слабый" порядок. Это означает, что элементы с одинаковым приоритетом несравнимы и могут располагаться в любом порядке, в отличие от «общего порядка», когда каждый элемент сопоставим. (Есть хорошее описание упорядочения здесь.) , «строгий слабый» аналогичен нестабильной сортировке, а «полный порядок» аналогичен стабильной сортировке.

В результате, если элементы с одинаковым приоритетом должны оставаться в том же порядке, в котором вы их вставили в свою структуру данных, вам нужна стабильная сортировка или общий порядок. Если вы планируете использовать C++ STL, у вас есть только один вариант. Очереди с приоритетами используют строгий слабый порядок, поэтому здесь они бесполезны, но алгоритм «stable_sort» в библиотеке алгоритмов STL выполнит свою работу.

Надеюсь, это поможет. Дайте мне знать, если вам нужна копия любого из упомянутых документов или вы хотели бы получить разъяснения. :-)

На ваш первый вопрос (который быстрее): это зависит. Просто проверьте это. Предполагая, что вы хотите получить окончательный результат в виде вектора, альтернативы могут выглядеть примерно так:

#include <iostream>
#include <vector>
#include <queue>
#include <cstdlib>
#include <functional>
#include <algorithm>
#include <iterator>

#ifndef NUM
    #define NUM 10
#endif

int main() {
    std::srand(1038749);
    std::vector<int> res;

    #ifdef USE_VECTOR
        for (int i = 0; i < NUM; ++i) {
            res.push_back(std::rand());
        }
        std::sort(res.begin(), res.end(), std::greater<int>());
    #else
        std::priority_queue<int> q;
        for (int i = 0; i < NUM; ++i) {
            q.push(std::rand());
        }
        res.resize(q.size());
        for (int i = 0; i < NUM; ++i) {
            res[i] = q.top();
            q.pop();
        }
    #endif
    #if NUM <= 10
        std::copy(res.begin(), res.end(), std::ostream_iterator<int>(std::cout,"\n"));
    #endif
}

$ g++     sortspeed.cpp   -o sortspeed -DNUM=10000000 && time ./sortspeed

real    0m20.719s
user    0m20.561s
sys     0m0.077s

$ g++     sortspeed.cpp   -o sortspeed -DUSE_VECTOR -DNUM=10000000 && time ./sortspeed

real    0m5.828s
user    0m5.733s
sys     0m0.108s

Итак, std::sort лучше std::priority_queue, в данном случае. Но, может быть, у вас лучше или хуже std:sort, а может быть, у вас лучше или хуже реализация кучи. Или, если не лучше или хуже, просто более или менее подходит для вашего точного использования, которое отличается от моего придуманного использования: «создать отсортированный вектор, содержащий значения».

Я могу с большой уверенностью сказать, что случайные данные не попадут в худший случай std::sort, поэтому в некотором смысле этот тест может польстить ему. Но для хорошей реализации std::sort его наихудший случай будет очень сложно сконструировать, и, возможно, на самом деле все не так уж и плохо.

Изменить: я добавил использование мультимножества, так как некоторые люди предложили дерево:

    #elif defined(USE_SET)
        std::multiset<int,std::greater<int> > s;
        for (int i = 0; i < NUM; ++i) {
            s.insert(std::rand());
        }
        res.resize(s.size());
        int j = 0;
        for (std::multiset<int>::iterator i = s.begin(); i != s.end(); ++i, ++j) {
            res[j] = *i;
        }
    #else

$ g++     sortspeed.cpp   -o sortspeed -DUSE_SET -DNUM=10000000 && time ./sortspeed

real    0m26.656s
user    0m26.530s
sys     0m0.062s

На ваш второй вопрос (сложность): все они O (n log n), игнорируя неудобные детали реализации, такие как выделение памяти O (1) или нет (vector::push_back и другие формы вставки в конце амортизируются O (1) ) и предполагая, что под «сортировкой» вы подразумеваете сортировку сравнением. Другие виды сортировки могут иметь меньшую сложность.

Зависит от данных, но обычно InsertSort работает быстрее.

У меня был связанный с этим вопрос, и в конце концов я обнаружил, что узким местом было то, что я выполнял отложенную сортировку (только когда мне это нужно) и для большого количества элементов у меня обычно был наихудший сценарий для мой QuickSort (уже в порядке), Поэтому я использовал сортировку вставками

Сортировка 1000-2000 элементов с большим количеством промахов кеша

Так что анализируйте свои данные!

Насколько я понимаю, ваша задача не требует Priority Queue, так как ваши задачи звучат как "Сделайте много вставок, после этого разберите все". Это как стрелять по птицам из лазера, а не подходящего инструмента. Используйте для этого стандартные методы сортировки.

Вам понадобится приоритетная очередь, если ваша задача состоит в том, чтобы имитировать последовательность операций, где каждая операция может быть либо «Добавить элемент в набор», либо «Удалить наименьший/наибольший элемент из набора». Это можно использовать, например, в задаче поиска кратчайшего пути на графе. Здесь вы не можете просто использовать стандартные методы сортировки.

Очередь с приоритетом обычно реализуется в виде кучи. Сортировка с использованием кучи в среднем медленнее, чем быстрая сортировка, за исключением того, что быстрая сортировка имеет худшую производительность в худшем случае. Кроме того, кучи являются относительно тяжелыми структурами данных, поэтому возникает больше накладных расходов.

Я бы рекомендовал сортировать в конце.

Почему бы не использовать бинарное дерево поиска? Тогда элементы сортируются постоянно, а затраты на вставку равны приоритетной очереди. Подробнее о сбалансированных деревьях RedBlack читайте здесь

Я думаю, что вставка более эффективна почти во всех случаях, когда вы генерируете данные (т.е. еще не имеете их в списке).

Очередь с приоритетом — не единственный вариант для вставки по ходу дела. Как упоминалось в других ответах, двоичное дерево (или связанное с ним RB-дерево) одинаково эффективно.

Я бы также проверил, как реализована очередь с приоритетами — многие из них уже основаны на b-деревьях, но некоторые реализации не очень хорошо извлекают элементы (по сути, они проходят через всю очередь и ищут наивысший приоритет).

В очереди с приоритетом max-insert операции O(lg n)

На этот вопрос есть много отличных ответов. Разумное эмпирическое правило

• Если у вас есть все элементы заранее, выберите сортировку.
• Если вы будете добавлять элементы/удалять минимальные элементы на лету, используйте приоритетную очередь (например, кучу).

В первом случае наилучшей сортировкой в ​​наихудшем случае будет сортировка кучей, и вы часто сможете повысить производительность кэша, просто сосредоточившись на сортировке (т. е. вместо чередования с другими операциями).