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

Ответ 1

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

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

Ответ 2

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

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

Во-первых, очереди приоритетов не обязательно 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, у вас есть только один вариант. Приоритетные очереди используют строгий слабый порядок, поэтому они бесполезны здесь, но алгоритм "stable_sort" в библиотеке алгоритмов STL выполнит свою работу.

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

Ответ 3

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

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

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

Итак, проанализируйте свои данные!

Ответ 4

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

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

Ответ 5

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

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

Ответ 6

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

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

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

Ответ 7

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

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

Ответ 8

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

Ответ 9

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