Что быстрее: вставка в очередь приоритетов или сортировка ретроспективно?
Я создаю некоторые элементы, которые мне нужно отсортировать в конце. Мне было интересно, что быстрее с точки зрения сложности: вставка их непосредственно в priority_queue или аналогичная структура данных или с использованием алгоритма сортировки в конце?
Вставка n элементов в очередь приоритета будет иметь асимптотическую сложность O (n log n), поэтому с точки зрения сложности она не будет более эффективной, чем использование sort один раз, в конце.
На самом деле это зависит от его эффективности. Тебе нужно протестировать. Фактически, на практике даже продолжительная вставка в линейный массив (как при сортировке вставки, без создания кучи) может быть наиболее эффективной, хотя асимптотически она имеет худшее время исполнения.
Это, вероятно, доходит до вас немного поздно в игре, насколько ваш вопрос, но пусть будет полным.
Тестирование - лучший способ ответить на этот вопрос для конкретной компьютерной архитектуры, компилятора и реализации. Кроме того, существуют обобщения.
Во-первых, очереди приоритетов не обязательно O (n log n).
Если у вас есть целочисленные данные, есть очереди приоритетов, которые работают в O (1) раз. Публикация Beucher and Meyer 1992 "Морфологический подход к сегментации: преобразование водоразделов" описывает иерархические очереди, которые довольно быстро работают для целочисленных значений с ограниченным диапазоном. Brown 1988 публикация "Календарные очереди: быстрая реализация очереди 0 (1) для задачи набора симуляции" предлагает еще одно решение, которое отлично справляется с более широкими диапазонами целых чисел - два десятилетия работы после публикации в Brown опубликовало несколько приятных результатов для выполнения целого числа очереди приоритетов. Но механизм этих очередей может усложниться: сортировка ведра и сортировка по методу рад может по-прежнему обеспечивать работу O (1). В некоторых случаях вы даже можете квантовать данные с плавающей запятой, чтобы воспользоваться очередью приоритетов O (1).
Даже в общем случае данных с плавающей запятой O (n log n) мало вводит в заблуждение. Книга Edelkamp "Эвристический поиск: теория и приложения" имеет следующую удобную таблицу, показывающую сложность времени для различных алгоритмов очереди приоритетов (помните, приоритетные очереди эквивалентны сортировке и управлению кучей):
Как вы можете видеть, во многих очередях приоритетов O (log n) стоит не только для вставки, но также для извлечения и даже управления очередью! Хотя коэффициент обычно снижается для измерения временной сложности алгоритма, эти затраты все еще стоит знать.
Но у всех этих очередей все еще есть сложности времени, которые сопоставимы. Что лучше? В документе 2010 года Cris L. Luengo Hendriks, озаглавленном "Пересмотр очередей приоритетов для анализа изображений", рассматривается этот вопрос.
В тесте удержания Хендрикса приоритетная очередь была засеяна N случайными числами в диапазоне [0,50]. Самый верхний элемент очереди был затем удален, увеличен на случайное значение в диапазоне [0,2], а затем поставлен в очередь. Эта операция повторялась 10 ^ 7 раз. Накладные расходы на создание случайных чисел были вычтены из измеренных времен. Тесты лестницы и иерархические кучи выполнялись достаточно хорошо.
Время элемента для инициализации и опорожнения очередей также было измерено --- эти тесты очень важны для вашего вопроса.
Как вы можете видеть, в разных очередях часто возникали очень разные ответы на очереди и деактивацию. Эти цифры подразумевают, что, хотя могут существовать алгоритмы приоритетной очереди, которые являются превосходными для непрерывной работы, нет лучшего выбора алгоритма для простого заполнения, а затем для опорожнения очереди приоритетов (операция, которую вы выполняете).
Оглянитесь на свои вопросы:
Что быстрее: вставка в очередь приоритетов или сортировка ретроспективно?
Как показано выше, приоритетные очереди могут быть эффективными, но по-прежнему существуют затраты на вставку, удаление и управление. Вставка в вектор выполняется быстро. Это O (1) в амортизированном времени, и нет никаких затрат на управление, плюс вектор O (n) для чтения.
Сортировка вектора будет стоить вам O (n log n), если у вас есть данные с плавающей запятой, но на этот раз сложность не скрывала такие вещи, как очереди приоритетов. (Тем не менее, вы должны быть немного осторожны. Quicksort очень хорошо работает с некоторыми данными, но имеет худшую временную сложность O (n ^ 2). Для некоторых реализаций это серьезный риск для безопасности.)
Я боюсь, что у меня нет данных о стоимости сортировки, но я бы сказал, что ретроактивная сортировка отражает суть того, что вы пытаетесь сделать лучше, и поэтому лучший выбор. Исходя из относительной сложности управления очередью приоритетов и пост-сортировки, я бы сказал, что пост-сортировка должна быть быстрее. Но опять же, вы должны проверить это.
Я создаю некоторые элементы, которые мне нужно отсортировать в конце. Мне было интересно, что быстрее с точки зрения сложности: вставка их непосредственно в очередь приоритетов или аналогичную структуру данных или с помощью алгоритма сортировки в конце?
Мы, вероятно, рассмотрели это выше.
Тем не менее, другой вопрос вы не задавали. И, возможно, вы уже знаете ответ. Это вопрос стабильности. С++ STL говорит, что очередь приоритетов должна поддерживать "строгий слабый" порядок. Это означает, что элементы равного приоритета несравнимы и могут быть размещены в любом порядке, а не в "общем порядке", где каждый элемент сопоставим. (Здесь есть приятное описание порядка здесь.) При сортировке "строгий слабый" аналогичен неустойчивой сортировке, а "полный порядок" аналогичен стабильный вид.Результат состоит в том, что если элементы одного и того же приоритета должны оставаться в том же порядке, что и вы вставляете их в свою структуру данных, вам нужен стабильный вид или общий порядок. Если вы планируете использовать С++ STL, у вас есть только один вариант. Приоритетные очереди используют строгий слабый порядок, поэтому они бесполезны здесь, но алгоритм "stable_sort" в библиотеке алгоритмов STL выполнит свою работу.
Надеюсь, это поможет. Дайте мне знать, если вы хотите получить копию любой из упомянутых статей или хотите получить разъяснения.: -)
Зависит от данных, но обычно я вставляю InsertSort быстрее.
У меня был связанный с ним вопрос, и я обнаружил, что в конечном итоге узким местом было то, что я делал дефферированную сортировку (только когда мне это было нужно) и на большом количестве предметов я обычно был в худшем случае -scenario для моего QuickSort (уже по порядку), Итак, я использовал сортировку вставки
Сортировка 1000-2000 элементов со многими промахами кеша
Итак, проанализируйте свои данные!
К вашему первому вопросу (который быстрее): это зависит. Просто проверьте это. Предполагая, что вы хотите получить конечный результат в векторе, альтернативы могут выглядеть примерно так:
#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)) и полагая, что под "сортировкой" вы подразумеваете сортировку. Другие виды сортировки могут иметь более низкую сложность.
Насколько я понимаю, ваша проблема не требует Priority Queue, так как ваши задачи звучат так: "Сделайте много вставок, после этого сортируйте все". Это как стрельба птиц с лазера, а не подходящий инструмент. Для этого используйте стандартные методы сортировки.
Вам понадобится очередь приоритетов, если ваша задача должна имитировать последовательность операций, где каждая операция может быть либо "Добавить элемент в набор", либо "Удалить наименьший/наибольший элемент из набора". Это может быть использовано, например, при поиске кратчайшего пути на графике. Здесь вы не можете просто использовать стандартные методы сортировки.
Я думаю, что вставка более эффективна почти во всех случаях, когда вы генерируете данные (т.е. не имеете ее в списке).
Приоритетная очередь не является вашим единственным вариантом для вставки при прохождении. Как упоминалось в других ответах, бинарное дерево (или связанное с ним дерево RB) одинаково эффективно.
Я бы также посмотрел, как реализована очередь приоритетов - многие из них основаны на b-деревьях, но несколько реализаций не очень хороши в извлечении элементов (они, по сути, проходят всю очередь и ищут наивысший приоритет).
Очередь приоритетов обычно реализуется как куча. Сортировка с использованием кучи в среднем медленнее, чем quicksort, за исключением того, что quicksort имеет худшую производительность в худшем случае. Кроме того, кучи представляют собой относительно тяжелые структуры данных, поэтому на них больше накладных расходов.
Я бы посоветовал сортировать в конце.
Почему бы не использовать двоичное дерево поиска? Затем элементы сортируются во все времена, а затраты на вставку равны очереди приоритетов. Читайте о сбалансированных деревьях RedBlack здесь
В операциях очереди приоритетов max-insert есть O (lg n)