Очередь ведра

Структура данных для целочисленных приоритетов

Очередь из контейнеров — это структура данных , реализующая абстрактный тип данных очереди приоритетов : она поддерживает динамическую коллекцию элементов с числовыми приоритетами и обеспечивает быстрый доступ к элементу с минимальным (или максимальным) приоритетом. В очереди из контейнеров приоритеты должны быть целыми числами , и она особенно подходит для приложений, в которых приоритеты имеют небольшой диапазон. ^[1] Очередь из контейнеров имеет форму массива контейнеров: массива данных , индексированного по приоритетам, ячейки которого содержат коллекции элементов с одинаковым приоритетом. При использовании этой структуры данных вставка элементов и изменение их приоритета занимают постоянное время . Поиск и удаление элемента с минимальным приоритетом занимает время, пропорциональное количеству контейнеров или, при сохранении указателя на последний найденный контейнер, время, пропорциональное разнице в приоритетах между последовательными операциями.

Очередь с ведром — это аналог приоритетной очереди сортировки Pigeonhole (также называемой сортировкой с ведром), алгоритма сортировки, который помещает элементы в ведры, индексированные по их приоритетам, а затем объединяет ведры. Использование очереди с ведром в качестве приоритетной очереди в сортировке выбором дает форму алгоритма сортировки Pigeonhole. ^[2] Очереди с ведром также называются очередями с ведром с приоритетом ^[3] или очередями с приоритетом ограниченной высоты . ^[1] При использовании для квантованных приближений к действительным числовым приоритетам их также называют неаккуратными очередями с приоритетом ^[4] или псевдоприоритетными очередями . ^[5] Они тесно связаны с календарной очередью , структурой, которая использует аналогичный массив ведров для точной приоритезации действительными числами.

Приложения очереди из ведер включают вычисление вырожденности графа , быстрые алгоритмы для кратчайших путей и широчайших путей для графов с весами, которые являются небольшими целыми числами или уже отсортированы, и жадные алгоритмы приближения для задачи покрытия множества . Квантованная версия структуры также применялась к планированию ^[2] и к марширующим кубам в компьютерной графике . ^[4] Первое использование очереди из ведер ^[6] было в алгоритме кратчайшего пути Дайала (1969). ^[7]

Операция

Базовая структура данных

Очередь контейнеров может обрабатывать элементы с целочисленными приоритетами в диапазоне от 0 или 1 до некоторой известной границы C , а также операции, которые вставляют элементы, изменяют приоритет элементов или извлекают (находят и удаляют) элемент, имеющий минимальный (или максимальный) приоритет. Она состоит из массива A структур данных контейнера ; в большинстве источников эти контейнеры представляют собой двусвязные списки, но в качестве альтернативы они могут быть динамическими массивами ^[3] или динамическими наборами . Контейнер в ячейке массива p [ p ] хранит коллекцию элементов, приоритет которых равен p .

Очередь контейнеров может обрабатывать следующие операции:

• Чтобы вставить элемент x с приоритетом p , добавьте x в контейнер в A [ p ] .
• Чтобы изменить приоритет элемента, удалите его из контейнера со старым приоритетом и вставьте его обратно в контейнер с новым приоритетом.
• Чтобы извлечь элемент с минимальным или максимальным приоритетом, выполните последовательный поиск в массиве, чтобы найти соответственно первый или последний непустой контейнер, выберите произвольный элемент из этого контейнера и удалите его из контейнера.

Таким образом, вставки и изменения приоритета занимают постоянное время, а извлечение элемента с минимальным или максимальным приоритетом занимает время O ( C ) . ^{[1] [6] [8]}

Оптимизации

В качестве оптимизации структура данных может начинать каждый последовательный поиск непустого контейнера с последнего найденного непустого контейнера, а не с начала массива. Это можно сделать двумя способами: ленивым (откладывая эти последовательные поиски до тех пор, пока они не понадобятся) или жадным (выполняя поиск заранее). Выбор времени выполнения поиска влияет на то, какие из операций структуры данных замедляются этими поисками. Первоначальная версия структуры Dial использовала ленивый поиск. Это можно сделать, поддерживая индекс L , который является нижней границей минимального приоритета любого элемента, находящегося в очереди в данный момент. При вставке нового элемента L следует обновить до минимума его старого значения и приоритета нового элемента. При поиске элемента с минимальным приоритетом поиск может начинаться с L вместо нуля, а после поиска L следует оставить равным приоритету, который был найден в ходе поиска. ^{[7] [9]} В качестве альтернативы жадная версия этой оптимизации сохраняет L обновленным, так что он всегда указывает на первый непустой контейнер. При вставке нового элемента с приоритетом, меньшим, чем L , структура данных устанавливает L на новый приоритет, а при удалении последнего элемента из контейнера с приоритетом L выполняет последовательный поиск по большим индексам, пока не найдется непустой контейнер и не установит L на приоритет полученного контейнера. ^[1]

