버킷 대기열

버킷 대기열은 우선 순위 대기열 추상 데이터 유형을 구현하는 데이터 구조로, 숫자 우선 순위를 가진 요소의 동적 컬렉션을 유지하며 최소(또는 최대) 우선 순위를 가진 요소에 빠르게 액세스할 수 있다. 버킷 대기열에서 우선순위는 정수여야 하며, 특히 우선순위의 범위가 작은 애플리케이션에 적합하다.^[1] 버킷 대기열은 우선순위에 의해 색인화된 배열 데이터 구조와 같은 버킷 배열 형태를 가지고 있으며, 셀에는 서로 동일한 우선순위를 가진 항목의 컬렉션이 들어 있다. 이러한 데이터 구조에서는 요소의 삽입과 그 우선순위 변경은 일정한 시간이 걸린다. 최소 우선순위 요소를 검색하고 제거하려면 버킷 수에 비례하는 시간이 걸리거나, 가장 최근에 발견된 버킷에 대한 포인터를 유지함으로써 연속 작업 간의 우선순위 차이에 비례하는 시간 내에 시간이 걸린다.

버킷 대기열은 비둘기홀 정렬의 우선순위 큐 아날로그(버킷 정렬이라고도 함)로, 우선순위에 의해 색인된 버킷에 요소를 배치한 다음 버킷을 연결시키는 정렬 알고리즘이다. 버킷 대기열을 선택 정렬의 우선 순위 대기열로 사용하면 비둘기 구멍 정렬 알고리즘의 형식이 제공된다.^[2] 버킷 대기열을 버킷 우선 순위 대기열^[3] 또는 경계 높이 우선 순위 대기열이라고도 한다.^[1] 실제 수 우선순위에 대한 정량화된 근사치에 사용될 때, 이를 비정형 우선 순위 대기열^[4] 또는 유사 우선 순위 대기열이라고도 한다.^[5] 그것들은 실제 숫자에 의한 정확한 우선순위를 정하기 위해 유사한 버킷 배열을 사용하는 구조인 달력 대기열과 밀접하게 관련되어 있다.

버킷 대기열의 응용 프로그램에는 그래프의 퇴보성 계산, 작은 정수이거나 이미 정렬된 가중치를 가진 그래프의 최단 경로 및 가장 넓은 경로에 대한 빠른 알고리즘, 세트 커버 문제에 대한 탐욕스러운 근사 알고리즘이 포함된다. 구조물의 정량화된 버전은 컴퓨터[2] 그래픽의 스케줄링과 행군 큐브에도 적용되었다.^[4] 버킷 대기열의^[6] 첫 사용은 다이얼(1969년)에 의한 최단 경로 알고리즘에 있었다.^[7]

작전

기본 데이터 구조

버킷 대기열은 0 또는 1에서 일부 알려진 바운드 C까지의 범위에서 정수 우선순위를 가진 요소와 요소를 삽입하거나 요소의 우선순위를 변경하거나 최소(또는 최대) 우선순위를 가진 요소를 추출(찾아 제거)하는 작업을 처리할 수 있다. 그것은 컨테이너 데이터 구조의 배열 A로 구성된다. 대부분의 소스에서 이 컨테이너들은 이중으로 연결된 목록이지만 그것들은 동적 배열이나^[3] 동적 집합일 수 있다. pth 어레이 셀 A[p]의 컨테이너는 우선 순위가 p인 요소의 컬렉션을 저장한다.

버킷 대기열은 다음 작업을 처리할 수 있다.

• x 요소를 p와 함께 삽입하려면 x를 A[p]의 용기에 추가하십시오.
• 요소의 우선 순위를 변경하려면 기존 우선 순위에 따라 용기에서 제거한 후 새 우선 순위를 위해 용기에 다시 삽입하십시오.
• 최소 또는 최대 우선 순위로 요소를 추출하려면 배열에서 순차 검색을 수행하여 비어 있지 않은 첫 번째 또는 마지막 컨테이너를 찾은 다음 이 컨테이너에서 임의 요소를 선택하고 컨테이너에서 제거하십시오.

이와 같이 삽입과 우선순위 변경은 일정한 시간이 소요되며, 최소 또는 최대 우선순위 요소를 추출하는 데는 O(C) 시간이 소요된다.^[1][6][8]

최적화

