Множественные вставки и удаления в priority_queue

Проблема

В моем алгоритме я должен реализовать «Упорядоченную очередь» (я выбираю это имя, чтобы отличить мою идею от существующих реализаций). Мне нужно вставить некоторые значения в очередь, где значение представляет порядок в очереди, а затем я должен переварить очередь в соответствии с порядком. У меня есть ощущение, что лучшая структура данных для того, что мне нужно сделать, это std::priority_queue, но у меня есть некоторые опасения по поводу эффективности моей программы, в частности, из-за:

  • Интерфейс, который не предоставляет методы для вставки/удаления нескольких элементов
  • (Возможно) Внутренний дизайн класса и его алгоритмы

Из документации , как priority_queue::push, так и priority_queue::pop внутренне вызывают std::push_heap и std::pop_heap, которые имеют сложность O(log(N)). Я думаю, что очень неэффективно вставлять/удалять один элемент за раз, прибегая к базовому контейнеру при каждом вызове.

Почему это реализовано именно так? Может быть, когда вы вызываете std::push_heap и std::pop_heap в последовательности, базовая структура кучи находится в оптимальном случае, а сложность уменьшается относительно O (log (N))?

В противном случае, есть ли лучшая структура данных, которая соответствует моим потребностям, которую я не рассматривал? Я также думал, что std::forward_list может удовлетворить мои потребности при удалении (через forward_list::pop_front), но я боюсь, что вставка станет слишком дорогой, так как мне нужно найти итератор для правильного места для вставки, которое должно быть O (N).

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

Выполнение

Программа эквивалентна:

struct MyType{
    double when;
    int who;
    MyType(double t, double i) : when(t), who(i) {};
    bool operator<(const MyType & other) const{ return when < other.when; }
};

using OrderedQueue = priority_queue<MyType,std::vector<MyType>,std::less<MyType>>;

const double TMax = 1e9; // some BIG stopping condition

double some_time(){/*routine to generate the time*/ return TMax * rand(); }

int some_number(){/*routine to generate the number*/ return 100 * rand(); }

void populate(OrderedQueue & q){
    unsigned Ni = 10; // number of insertions: it is not fixed in the real program
    for (auto i = 0; i < Ni; ++i){
        q.emplace(some_time(), some_number());
    }
}

void use_MyType(MyType m){/*routine that uses the top value*/ return; }

void remove(double t, OrderedQueue & q){
    while(q.top().when < t){
        use_MyType(q.top());
        q.pop();
    }
}

int main(){
    double t = 0;
    OrderedQueue q;
    while(t < TMax){
        populate(q);
        remove(t, q);
        t += 1;
    }
}

Меня особенно интересует эффективность populate() и remove(), потому что цикл при их вызове имеет очень много итераций.

Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
2
0
66
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

std::priority_queue — это адаптер для структуры кучи. Учитывая ваши требования к потреблению элементов по порядку, куча является наиболее эффективной структурой.

Вставки кучи в худшем случае O (log (N)), но в среднем O (1). Это быстрее, чем, например. вставка двоичного дерева (std::map), которая всегда равна O (log (N)). Точно так же удаление верхнего элемента из кучи в худшем случае O (log (N)), но в среднем намного быстрее, поскольку куча частично отсортирована.

С учетом сказанного нельзя пренебрегать эффектами прогнозирования ветвлений и кэширования на современных компьютерах. Лучший способ ответить на вопрос о производительности — сравнить ее с вашими фактическими данными и репрезентативным количеством элементов. Я бы предложил сравнить эти 3 структуры очередей:

  • std::priority_queue<MyType, std::vector<MyType>>
  • std::priority_queue<MyType, std::deque<MyType>>
  • std::map<MyType>

std::deque поскольку резервное хранилище может предложить улучшенную pop_front производительность за счет более медленного произвольного доступа. Так что это должно быть эталоном.

Я бы проигнорировал std::list (std::forward_list) на этом этапе - вставка в связанный список в нужном месте - это O (N), плюс связанный список не поддерживает кеширование, поэтому это определенно будет гораздо более медленное решение.

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


Чтобы решить ваши проблемы:

Интерфейс, который не предоставляет методы для вставки/удаления нескольких элементов

Вставка элемента в кучу включает в себя добавление элемента в конец и «восстановление» структуры кучи. Это то, что делает алгоритм std::push_heap. Вполне возможно реализовать алгоритм для вставки нескольких элементов таким образом и/или просто вызвать std::make_heap после добавления нескольких элементов для восстановления всей кучи.

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

Внутренний дизайн класса и его алгоритмы

std::priority_queue — это просто адаптер вокруг алгоритмов кучи. Это удобный класс, который обертывает последовательный контейнер и вызывает для него алгоритмы кучи. Вам не обязательно использовать его, вы можете использовать std::vector, std::push_heap и std::pop_heap с точно такими же результатами (хотя код может быть менее читаемым и более подверженным ошибкам).

Я очень ценю ваш полный ответ! В вопросе, который вы связали, было полезное понимание: новые вставки добавляются к листьям кучи, а затем просачиваются к корню. Я предполагаю, что это означает, что: (A) «ремонт», выполненный std::push_heap, намного дешевле, чем полностью новый make_heap (отсюда и отсутствие метода множественной вставки в интерфейсе) (B) если вставка с большей вероятностью быть элементов с низким приоритетом (что имеет место для меня), перколяция в куче должна быть ~ O (1). Я надеюсь, что эти соображения могут быть полезны другим с аналогичной проблемой.

dariobaron 12.02.2023 01:53

В то время как вставка кучи обычно очень близка к O(1), удаление обычно очень близко к O(log n). Причина в том, что при удалении узел удаляется с конечного уровня, добавляется в корень, а затем просеивается в правильное положение. Половина узлов в куче находится на уровне листа, и, учитывая, что узел пришел с уровня листа, весьма вероятно, что он вернется обратно на уровень листа, то есть для его получения потребовалось O(log n) свопов. .

Jim Mischel 14.02.2023 00:17

Другие вопросы по теме