В любом из этих двух вариантов каждый последовательный поиск занимает время, пропорциональное разнице между старым и новым значениями L . Это может быть значительно быстрее, чем ограничение по времени O ( C ) для поисков в неоптимизированной версии структуры данных. Во многих приложениях приоритетных очередей, таких как алгоритм Дейкстры , минимальные приоритеты образуют монотонную последовательность , что позволяет использовать монотонную приоритетную очередь . В этих приложениях, как для ленивых, так и для энергичных вариаций оптимизированной структуры, последовательные поиски непустых ведер охватывают непересекающиеся диапазоны ведер. Поскольку каждое ведро находится не более чем в одном из этих диапазонов, их количество шагов в сумме составляет не более C . Следовательно, в этих приложениях общее время для последовательности из n операций составляет O ( n + C ) , а не более медленное ограничение по времени O ( nC ), которое было бы получено без этой оптимизации. ^[9] Соответствующая оптимизация может быть применена в приложениях, где очередь контейнеров используется для поиска элементов с максимальным приоритетом, но в этом случае она должна поддерживать индекс, который ограничивает максимальный приоритет сверху, а последовательный поиск непустого контейнера должен осуществляться сверху вниз от этой верхней границы. ^[10]

Другая оптимизация (уже предложенная Дайалом 1969) может быть использована для экономии места, когда приоритеты монотонны и на протяжении всего алгоритма всегда попадают в диапазон значений r , а не простираются на весь диапазон от 0 до C. В этом случае можно индексировать массив по приоритетам по модулю r, а не по их фактическим значениям. Поиск элемента с минимальным приоритетом всегда должен начинаться с предыдущего минимума, чтобы избежать приоритетов, которые выше минимума, но имеют меньшие модули. В частности, эта идея может быть применена в алгоритме Дейкстры на графах, длины ребер которых являются целыми числами в диапазоне от 1 до r . ^[8]

Поскольку создание новой очереди ведер включает инициализацию массива пустых ведер, этот шаг инициализации занимает время, пропорциональное количеству приоритетов. Разновидность очереди ведер, описанная Дональдом Б. Джонсоном в 1981 году, вместо этого сохраняет только непустые ведра в связанном списке, отсортированном по их приоритетам, и использует вспомогательное дерево поиска для быстрого нахождения позиции в этом связанном списке для любых новых ведер. Требуется время O (log log C ) для инициализации этой вариантной структуры, постоянное время для поиска элемента с минимальным или максимальным приоритетом и время O (log log D ) для вставки или удаления элемента, где D — это разница между ближайшим меньшим и большим приоритетами к приоритету вставленного или удаленного элемента. ^[11]

Пример

Например, рассмотрим очередь контейнеров с четырьмя приоритетами, числами 0, 1, 2 и 3. Она состоит из массива, четыре ячейки которого содержат набор элементов, изначально пустых. Для целей этого примера можно записать как последовательность из четырех наборов в скобках: . Рассмотрим последовательность операций, в которой мы вставляем два элемента и с тем же приоритетом 1, вставляем третий элемент с приоритетом 3, меняем приоритет на 3, а затем выполняем два извлечения элемента с минимальным приоритетом. ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A=[\emptyset ,\emptyset ,\emptyset ,\emptyset ]}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle x}$