최적화로서 데이터 구조는 배열의 시작 대신 가장 최근에 발견된 비어 있지 않은 버킷에서 각 순차적 검색을 시작할 수 있다. 이는 게으름(필요할 때까지 순차적 검색을 지연) 또는 열심(일단 검색을 미리 수행)의 두 가지 방법 중 하나로 수행될 수 있다. 검색 시기의 선택은 이러한 검색에 의해 어떤 데이터 구조 작업이 느려지는지에 영향을 미친다. 다이얼의 원래 구조는 게으른 검색을 사용했다. 이는 현재 대기열에 있는 요소의 최소 우선순위 하한인 인덱스 L을 유지함으로써 수행할 수 있다. 새 요소를 삽입할 때 L은 이전 값의 최소값과 새 요소의 우선순위로 업데이트해야 한다. 최소 우선순위 요소를 검색할 때 0이 아닌 L에서 검색을 시작할 수 있으며, 검색 후 L은 검색에서 발견된 우선순위와 동일하게 유지되어야 한다.^[7][9] 또는 이 최적화의 열렬한 버전은 항상 비어 있지 않은 첫 번째 버킷을 가리키도록 L을 업데이트한다. 우선순위가 L보다 작은 새 요소를 삽입할 때 데이터 구조는 L을 새 우선순위로 설정하고, 우선순위가 L인 버킷에서 마지막 요소를 제거할 때는 비어 있지 않은 버킷을 찾을 때까지 큰 인덱스를 통해 순차적으로 검색을 수행하여 결과 버킷의 우선순위로 L을 설정한다.^[1]

이 두 가지 변이 중 하나에서, 각각의 순차적 검색은 L의 이전 값과 새로운 값의 차이에 비례하는 시간이 걸린다. 이는 최적화되지 않은 버전의 데이터 구조에서 검색에 대한 O(C) 시간보다 훨씬 더 빠를 수 있다. Dijkstra 알고리즘과 같은 우선순위 대기열의 많은 애플리케이션에서, 최소 우선순위는 단조로운 순서를 형성하여 단조로운 우선순위 대기열을 사용할 수 있다. 이러한 애플리케이션에서, 최적화된 구조의 게으르고 열렬한 변동에 대해, 비어 있지 않은 버킷에 대한 순차적 검색은 버킷의 분리 범위를 다룬다. 각 버킷은 이 범위 중 최대 한 곳에 있기 때문에, 이들의 단계 수는 최대 C에 추가된다. 따라서 이러한 애플리케이션에서, 이러한 최적화 없이 발생할 수 있는 느린 O(nC) 시간 범위보다는 일련의 n 작업에 대한 총 시간이 O(n + C)이다.^[9] 버킷 대기열을 사용하여 최대 우선순위 요소를 찾는 애플리케이션에는 해당 최적화를 적용할 수 있지만, 이 경우 최대 우선순위를 초과하는 인덱스를 유지해야 하며, 비어 있지 않은 버킷에 대한 순차적 검색은 이 상한에서 아래로 진행해야 한다.^[10]

우선순위가 단조로울 때 또 다른 최적화(Dial 1969에 의해 이미 부여된)를 사용하여 공간을 절약할 수 있으며, 알고리즘의 과정 전체에 걸쳐 0에서 C까지 전체 범위를 확장하는 것이 아니라 항상 r 값의 범위에 속한다. 이 경우 실제 값이 아닌 우선순위 modulo r에 따라 배열을 인덱싱할 수 있다. 최소 우선순위 요소에 대한 검색은 최소값보다 높지만 모듈리가 낮은 우선순위를 피하기 위해 항상 이전 최소값에서 시작해야 한다. 특히 이 아이디어는 1에서 r까지의 범위에서 에지 길이가 정수인 그래프에 Dijkstra 알고리즘에 적용할 수 있다.^[8]

새 버킷 대기열을 생성하려면 빈 버킷의 배열을 초기화해야 하므로 이 초기화 단계는 우선순위 수에 비례하는 시간이 걸린다. Donald B가 설명하는 버킷 대기열의 변형. 1981년 Johnson은 대신 비어 있지 않은 버킷만 우선순위에 따라 정렬된 링크된 목록에 저장하고 보조 검색 트리를 사용하여 새로운 버킷에 대한 이 링크된 목록에서 위치를 신속하게 찾는다. 이 변형 구조를 초기화하는 데는 O(로그 로그 C), 최소 또는 최대 우선순위를 가진 요소를 찾는 데는 일정한 시간, 요소를 삽입하거나 삭제하는 데는 O(로그 로그 D)가 소요되는데, 여기서 D는 삽입되거나 삭제된 요소의 우선순위와 가장 가까운 더 작은 우선순위 간의 차이다.^[11]

예

예를 들어, 숫자 0, 1, 2, 3의 네 가지 우선 순위를 가진 버킷 대기열을 생각해 보십시오. 처음에는 비어 있는 4개의 셀이 각각 요소 집합을 포함하는 $어레이$ A ${\displaystyle A}$로 구성된다. 이 예제의 목적상 $A{\displaystyle }$ ${\displaystyle A}$은(는) 다음 4개의 세트로 구성된 브라켓형 시퀀스로 작성할$$ 수 있다. ${\displaystyle A=[\emptyset ,\emptyset ,\emptyset ,\emptyset ]}$. Consider a sequence of operations in which we insert two elements ${\displaystyle x}$ and ${\displaystyle y}$ with the same priority 1, insert a third element ${\displaystyle z}$ with priority 3, change the priority of ${\d$$isplaystyle x}$ ~ 3을$$ 선택한 다음 최소 우선순위 요소의 두 가지 추출을 수행하십시오.

• 우선 순위가 1인$$ $x{\displaystyle }$ ${\displaystyle x}$을(를) 삽입한 후 $A{\displaystyle }$=${\displaystyle }$[ ${\displaystyle \varnothing ,}${ x ${\displaystyle \},}$ ${\displaystyle \varnothing ,}$ ${\displaystyle \mathrm{]}}$ ${\displaystyle ]}$ ${\displaystyle$ A$=[\empt,\x\},\emptysset,\$empt $]\}.$
• 우선 순위가 1인$$ $y{\displaystyle }$ ${\displaystyle y}$을(를) 삽입한 후 $A{\displaystyle }$=${\displaystyle }$[ ${\displaystyle \varnothing ,}${ ${\displaystyle x,}$ ${\displaystyle y\},}$ ${\displaystyle \varnothing ,}$ ${\displaystyle \mathrm{]}}$ ${\displaystyle ]}$ ${\displaystyle$ A$=[\empt,\x,y\},\empt,\empt$ $]\}.$
• 우선 순위 3으로 z를 삽입한 $후{\displaystyle }$ A${\displaystyle }$= [${\displaystyle \mathrm{}\varnothing ,}${ x${\displaystyle ,}$ ${\displaystyle y}$ ${\displaystyle \},\varnothing ,}${ ${\displaystyle z]}$ ${\displaystyle A=[\emptyset,\x,y\},\emptysset,\{z$
• Changing the priority of x from 1 to three involves removing it from ${\displaystyle A[1]}$ and adding it to ${\displaystyle A[3]}$, after which ${\displaystyle A=[\emptyset ,\{y\},\emptyset ,\{x,z\}]}$.
• 버킷 대기열의 기본 버전에서 최소 우선 순위 요소를 추출하면 $A{\displaystyle }$ ${\displaystyle A}$의 시작부터 검색하여$$ 비어 있지 않은 첫 번째 요소를 찾으십시오. ${\displaystyle A}$[ ${\displaystyle 0}$ ${\displaystyle ]}$ ${\displaystyle A[0]}$은(는) 비어 있지만 ${\displaystyle A}$[ ${\displaystyle 1}$ ${\displaystyle ]}$=${\displaystyle }${ y ${\displaystyle \}}$ ${\displaystyle A[1]=\{y\}}}$은$($는) 비어 있지 않은 집합이다. 이 집합의 임의 요소(유일한 요소, $y{\displaystyle }$ ${\displaystyle y}$)를 최소 우선순위 요소로 선택한다. 구조에서$$ $y{\displaystyle }$ ${\displaystyle y}$을(를) 제거하면 $A{\displaystyle }$=${\displaystyle }$[ ${\displaystyle \varnothing ,\mathrm{}}$∅,${\displaystyle \varnothing ,}${ ${\displaystyle x,}$ ${\displaystyle z}$ ${\displaystyle ]}$ ${\displaystyle A=[\empt,\empt,\emptyset,\{x,z\}]}$이(가) 남는다$.$
• 버킷 대기열의 기본 버전에서 두 번째 추출 작업은 어레이의 시작부터 다시 검색한다. ${\displaystyle A}$$$${\displaystyle }$[ ${\displaystyle 0}$ ${\displaystyle ]}$= ${\displaystyle \mathrm{\varnothing }}$ ${\displaystyle A[0]=\emptyet$ $\},$ $A{\displaystyle }$[ ${\displaystyle 1}$ ${\displaystyle ]}$= ${\displaystyle \mathrm{\varnothing }}$ ${\$$displaystyle$ $A[1]=\emptyet },$ $A{\displaystyle }$[ ${\displaystyle 3]}$ =$${\$displaystystyle$ A$[3]={}}}}}}}}}.$ 버킷 대기열의 개선된 변형에서 이 검색은 대신 $비어{\displaystyle }$ 있지 않은 A${\displaystyle }$[ ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle A[1]}$의 마지막 위치에서 시작한다$.$ 두 경우 모두 $A{\displaystyle }$[ ${\displaystyle 3}$ ${\displaystyle ]}$=${\displaystyle }${ ${\displaystyle x,}$ z ${\displaystyle \}}$ ${\displaystyle A[3]=\{x,z\}}}}$이 비어 있지 않은 첫 번째 집합인 것으로 확인된다$$. 그 요소 중 하나는 최소 우선순위 요소로 임의로 선택된다. 예를 들어 $z{\displaystyle }$ ${\displaystyle$ z$}$을(를) 선택할 수 있다$$. $이{\displaystyle }$ 요소는 제거되어 A${\displaystyle }$=${\displaystyle }$[ ${\displaystyle \mathrm{\varnothing ,}\mathrm{\varnothing ,}}$∅,${\displaystyle \mathrm{\varnothing ,}}$ { x ${\displaystyle ]}$ ${\displaystyle$ A$=[\empteset,\emptyset,\emptyset,\{x\}}}}$이(가) 남는다$.$

