Написание O (1) высокопроизводительных структур данных - это серия из нескольких постов:

  1. Иерархическая очередь (эта статья)
  2. Иерархическая куча
  3. Ladder Queue (скоро)

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

Когда использовать очереди с приоритетом⁉

Признаюсь, я не использовал многие из них в своих приложениях, но есть несколько идеальных проблем:

  • сортировка - любая обработка, которая у вас есть на основе оценки / важности
  • упорядочение - когда ваши данные имеют определенный порядок обработки / анализа, например: обрабатывать DAU KPI перед MAU
  • Моделирование, управляемое событиями - приоритеты могут быть временными метками
  • Поиск по графику
  • Балансировка нагрузки - приоритет обратный нагрузке

Шаги малыша

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

2 нижних строчки вызвали мой интерес, они представляют собой многоструктурные приоритетные очереди O (1). Первый из них - это иерархическая куча, которая основана на иерархической очереди, так что давайте углубимся.

Иерархическая очередь

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

«Когда значения приоритета ограничены небольшими целыми числами (например, цифровые изображения часто имеют 8-битные или 12-битные целые числа в качестве значений пикселей, когда они выходят из датчика изображения), можно выделить очередь FIFO (ведро) для каждого возможного значение приоритета. Массив содержит указатель на каждую из этих корзин, и при постановке элемента в очередь правильная корзина может быть напрямую проиндексирована с использованием значения приоритета. И постановка, и удаление - это операции O (1) ».

Документы, использованные для алгоритма и фрагментов:

Это простая структура, очень быстрая, но у нее есть несколько ограничений.

  1. Он имеет только ограниченное количество значений приоритета (в моей реализации - uin8 (0–255)). Каждое значение имеет свою очередь, поэтому увеличение числа приводит к дополнительным расходам памяти.

2. Как только очередь с наивысшим приоритетом опустеет, она удаляется, и следующая очередь может начать опустошаться, и ее нельзя создать снова. Это означает, что мы должны заполнить очереди, прежде чем мы начнем исключать из очереди, в противном случае наша производительность снизится, пример: у процесса удаления из очереди остался только 1 приоритет (255), и мы ставим в очередь другие элементы. Все новые элементы будут помещены в очередь 255 (поскольку 0–254 пусты и удалены).

Go code go

Приоритетами могут быть uint8 и значения interface{}.

Я решил снять 2-е ограничение. Я думаю, что это сделало структуру слишком жесткой для большинства реальных сценариев . Мне удалось сохранить примерно такую ​​же производительность (≤ 50 нс на операцию). Я кэшировал наивысший приоритет, у которого есть значения, и начинаю удалять их из очереди. В некоторых случаях процесс Dequeue может быть O (1 + k), где K количество пустых очередей, но в целом амортизируется, если приоритеты хорошо сбалансированы.

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

На первой итерации я использовал связанные списки в качестве очередей (использовал golang list.List), а среднее время работы составляло 150–200 нс. В итоге я использовал более быструю структуру (благодаря предложению Эгона Эльбре): github.com/karalabe/cookiejar/ collection / deque . Это сократило время работы до менее 50 нс (черт возьми, это довольно быстрый список).

Поскольку в Go важен параллелизм, в структуре есть мьютекс. Его можно использовать вручную или автоматически (каждый вызов функции блокирует мьютекс).

Чтобы быть максимально универсальным, очереди могут хранить любой тип данных interface {}.

Упаковки

Иерархическая структура очереди является частью пакета priorityqueue, она имеет 100% тестовое покрытие, примеры, тесты и документацию.



bgadrian / data-structure
data-structure - Абстрактные структуры данных Пакеты Go, созданные с учетом производительности и параллелизма для изучения Go. github.com



Следующий

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



Очереди с быстрым приоритетом в Golang: иерархическая куча
Иерархическая куча - очень эффективная приоритетная очередь O (журнал n / k) для больших наборов данных. coder.today



Вклад

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

Спасибо! 🤝

Пожалуйста (хлопайте в ладоши) 👏🏻 и подпишитесь, если вы узнали что-то новое. Отправьте мне свой отзыв, и я смогу улучшить следующие сообщения.