• После вставки с приоритетом 1, . ${\displaystyle x}$ ${\displaystyle A=[\emptyset ,\{x\},\emptyset ,\emptyset ]}$
• После вставки с приоритетом 1, . ${\displaystyle y}$ ${\displaystyle A=[\emptyset ,\{x,y\},\emptyset ,\emptyset ]}$
• После вставки z с приоритетом 3, . ${\displaystyle A=[\emptyset ,\{x,y\},\emptyset ,\{z\}]}$
• Изменение приоритета x с 1 до трех включает его удаление из и добавление к , после чего . ${\displaystyle A[1]}$ ${\displaystyle A[3]}$ ${\displaystyle A=[\emptyset ,\{y\},\emptyset ,\{x,z\}]}$
• Извлечение элемента с минимальным приоритетом в базовой версии очереди ведра выполняет поиск с начала для нахождения его первого непустого элемента: пуст, но , непустое множество. Он выбирает произвольный элемент этого множества (единственный элемент, ) в качестве элемента с минимальным приоритетом. Удаление из структуры оставляет . ${\displaystyle A}$ ${\displaystyle A[0]}$ ${\displaystyle A[1]=\{y\}}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle A=[\emptyset ,\emptyset ,\emptyset ,\{x,z\}]}$
• Вторая операция извлечения в базовой версии очереди контейнеров снова ищет с начала массива: , , , непустой. В улучшенных вариантах очереди контейнеров этот поиск начинается с последней позиции, которая оказалась непустой, . В любом случае оказывается первым непустым набором. Один из его элементов выбирается произвольно в качестве элемента с минимальным приоритетом; например, может быть выбран. Этот элемент удаляется, оставляя . ${\displaystyle A[0]=\emptyset }$ ${\displaystyle A[1]=\emptyset }$ ${\displaystyle A[2]=\emptyset }$ ${\displaystyle A[3]={}}$ ${\displaystyle A[1]}$ ${\displaystyle A[3]=\{x,z\}}$ ${\displaystyle z}$ ${\displaystyle A=[\emptyset ,\emptyset ,\emptyset ,\{x\}]}$

Приложения

Вырожденность графа

Очередь из блоков может использоваться для поддержания вершин неориентированного графа , упорядоченных по их степеням , и многократного поиска и удаления вершины минимальной степени. ^[1] Этот жадный алгоритм может использоваться для вычисления вырожденности заданного графа, равной наибольшей степени любой вершины на момент ее удаления. Алгоритм занимает линейное время , с оптимизацией или без нее, которая поддерживает нижнюю границу минимального приоритета, поскольку каждая вершина находится за время, пропорциональное ее степени, а сумма всех степеней вершин линейна по числу ребер графа. ^[12]

Алгоритм Дайала для кратчайших путей

В алгоритме Дейкстры для кратчайших путей в ориентированных графах с весами ребер, которые являются положительными целыми числами, приоритеты являются монотонными, ^[13] и монотонная очередь из блоков может быть использована для получения временного ограничения O ( m + dc ) , где m — количество ребер, d — диаметр сети, а c — максимальная (целочисленная) стоимость связи. ^{[9] [14]} Этот вариант алгоритма Дейкстры также известен как алгоритм Дайала , ^[9] в честь Роберта Б. Дайала, который опубликовал его в 1969 году. ^[7] Та же идея также работает, используя квантованную очередь из блоков, для графов с положительными действительными весами ребер, когда отношение максимального веса к минимальному не превышает c . ^[15] В этой квантованной версии алгоритма вершины обрабатываются не в порядке, по сравнению с результатом с неквантованной очередью с приоритетами, но правильные кратчайшие пути все равно находятся. ^[5] В этих алгоритмах приоритеты будут охватывать только диапазон шириной c + 1 , поэтому модульную оптимизацию можно использовать для сокращения пространства до O ( n + c ) . ^{[8] [14]}

Вариант того же алгоритма может быть использован для задачи поиска самого широкого пути . В сочетании с методами быстрого разбиения нецелочисленных весов ребер на подмножества, которым можно назначить целочисленные приоритеты, это приводит к решениям с почти линейным временем для версии задачи поиска самого широкого пути с одним источником и одним пунктом назначения. ^[16]

Крышка набора Greedy

Задача покрытия множеств имеет в качестве входных данных семейство множеств . Выходными данными должно быть подсемейство этих множеств с тем же объединением, что и исходное семейство, включающее как можно меньше множеств. Она NP-трудна , но имеет жадный алгоритм аппроксимации , который достигает логарифмического отношения аппроксимации, по сути, наилучшего возможного, если только P = NP . ^[17] Этот алгоритм аппроксимации выбирает свое подсемейство, многократно выбирая множество, которое покрывает максимально возможное количество оставшихся непокрытых элементов. ^[18] Стандартное упражнение по проектированию алгоритмов требует реализации этого алгоритма, которая занимает линейное время по размеру входных данных, который является суммой размеров всех входных множеств. ^[19]

Это можно решить с помощью очереди наборов в семействе входных данных, упорядоченных по числу оставшихся элементов, которые они покрывают. Каждый раз, когда жадный алгоритм выбирает набор в качестве части своего вывода, вновь охваченные элементы набора должны вычитаться из приоритетов других наборов, которые их покрывают; в ходе работы алгоритма количество этих изменений приоритетов равно просто сумме размеров входных наборов. Приоритеты представляют собой монотонно убывающие целые числа, ограниченные сверху числом элементов, которые должны быть охвачены. Каждый выбор жадного алгоритма включает в себя поиск набора с максимальным приоритетом, что можно сделать путем сканирования вниз по контейнерам очереди контейнеров, начиная с самого последнего предыдущего максимального значения. Общее время линейно зависит от размера входных данных. ^[10]

Планирование

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

Разновидность квантованной структуры данных очереди ведер, календарная очередь , была применена для планирования дискретно-событийных симуляций , где элементы в очереди являются будущими событиями, приоритет которых определяется временем в симуляции, когда события должны произойти. В этом приложении порядок событий имеет решающее значение, поэтому приоритеты не могут быть аппроксимированы. Поэтому календарная очередь выполняет поиск элемента с минимальным приоритетом иным способом, чем очередь ведер: в очереди ведер может быть возвращен любой элемент первого непустого ведра, но вместо этого календарная очередь ищет все элементы в этом ведерке, чтобы определить, какой из них имеет наименьший неквантованный приоритет. Чтобы поддерживать эти поиски быстрыми, эта вариация пытается поддерживать количество ведер пропорциональным количеству элементов, регулируя масштаб квантования и перестраивая структуру данных, когда она выходит из равновесия. Календарные очереди могут быть медленнее очередей с контейнерами в худшем случае (когда множество элементов попадают в один и тот же наименьший контейнер), но они быстры, когда элементы равномерно распределены по контейнерам, в результате чего средний размер контейнера остается постоянным. ^{[20] [21]}

Быстрый марш

В прикладной математике и численных методах решения дифференциальных уравнений неаккуратные очереди приоритетов использовались для расстановки приоритетов шагов метода быстрого марша для решения краевых задач уравнения Эйконала , используемого для моделирования распространения волн . Этот метод находит моменты времени, в которые движущаяся граница пересекает набор дискретных точек (например, точек целочисленной сетки), используя метод расстановки приоритетов, напоминающий непрерывную версию алгоритма Дейкстры , и его время выполнения доминирует его очередь приоритетов этих точек. Его можно ускорить до линейного времени, округлив приоритеты, используемые в этом алгоритме, до целых чисел и используя очередь контейнеров для этих целых чисел. Как и в алгоритмах Дейкстры и Дайала, приоритеты монотонны, поэтому быстрый марш может использовать монотонную оптимизацию очереди контейнеров и ее анализ. Однако дискретизация вносит некоторую ошибку в полученные вычисления. ^[4]

Смотрите также

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

Ссылки

