대기열은 어떻게 파이썬에서 작동합니까?

Question

는 파이썬 물건을 배우려고 노력하고, 누군가는 우선 순위 큐를 사용하는 몇 가지 예를 도와 줄 수 있는지 궁금 해서요. 나는 자바에서 그들이 어떻게 작동하는지 알지만, 파이썬에서 어떻게 작동하는지 명확한 예제를 보는 것 같다. http://docs.python.org/2/library/queue.html하지만 그들을 통해 반복, 그들을 정렬, 최소, 최대를 받고 조직, 팝, 대기열에 추가의 예를 표시하지 않습니다 : 내가 본 큐의 크기를 점점처럼 .qsize() 여기에서이다. 누군가가 내게 이런 예를 들어 주거나 ​​이것을 배울 수있는 올바른 방향으로 나를 가리키면 정말 고맙겠습니다. Queue 모듈

Answer 1

큐는 주로 멀티 스레딩의 생산자/소비자 패턴의 구현 위해 개발된다. 범용 우선 순위 대기열 데이터 구조에 관심이 있다면 use the heapq module.

Answer 2

Queue 당신이 찾고 우선 순위 큐가 아닙니다. 대신 파이썬 list에서 작동하는 heapq을 찾고 있습니다.

힙은 모든 부모 노드가 자식의보다 작거나 같은 값을 갖고있는 이진 트리 위치 : 표시됩니다 빈리스트 ([]) 또는 heapify 기존 하나를 사용 할 수 있습니다. 이 구현은 0에서 요소를 계산, 모든 k에 대한 heap[k] <= heap[2*k+1] 및 heap[k] <= heap[2*k+2]에 대한 배열을 사용합니다.

이 속성은 불변 힙로 알려져 있습니다. 한 가지주의해야 할 점은 정렬 된 목록은이 경우 힙으로 이미 유효하다는 것입니다 (모든 항목이 올바른 이웃보다 적기 때문에 쉽게 이해할 수 있습니다). 또한 힙이 균형을 이루고 루트에서 모든 리프 노드의 높이 사이에 최대 차이가 1이되도록 보장됩니다.이 점은 나중에 입증 될 것입니다. 목록이 정렬되지 않았거나 이미 힙이 아닌 경우 유효한 힙을 얻으려면 heapq.heapify을 호출해야합니다. 이 작업은 선형 시간 (O(N) 시간)에서 작동

  1 
     / \ 
     3  2 
    / \ 
    9  10 

처럼 힙으로

>>> import heapq 
>>> L = [2, 3, 1, 9, 10] 
>>> heapq.heapify(L) 
>>> L 
[1, 3, 2, 9, 10] 

이 이제 보인다. 보시다시피, 가장 작은 항목은 항상 목록의 0th 색인입니다. 간단하게 검색 할 수 있습니다 :

>>> L[0] 
1 

가장 큰 항목은 여기에서 선택하지 마십시오. 이 경우 당신은 n=1 항목 heapq.nlargest을 사용할 수 있습니다

>>> heapq.nlargest(1, L) 
[10] 

는 힙 떨어져 작은 항목을 나타납니다 heapq.heappop()를 사용할 수있는 힙에서 항목을 팝업.

>>> heapq.heappop(L) 
1 

처럼이 보이는 수행하는 코드 :

def heappop(heap): 
    """Pop the smallest item off the heap, maintaining the heap invariant.""" 
    lastelt = heap.pop() # raises appropriate IndexError if heap is empty 
    if heap: 
     returnitem = heap[0] 
     heap[0] = lastelt 
     _siftup(heap, 0) 
    else: 
     returnitem = lastelt 
    return returnitem 

어떤이가하는 것입니다 것은 0th 요소를 반환합니다. 그러나 먼저 힙의 마지막 항목 (heap.pop()은 목록에서 heap[-1]을 제거함)과 첫 번째 항목 (heap[0] = lastelt)을 서로 바꿉니다. heapq 모듈의 숨겨진 함수 _siftup을 호출하여 힙 불변성을 유지해야합니다.과학적인 목적을 위해, 여기에 수행하는 코드입니다 (heapq가 빠른 C 코드 구현을 사용하지만 의미 해당되는 그 전에 파이썬 구현했다) : 그것은 기본적으로는 작은 아이의와 부모를 교환 유지

