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

Question

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

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

Answer 1

Скорее всего, это немного поздно для вас в игре, но ваш вопрос будет завершен.

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

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

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

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

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

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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

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

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

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

Answer 5

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

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

Answer 6

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

Answer 7

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

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

Answer 8

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

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

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

Answer 9

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