1. Скиена, Стивен С. (1998), Руководство по разработке алгоритмов, Springer, стр. 181, ISBN 9780387948607.
2. Figueira, NR (1997), "Решение проблемы приоритетной очереди дисциплин обслуживания с крайним сроком", Труды Шестой международной конференции по компьютерным коммуникациям и сетям , IEEE Computer Society Press, стр. 320–325, doi :10.1109/icccn.1997.623330, S2CID  5611516
3. Henzinger, Monika ; Noe, Alexander; Schulz, Christian (2019), "Shared-memory exact minimum cuts", 2019 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2019, Рио-де-Жанейро, Бразилия, 20-24 мая 2019 г. , стр. 13–22, arXiv : 1808.05458 , doi : 10.1109/IPDPS.2019.00013, S2CID  52019258
4. Раш, Кристиан; Зацгер, Томас (2009), «Замечания о реализации O (N) метода быстрого марша» (PDF) , IMA Journal of Numerical Analysis , 29 (3): 806–813, doi : 10.1093/imanum/drm028, MR  2520171
5. Robledo, Alicia; Guivant, José E. (2010), «Псевдоприоритетные очереди для производительности в реальном времени в процессах динамического программирования, применяемых к планированию пути» (PDF) , в Wyeth, Gordon; Upcroft, Ben (ред.), Australasian Conference on Robotics and Automation
6. Эделькамп, Стефан; Шредль, Стефан (2011), "3.1.1 Структуры данных сегмента", Эвристический поиск: теория и приложения , Elsevier, стр. 90–92, ISBN 9780080919737. См. также стр. 157 для истории и названия этого сооружения.
7. Dial, Robert B. (1969), «Алгоритм 360: Лес кратчайших путей с топологическим упорядочением [H]», Communications of the ACM , 12 (11): 632–633, doi : 10.1145/363269.363610 , S2CID  6754003.
8. Мельхорн, Курт ; Сандерс, Питер (2008), "10.5.1 Очереди блоков", Алгоритмы и структуры данных: базовый набор инструментов , Springer, стр. 201, ISBN 9783540779773.
9. Берцекас, Димитрий П. (1991), «Алгоритм Дайала», Оптимизация линейных сетей: алгоритмы и коды , Кембридж, Массачусетс: MIT Press, стр. 72–75, ISBN 0-262-02334-2, МР  1201582
10. Lim, CL; Moffat, Alistair; Wirth, Anthony Ian (2014), «Ленивые и энергичные подходы к задаче покрытия множества», в Thomas, Bruce; Parry, Dave (ред.), Thirty-Seventh Australasian Computer Science Conference, ACSC 2014, Окленд, Новая Зеландия, январь 2014 г. , CRPIT, т. 147, Australian Computer Society, стр. 19–27. См. в частности раздел 2.4 «Приоритетная очередь», стр. 22.
11. Джонсон, Дональд Б. (1981), «Приоритетная очередь, в которой инициализация и операции очереди занимают O (log log D ) времени», Математическая теория систем , 15 (4): 295–309, doi :10.1007/BF01786986, MR  0683047, S2CID  35703411
12. Матула, Дэвид В .; Бек, Л. Л. (1983), «Алгоритмы упорядочения наименьшего последнего элемента, кластеризации и раскраски графов», Журнал ACM , 30 (3): 417–427, doi : 10.1145/2402.322385 , MR  0709826, S2CID  4417741.
13. Варгезе, Джордж (2005), Сетевые алгоритмы: междисциплинарный подход к проектированию быстрых сетевых устройств, Morgan Kaufmann, стр. 78–80, ISBN 9780120884773.
14. Festa, Paola (2006), «Алгоритмы кратчайшего пути», в Resende, Mauricio GC ; Pardalos, Panos M. (ред.), Handbook of Optimization in Telecommunications , Boston: Springer, стр. 185–210, doi :10.1007/978-0-387-30165-5_8; см. в частности раздел 8.3.3.6, «Реализация Dial», стр. 194–195.
15. Мельхорн и Сандерс (2008) (Упражнение 10.11, стр. 201) приписывают эту идею статье 1978 года Е. А. Динича (Ефима Диница).
16. Габов, Гарольд Н.; Тарьян , Роберт Э. (1988), «Алгоритмы для двух задач оптимизации узких мест», Журнал алгоритмов , 9 (3): 411–417, doi :10.1016/0196-6774(88)90031-4, MR  0955149
17. Динур, Ирит ; Стейрер, Дэвид (2014), «Аналитический подход к параллельному повторению», в Шмойс, Дэвид Б. (ред.), Симпозиум по теории вычислений, STOC 2014, Нью-Йорк, штат Нью-Йорк, США, 31 мая - 3 июня 2014 г. , ACM, стр. 624–633, arXiv : 1305.1979 , doi : 10.1145/2591796.2591884, MR  3238990, S2CID  15252482
18. Джонсон, Дэвид С. (1974), «Аппроксимационные алгоритмы для комбинаторных задач», Журнал компьютерных и системных наук , 9 (3): 256–278, doi :10.1016/S0022-0000(74)80044-9, MR  0449012
19. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2009) [1990], «Упражнение 35.3-3», Введение в алгоритмы (3-е изд.), MIT Press и McGraw-Hill, стр. 1122, ISBN 0-262-03384-4
20. Браун, Р. (октябрь 1988 г.), «Календарные очереди: быстрая реализация приоритетной очереди для задачи набора событий моделирования», Communications of the ACM , 31 (10): 1220–1227, doi : 10.1145/63039.63045 , S2CID  32086497 ${\displaystyle O(1)}$
21. Эриксон, К. Брюс; Ладнер, Ричард Э .; Ламарка, Энтони (2000), «Оптимизация статических очередей календаря», ACM Transactions on Modeling and Computer Simulation , 10 (3): 179–214, doi : 10.1145/361026.361028