적용들

그래프 퇴행성

버킷 대기열은 각도에 따라 우선순위를 정하고 최소도의 정점을 반복적으로 찾아 제거하는 데 사용될 수 있다.^[1] 이 탐욕스러운 알고리즘은 주어진 그래프의 퇴행성을 계산하는 데 사용될 수 있는데, 이는 해당 그래프가 제거될 당시 어떤 정점의 가장 큰 정도와 같다. 알고리즘은 각 꼭지점이 그 정도에 비례하는 시간 내에 발견되고 모든 정점도의 합이 그래프의 가장자리 수로 선형이기 때문에 최소 우선순위에서 하한을 유지하는 최적화가 있든 없든 선형 시간이 걸린다.^[12]

최단 경로에 대한 다이얼 알고리즘

양의 정수인 에지 가중치를 가진 지시 그래프의 최단 경로에 대한 Dijkstra 알고리즘에서 우선 순위는 단조로우며, ^[13]단조 버킷 대기열을 사용하여 O(m + dc)의 시간 바인딩을 얻을 수 있는데 여기서 m은 에지 수, d는 네트워크의 직경, c는 최대(정수) 링크 비용이다.^[9][14] Dijkstra 알고리즘의 이 변형은 Robert B 다음에 ^[9]Dial's 알고리즘으로도 알려져 있다. 1969년에 출판한 다이얼.^[7] 또한 최대 중량과 최소 중량의 비율이 최대 c일 때 실제 에지 무게가 양의 그래프에 대해 정량화된 버킷 대기열을 사용하여 동일한 아이디어를 사용할 수 있다.^[15] 이 알고리즘의 정량화된 버전에서 정점은 정량화되지 않은 우선 순위 대기열을 가진 결과와 비교하여 순서가 맞지 않게 처리되지만, 정확한 최단 경로는 여전히 발견된다.^[5] 이러한 알고리즘에서 우선 순위는 폭 c + 1의 범위에만 걸쳐 있으므로 모듈식 최적화를 사용하여 공간을 O(n + c)로 줄일 수 있다.^[8][14]

가장 광범위한 경로 문제에 동일한 알고리즘의 변형을 사용할 수 있다. 정수 우선 순위를 할당할 수 있는 하위 집합으로 비정수 에지 가중치를 신속하게 분할하는 방법과 결합하여, 가장 넓은 경로 문제의 단일 소스 단일 대상 버전에 대한 거의 선형 시간 솔루션으로 이어진다.^[16]

탐욕스러운 세트 커버

세트 커버 문제는 세트 패밀리를 입력하는 것과 같다. 출력물은 가능한 적은 세트를 포함하여 원래 패밀리와 동일한 결합을 가진 이들 세트의 하위 패밀리가 되어야 한다. NP-hard이지만 로그 근사비를 달성하는 탐욕스러운 근사 알고리즘을 가지고 있는데, P = NP가 아닌 한 기본적으로 최선이 된다.^[17] 이 근사 알고리즘은 가능한 최대 개수의 남은 덮개를 덮는 세트를 반복적으로 선택하여 하위 패밀리를 선택한다.^[18] 알고리즘 설계에서 표준 연습은 입력 크기에서 선형 시간이 걸리는 이 알고리즘의 구현을 요구하는데, 이는 모든 입력 세트의 크기 합이다.^[19]

