Приоритетная очередь

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

Операции

Очереди с приоритетом нуждаются в операциях

  • вставить , для вставки элемента и
  • extractMin , для возврата и удаления элемента с наименьшим ключом (= наивысшим приоритетом)
  • isEmpty , чтобы проверить, пуста ли очередь,

служба поддержки.

Также есть операции, которые особенно важны для онлайн-алгоритмов :

  • удалить удалить элемент
  • reduceKey уменьшить значение ключа (= увеличить приоритет)

Другие часто используемые операции:

  • peek , вернуть элемент с наивысшим приоритетом без изменения очереди
  • слияние , слияние двух приоритетных очередей

реализация

Реализация приоритетных очередей может быть выполнена через деревья AVL . И insert, и extractMin могут быть выполнены за время O (log n). Другая возможность - использовать частично упорядоченные деревья ( кучи ). Здесь также временная сложность O (log n).

Примеры структур данных, которые эффективно реализуют очереди приоритетов:

В приведенной ниже таблице представлен обзор различных сред выполнения некоторых реализаций в O нотации .

операция заглядывать extractMin вставлять уменьшение слить
Двоичная куча Θ (1) Θ (журнал  n ) O (журнал  n ) O (журнал  n ) Θ ( п )
Левое дерево Θ (1) Θ (журнал n ) Θ (журнал n ) O (журнал n ) Θ (журнал n )
Биномиальная куча Θ (1) Θ (журнал n ) Θ (1) а Θ (журнал n ) O (журнал  n ) b
Куча Фибоначчи Θ (1) O (журнал  п ) а Θ (1) Θ (1) а Θ (1)
а амортизированный
б n - размер большей кучи

Приложения

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

Как правило, очереди с приоритетами необходимы для многих алгоритмов или даже классов алгоритмов.

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

Вы также можете использовать приоритетные очереди для лучших алгоритмов поиска . Очередь с приоритетами обычно используется для поиска следующего наиболее многообещающего узла за одну итерацию. Примером этого является алгоритм A * для вычисления кратчайших путей в графах.

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

Расширения

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

Очередь с параллельным приоритетом

Чтобы еще больше ускорить очереди с приоритетом, их можно распараллелить. Есть три разных варианта распараллеливания. Первая возможность - просто распараллелить отдельные операции ( insert , extractMin ...). Второй вариант позволяет нескольким процессам одновременно обращаться к приоритетной очереди. Последний вариант - выполнять каждую операцию с k элементами, а не только с одним элементом за раз. В случае extractMin, например, первые k элементов с наивысшим приоритетом будут удалены из очереди приоритетов.

Распараллеливание отдельных операций

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

На Concurrent Read, Exclusive Write (ЭКИПАЖ) PRAM модель, операции вставка , extractMin , decreaseKey и удалить могут быть выполнены в постоянная время , если процессоры доступны, в результате чего размера очереди приоритета есть. Далее очередь реализована как биномиальная куча. После каждой операции необходимо указать, что существует не более трех деревьев одного порядка и что наименьший корень деревьев этого порядка меньше всех корней деревьев более высокого порядка.

  • insert (e) : вставляется новое биномиальное дерево с порядком 0, единственный узел которого содержит элемент e . Затем два дерева одного порядка объединяются в одно дерево порядка, если существует три дерева порядка . Дерево с наименьшим корнем среди деревьев порядка для этого не используется. Этот шаг выполняется параллельно, при этом каждый процессор заботится о деревьях порядка. Таким образом , вставка в это выполнимо.

Ниже приводится операция в псевдокоде .

insert(e) {
  L[0] = L[0] ∪ e
  parallelesZusammenfügen()
}
parallelesZusammenfügen() {
  für jede Ordnung i parallel:
    falls |L[i]| >= 3:
      füge zwei Bäume aus L[i] \ min(L[i]) zu einem neuen Baum b zusammen
      L[i+1] = L[i+1] ∪ b
}
  • extractMin : Удаляемый минимум - это наименьший элемент деревьев порядка 0. Этот элемент удаляется. Чтобы гарантировать, что новый минимум также находится в порядке 0, дерево с наименьшим корнем разделяется для каждого порядка, и два новых дерева добавляются к порядку . Назначив каждый процессор ровно одному заказу, этот шаг можно выполнять параллельно . После этого шага, как и в операции вставки , два дерева порядка объединяются, чтобы сформировать одно дерево порядка, если существует по крайней мере три дерева порядка . Поскольку этот шаг также может выполняться параллельно для каждого заказа, extractMin может выполняться за постоянное время.
extractMin() {
  e = min(L[0])
  L[0] = L[0]\e
  für jede Ordnung i parallel:
    falls |L[i]| >= 1:
      teile min(L[i]) in zwei Bäume a,b
      L[i] = L[i] \ min(L[i])
      L[i-1] = L[i-1] ∪ {a,b}
  parallelesZusammenfügen()
  return e
}

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

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

Одновременный параллельный доступ

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

Узел 3 добавляется и устанавливает указатель с узла 2 на узел 3. Сразу после этого узел 2 удаляется, а указатель узла 1 устанавливается на узел 4. Это означает, что узел 3 больше недоступен.

Одновременный доступ к приоритетной очереди может быть реализован в модели PRAM с одновременным чтением и одновременной записью (CRCW). Далее приоритетная очередь реализована как список пропуска . Кроме того, для включения списка пропусков без блокировки используется примитив атомарной синхронизации CAS . Узлы списка пропускаемого состоят из уникального ключа, в приоритетном порядке массив из указателей на следующий узел и удаления тега. Индикатор удаления указывает, собирается ли процесс удалить узел. Это означает, что другие процессы знают, что узел собирается быть удален, и могут реагировать соответствующим образом в зависимости от выполняемых ими операций.

  • insert (e) : сначала создается новый узел с ключом и приоритетом. Кроме того, узлу передается ряд уровней. Затем начинается поиск нужной позиции в списке пропуска, куда вы должны добавить вновь созданный узел. Поиск начинается с первого узла и с самого высокого уровня и проходит по списку пропуска до самого нижнего уровня, пока не будет найдена правильная позиция. Последний пройденный узел сохраняется как предыдущий узел для каждого уровня. Кроме того, узел, на который указывает указатель узла-предшественника, сохраняется как узел-преемник. После этого для каждого уровня нового узла указатель сохраненного предыдущего узла устанавливается на новый узел. Наконец, указатели для каждого уровня нового узла устанавливаются на соответствующие узлы-преемники.
  • extractMin () : сначала просматривается список пропусков, пока не будет достигнут узел, флаг удаления которого не установлен. Затем для этого узла устанавливается флаг удаления . Затем обновляются указатели предыдущего узла.

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

K-элементные операции

Этот тип распараллеливания очередей с приоритетом вводит новые операции, которые больше не обрабатывают один элемент, а скорее элементы одновременно. Затем новая операция k_extractMin удаляет самые маленькие элементы из очереди приоритетов и возвращает их. Очередь распараллеливается в распределенной памяти. Каждый процессор имеет свою собственную частную память и локальную (последовательную) приоритетную очередь. Таким образом, элементы глобальной очереди распределяются по всем процессорам. В случае операции k_insert элементы случайным образом равномерно распределяются по процессорам, и каждый вставляется в локальные очереди приоритетов. Отдельные элементы все еще можно вставлять. При такой стратегии очень вероятно, что самые маленькие элементы в глобальном масштабе находятся в объединении локально самых маленьких элементов всех процессоров. Таким образом, каждый процессор содержит репрезентативную часть очереди с глобальным приоритетом.

k_extractMin работает в очереди с тремя процессорами. Зеленые предметы возвращаются и удаляются из очереди.

Это свойство используется с k_extractMin , удаляя самые маленькие элементы из каждой локальной очереди и собирая их в результирующий набор. Элементы остаются привязанными к их исходному процессору. Количество элементов, которые удаляются из каждой очереди с локальным приоритетом, зависит от количества процессоров . Наименьшие элементы результирующего набора определяются параллельным отбором . Очень вероятно, что это также самые маленькие элементы в мире . В противном случае элементы снова удаляются из каждой локальной очереди приоритета до тех пор, пока в результирующем наборе не появятся глобально наименьшие элементы. Теперь можно вернуть самые маленькие элементы. Все остальные элементы возвращаются в очереди с локальным приоритетом, из которых они были удалены. Время выполнения k_extractMin ожидается, когда оно описывает размер очереди приоритетов.

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

За счет одновременного удаления нескольких элементов можно добиться значительного ускорения по сравнению с последовательными очередями по приоритету. Однако не все алгоритмы могут использовать этот тип очереди приоритетов. Например, с помощью алгоритма Дейкстры нельзя редактировать сразу несколько узлов. Дейкстра берет узел с наименьшим расстоянием до начального узла из очереди приоритетов, а затем расслабляет его края. Это может изменить приоритет соседних узлов, которые уже находятся в очереди приоритетов. При удалении узлов с наименьшим расстоянием может случиться так, что обработка одного из узлов изменит приоритет одного из других узлов. Этот узел следует редактировать только позже, но теперь он будет отредактирован раньше. Затем этот узел помечается как посещенный слишком рано. В этом случае путь от начального узла до этого узла найден, но расстояние не минимальное. Другими словами, при использовании k-элементных операций для алгоритма Дейкстры свойство установки метки уничтожается.

литература

  • Джордж Ф. Люгер: Искусственный интеллект. Стратегии решения сложных проблем . Исследования Пирсона, 2001, ISBN 3-8273-7002-7 .

веб ссылки

Индивидуальные доказательства

  1. ^ A b c Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест : Введение в алгоритмы . В: MIT Press и McGraw-Hill . 1990, ISBN 0-262-03141-8 .
  2. ^ Кларк А. Клейн: линейные списки и очереди приоритетов как сбалансированные двоичные деревья (докторская диссертация) . Ред .: Факультет компьютерных наук Стэнфордского университета. 1972, ISBN 0-8240-4407-X ( stanford.edu ).
  3. Биномиальная куча | Блестящая вики по математике и науке. brilliant.org, по состоянию на 30 сентября 2019 г. (американский английский).
  4. Майкл Фредман, Роберт Тарьян : Куча Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети . В: Журнал Ассоциации вычислительной техники . Лента 34 , нет. 3 , июль 1987 г., стр. 596-615 , DOI : 10,1145 / 28869,28874 ( ict.ac.cn [PDF]).
  5. a b Герт Бродал: приоритетные очереди на параллельных машинах . В кн . : Теория алгоритмов - SWAT 96 . Springer-Verlag, 1996, стр. 416-427 , DOI : 10.1007 / 3-540-61422-2_150 .
  6. a b Хокан Сунделл, Филиппа Цигас: Быстрые и свободные от блокировок параллельные очереди приоритетов для многопоточной системы . В: Журнал параллельных и распределенных вычислений . Лента 65 , нет. 5 , 2005, с. 609-627 , DOI : 10,1109 / IPDPS.2003.1213189 .
  7. ^ Jonsson Lindén: Очередь одновременного приоритета на основе Skiplist с минимальной конкуренцией за память . В: Технический отчет 2018-003 . 2013 ( uu.se ).
  8. a b c Питер Сандерс , Курт Мельхорн, Мартин Дицфельбингер, Роман Дементьев: Последовательные и параллельные алгоритмы и структуры данных - Базовый набор инструментов . Издательство Springer International , 2019, стр. 226-229 , DOI : 10.1007 / 978-3-030-25209-0 .