@Goblin-Shaman
Вечно начинающий программист

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

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

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

По найденным асимптотическим оценкам, наиболее привлекательными выглядят Тонкая куча, Скошенная биномиальная куча и Очередь Бродала-Окасаки. Однако как насчёт производительности на практике?
  • Вопрос задан
  • 286 просмотров
Пригласить эксперта
Ответы на вопрос 3
@bacon
Так всё просто, берёте практические реализации, пишите тесты которые отражают ваш "планируемый характер нагрузки" и делаете замеры.
Ответ написан
@mayton2019
Ent. Software engineer.
Господи как все сложно. Берешь и делаешь столько очередей - сколько надо приоритетов. И все.
Ответ написан
maaGames
@maaGames
Погроммирую программы
Я бы сделал на std::deque. Вставка в начало и вытаскивание из конца у него работает махом. Сортировка и доступ чуть медленнее, чем у std::vector, но быстрее всех остальных. Придётся сортировать после каждого добавления узла (если делать лениво, то перед доступом можно сортировать, но это от нагрузки зависит, проверка перед доступом может всю пользу ленивости съесть). Еси добавления не частые, то можно и на векторе сделать, объём же ничтожный.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы