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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1118 Но все эти очереди все еще имеют временные сложности, которые сопоставимы. Какой лучше? В документе Cris L. Luengo Hendriks 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 выполнит свою работу.

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

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

#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)), и предполагается, что под «сортировкой» подразумевается сортировка сравнения. Другие виды сортировки могут иметь меньшую сложность.

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

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

В очереди с максимальным приоритетом операций вставки O (lg n)