def _siftup(heap, pos): 
    endpos = len(heap) 
    startpos = pos 
    newitem = heap[pos] 
    # Bubble up the smaller child until hitting a leaf. 
    childpos = 2*pos + 1 # leftmost child position 
    while childpos < endpos: 
     # Set childpos to index of smaller child. 
     rightpos = childpos + 1 
     if rightpos < endpos and not cmp_lt(heap[childpos], heap[rightpos]): 
      childpos = rightpos 
     # Move the smaller child up. 
     heap[pos] = heap[childpos] 
     pos = childpos 
     childpos = 2*pos + 1 
    # The leaf at pos is empty now. Put newitem there, and bubble it up 
    # to its final resting place (by sifting its parents down). 
    heap[pos] = newitem 
    _siftdown(heap, startpos, pos) 

을 . 이 작업은 O(log n) 시간이 걸리며, log n은 균형 이진 트리의 높이입니다. 힙 사용에 항목을 추가하려면 : O(log n) 시간이 소요

>>> heapq.heappush(L, 7) 
>>> L 
[3, 7, 10, 9] 

합니다. 먼저 새로운 노드를 목록의 끝에 추가합니다. 즉, h, 새로운 노드의 인덱스는 2*k + 1 또는 2*k + 2이고, (2*k + 1)이라고 가정 해 봅시다. 일부 노드는 k이고 높이는 h - 1입니다. 따라서 다른 항목을 추가하면 인덱스는 2*k + 2이되고 그 다음 동일한 인덱스의 하위 노드는 마지막 노드 오른쪽의 다른 노드의 왼쪽 자식을 높이 h - 1, 즉 트리가 항상 균형.

def _siftdown(heap, startpos, pos): 
    newitem = heap[pos] 
    # Follow the path to the root, moving parents down until finding a place 
    # newitem fits. 
    while pos > startpos: 
     parentpos = (pos - 1) >> 1 
     parent = heap[parentpos] 
     if cmp_lt(newitem, parent): 
      heap[pos] = parent 
      pos = parentpos 
      continue 
     break 
    heap[pos] = newitem 

하는 기본적으로 지속적으로 검사 : 당신은 결국 계속 추가 할 경우는이처럼 보이는 heapq 모듈의 _siftdown 숨겨진 함수를 호출 어쨌든 다음 등

을 해당 행을 작성하고 새로 만듭니다 만약 그 아이가 부모보다 작 으면, 그 아이는 그 둘을 서로 바꿉니다. 균형 잡힌 2 진 트리이므로 트리의 높이는 O(log n)이고 log n은 힙 불변성을 유지하기 위해 잠재적으로 스왑되어야하는 부모의 양입니다. 당신이 heapq을 정렬 할 경우

, 당신은 단지 반복 큐에 heappop를 호출하는 힙 정렬과 함께 시간 O(N log N) 정렬 최적의에서이 작업을 수행 할 수 있습니다 물론 파이썬의 내장 sorted의

[heappop(L) for i in range(len(L))] 

훨씬 더 최적화 된 비록 당신이 파이썬을 사용하지 않고 그냥 C에 힙을 구현한다고해도,이 코드보다 더 빨리 수행 할 것입니다. 마지막으로 힙을 반복하는 것은 쉽습니다, 그냥 목록을 통해 반복 : 나는 감히하지만

for x in L: 
    print x 

이 어떤 것이 순서되지 않습니다.

Answer 3

PriorityQueue를 사용할 수 있습니다. 다음은 그 예입니다.

In [1]: from Queue import PriorityQueue 
In [2]: pq = PriorityQueue() 
In [3]: pq.put((1, "girl")) # put data in the form of tuple (priority, data) 
In [4]: pq.put((3, "forest")) 
In [5]: pq.put((2, "rain")) 
In [6]: pq.get()    # retrieves data. lowest priority number first. 
Out[6]: (1, 'girl') 
In [7]: pq.empty()    # checks if empty 
Out[7]: False 
In [8]: pq.full()    # checks if full 
Out[8]: False 
In [9]: pq.qsize()    # current size of the queue. 
Out[9]: 2 

또한 PriorityQueue 클래스를 확장하고 사물을 사용자 정의 할 수 있습니다.