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

Question

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

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

Answer 1

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

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

Answer 2

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

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

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

Answer 3

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

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

Answer 4

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

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

Sorting 1000-2000 elements with many cache misses

Так анализировать ваши данные!

Answer 5

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

Answer 6

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

#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, его худший случай будет очень сложно построить, и на самом деле это может быть не так уж плохо.

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

#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 (п § п), игнорируя неудобную реализацию такие данные, как распределение памяти O (1) или нет (vector::push_back и другие формы вставки в конце амортизируются O (1)) и предполагается, что под «сортировкой» вы имеете в виду сортировку. Другие виды сортировки могут иметь более низкую сложность.

Answer 7

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

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

Answer 8

В течение операции очередей приоритетов макс-вставки являются O (Л.Г. п)

Answer 9

Это, вероятно, приходит к вам немного поздно в игре, насколько ваш вопрос касается, но давайте быть полным.

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

Прежде всего очереди приоритетов необязательно должны быть O (n log n).

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

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

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

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

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

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

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

Давайте оглянемся на вопросы:

Что быстрее: вставив в приоритетной очереди, или сортировка задним числом?

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

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

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

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

Возможно, мы покрыли это выше.

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

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

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