Какая приоритетная очередь быстрее?

Question

[John Smith]

Какая из приоритетных очередей быстрее?
Выбираю из:

• Наивная реализация на основе сортированного двусвязного списка
  
• Простая куча
  
• Фибоначчиева куча
  
• Pairing heap
  
• Тонкая куча
  
• Толстая куча
  
• Скошенная биномиальная куча
  
• Очередь Бродала-Окасаки
  

Пытался найти сравнительные графики в Интернете, однако сколько не мучил Google, ответа так и не добился.
Планируемый характер нагрузки:

• Количество элементов в очереди: до 2^16-1 (< 65536).
  
• Размер узлов 64 байта, из них 16 байт полезной нагрузки и остальное для полей узла кучи.
  
• Планируемый язык реализации C/C++ или Ассемблер. Архитектура x86-64.
  
• Необходимые операции: FindMin, Insert, ExtractMin, Merge.
  
• Желательные операции (но не критично): DeleteNode.
  
• Наиболее частая операция: FindMin. Реже: Insert и ExtractMin. Редко: DeleteNode. Очень редко: Merge.
  

По найденным асимптотическим оценкам, наиболее привлекательными выглядят Тонкая куча, Скошенная биномиальная куча и Очередь Бродала-Окасаки. Однако как насчёт производительности на практике?

Comments

[Евгений Шатунов]

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

Answer 1

[mayton2019]

Господи как все сложно. Берешь и делаешь столько очередей - сколько надо приоритетов. И все.

Answer 2

[maaGames]

Я бы сделал на std::deque. Вставка в начало и вытаскивание из конца у него работает махом. Сортировка и доступ чуть медленнее, чем у std::vector, но быстрее всех остальных. Придётся сортировать после каждого добавления узла (если делать лениво, то перед доступом можно сортировать, но это от нагрузки зависит, проверка перед доступом может всю пользу ленивости съесть). Еси добавления не частые, то можно и на векторе сделать, объём же ничтожный.

Comments

[Евгений Шатунов]

std::deque не решает задач приоритетной очереди. Стандартная std::priority_queue, при этом, по умолчанию базируется на std::vector.

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

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

[maaGames]

Евгений Шатунов, Это потому что: Первое - я был не прав, Второе - я забыл про существование priority_queue. Не прав, потому что не подумал про сохранение порядка сортировки, а stable_sort уже делает ручную сортировку не такой производительной идеей.
но я на 99% уверен, что любое решение на основе deque (priority_queue или ручной вариант) будет самым быстрым, с учётом малого объёма данных и более частого попадания в кэш, чем при использовании деревьев (вставка-удаление заявлены редкими, поэтмоу временем на перестройку очереди можно пренебречь, независимо от её реализации).

[Евгений Шатунов]

но я на 99% уверен, что любое решение на основе deque (priority_queue или ручной вариант) будет самым быстрым, с учётом малого объёма данных и более частого попадания в кэш, чем при использовании деревьев

Твоя правда. Я, чес-говоря, пока тоже в этом уверен, пока автор не описал задачу, в решении которой должна участвовать очередь.