이 문제는 입력 패밀리의 세트 버킷 대기열을 사용하여 해결할 수 있으며, 이 버킷 대기열에서 적용되는 나머지 요소의 수에 따라 우선순위가 결정된다. 탐욕스러운 알고리즘이 출력물의 일부로 세트를 선택할 때마다, 새로 포함된 세트 요소들은 그것들을 포함하는 다른 세트의 우선순위에서 빼야 한다; 알고리즘의 과정에서 이러한 우선순위의 변경의 수는 입력 세트의 크기의 합에 불과하다. 우선 순위는 단조롭게 감소하는 정수로, 커버할 요소의 수에 따라 상한을 둔다. 탐욕스러운 알고리즘의 각 선택에는 최대 우선 순위의 집합을 찾는 것이 포함되며, 이는 가장 최근의 이전 최대값에서 시작하여 버킷 대기열의 버킷을 통해 아래쪽으로 스캔함으로써 수행될 수 있다. 총 시간은 입력 크기로 선형이다.^[10]

스케줄링

버킷 대기열은 예를 들어 서비스 품질을 보증하는 인터넷 데이터의 패킷 포워딩과 같이 마감일이 있는 작업을 스케줄링하는 데 사용될 수 있다. 이 적용의 경우, 마감일은 별개의 간격으로 정량화해야 하며, 마감일이 동일한 간격으로 속하는 업무는 동등한 우선순위로 간주해야 한다.^[2]

계량화된 버킷 대기열 데이터 구조, 캘린더 대기열의 변화는 개별 이벤트 시뮬레이션 스케줄링에 적용되었으며, 여기서 대기열의 요소는 이벤트가 발생해야 하는 시뮬레이션 내의 시간에 따라 우선순위가 정해진다. 이 애플리케이션에서는 사건의 순서가 중요하므로 우선순위를 근사하게 추정할 수 없다. 따라서, 달력 대기열은 버킷 대기열과 다른 방식으로 최소 우선순위 요소에 대한 검색을 수행한다. 버킷 대기열에서 비어 있지 않은 첫 번째 버킷의 모든 요소를 반환할 수 있지만, 대신 달력 대기열은 해당 버킷의 모든 요소를 검색하여 가장 작은 우선 순위를 가진 요소를 결정한다. 이러한 검색을 빠르게 유지하기 위해 이러한 변동은 양적화 척도를 조정하고 데이터 구조가 균형을 벗어날 때 재구성함으로써 요소 수에 비례하는 버킷 수를 유지하려고 시도한다. 캘린더 대기열은 최악의 경우 버킷 대기열보다 느릴 수 있지만(많은 요소가 동일한 가장 작은 버킷에 모두 착륙할 경우) 요소들이 버킷 사이에 균일하게 분포되어 평균 버킷 크기가 일정하게 될 때 빠르다.^[20][21]

빠른행진

미분방정식의 해법에 대한 응용수학 및 수치법에서는, 파동 전파를 모형화하는 데 사용되는 에이콘 방정식의 경계값 문제 해결을 위한 빠른 행진법의 단계를 우선시하는 데 불필요한 우선순위 대기열이 이용되어 왔다. 이 방법은 Dijkstra 알고리즘의 연속 버전을 닮은 우선순위화 방법을 사용하여 이동 경계가 이산점 집합(정수 격자의 점 등)을 가로지르는 시간을 찾아내고, 그 실행 시간은 이러한 점의 우선순위 대기열에 의해 지배된다. 이 알고리즘에서 사용하는 우선순위를 정수로 반올림하고, 이러한 정수에 버킷 대기열을 사용하여 선형 시간까지 속도를 높일 수 있다. 디즈크스트라와 다이얼의 알고리즘에서처럼 우선순위는 단조로운 것이므로 빠른 행진은 버킷 대기열의 단조로운 최적화와 그 분석을 이용할 수 있다. 그러나, 탈바꿈은 결과 계산에 약간의 오류를 도입한다.^[4]

참고 항목

• 소프트 힙, 대략적인 우선 순위를 사용하여 우선 순위 대기열을 가속화하는 다른 방법

참조