Kolejka priorytetowa z użyciem kopca

Temat kolejek to temat który w Informatyce jest wiecznie żywy. Gwarantuję Ci że każdy większy projekt ma jakąś kolejkę a pewnie ma ich kilka czy kilkanaście. Powodem takiej popularności jest oczywiście sam sposób jej działania, ponieważ kolejkowanie zadań leży u podstaw efektywnego przetwarzania informacji.

Czym jest kolejka?

Kolejka to bufor który przechowuje jakieś dane. W tym wpisie zajmiemy się kolejką typu FIFO czy First In First Out. Działa ona, tak jak rozwinięcie skrótu wskazuje, dokładnie tak jak kolejka w sklepie – ten który ostatni wejdzie do sklepu i stanie w kolejce zostanie obsłużony ostatni.

Znalezione obrazy dla zapytania queue
Bufor typu FIFO – kolejka

A chcąc pokazać to bardziej informatycznie można by użyć np. takiego schematu:

Znalezione obrazy dla zapytania queue

Wskazuje on że kolejka ma dwie metody enqueue która dodaje elementy i dequeue która te elementy z niej usuwa. Zauważ że nie istnieje funkcja która pozwala wyciągnąć elementy ze środka kolejki!

Kolejka w Pythonie

Najprostszą i zazwyczaj wystarczającą implementacją kolejki w Pythonie jest… Lista.

Mogłaby ona wyglądać np. tak:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Queue:
    def __init__(self):
        self._queue = []

    def enqueue(self, element):
        self._queue.insert(0, element)
        return self

    def dequeue(self):
        return self._queue.pop()

    def __len__(self):
        return len(self._queue)


q = Queue()
q.enqueue(1).enqueue(2).enqueue(3).enqueue(4)

while q:
    print(q.dequeue())

Czyli metodą enqueue dodajemy na początek kolejki i metodą dequeue usuwamy z kolejki. Efekt tego programu to wypisanie liczb 1, 2, 3 i 4 – ponieważ w takiej kolejności one weszły do kolejki – zgodnie z kolejnością wykonywania metod enqueue.

To o czym warto tutaj wspomnieć to przeciążenie funkcji __len__ – pozwala ona na dostosowanie interfejsu naszej klasy do wymogów pętli while – dzięki tej funkcji owa pętla będzie wiedzieć kiedy kolejka będzie pusta. Sprawdź sam – usuń definicję __len__ a zobaczyć że dostaniesz Exception mówiący o tym że próbujesz robić pop() na pustej liście.

Wydajność listy jako kolejki

Wpis byłby mocno niekompletny gdybym nie wspomniał o słabościach tworzenia kolejki na listach. Problemem list a dokładniej metody insert(index, element) jest jej złożoność obliczeniowa.

Znacznie lepszy podejściem jest użycie obiektu deque.

I żeby nie być gołosłownym, zmierzmy to.

1
2
3
4
from timeit import timeit

print(timeit('s.appendleft(37)', 'import collections; s = collections.deque()', number=100000))
print(timeit('s.insert(0,37)', 's = []', number=100000))

Dla jasności – zmierzymy tu ile trwa wykonanie się metody appendLeft która należy do obiektu deque i porównamy wynik z tym ile trwa operacja robiąca dokładnie to samo czyli insert. W każdym przypadku dodajemy do kolejki liczbę 37 i proces dodawania powtarzamy 100000 razy.

Wynik jest zaskakujący:

0.006844676099717617 # dla deque
2.0261281218845397 # dla list

Pozwolę sobie zostawić Cię tu z wnioskami :)

Kolejka priorytetowa

Wróćmy do naszej kolejki w sklepie. Co się stanie jeśli sklep wprowadzi usługę premium która pozwala osobom które ją posiadają na wchodzenie do środka kolejki? No takiej rzeczy nasza kolejka nie umie. W aktualnej formie możemy dodawać elementy od „lewej” i odbierać „od prawej”.

Kolejka priorytetowa jako struktura danych pozwala właśnie na to by kolejność elementu w niej nie była zależna od kolejności ich napływania ale od ich priorytetu!

Zaimplementujemy sobie ją w Pythonie, ale pierw…

Czym jest kopiec?

Kopiec to drzewiasta struktura danych.

Kopiec to takie drzewo binarne w którym:

  • Wartość w każdym węźle jest nie mniejsza/nie większa niż u jego potomków.
  • Wszystkie liście leżą na co najwyżej dwóch sąsiednich poziomach.
  • Liście na ostatnim poziomie szczelnie wypełniają lewą część drzewa.

Więc kopiec mógłby wyglądać tak:

Znalezione obrazy dla zapytania kopiec algorytm
Przykład kopca.

I teraz tak, jeśli zamienilibyśmy cyfrę 1 na powiedzmy 8 to to drzewo przestanie być kopcem ponieważ straci właściwość kopca mówiącą że wartość w każdym węźle nie jest mniejsza niż u jego potomków.

Można to zobaczyć tez na listach, listy z kopców tworzy się przeszukując je wszerz:

[0, 1, 4, 7, 5, 8]  # kopiec zgodny z rysunkiem
[0, 8, 4, 7, 5, 8]  # kopiec z podmienioną wartością 1->8
[0, 5, 4, 7, 8, 8]  # przywrócona właściwość kopca

I efekt taki jest wynikiem takiego kodu:

1
2
3
4
5
6
7
8
9
10
11
heap = [0, 1, 4, 7, 5, 8]
from heapq import heapify

heapify(heap)
print(heap)

heap[1] = 8

print(heap)
heapify(heap)
print(heap)

Zauważ że właściwość kopca tutaj przywróciłem za pomocą funkcji heapify która pochodzi w modułu heapq który właśnie dostarcza nam możliwość pracy z kopcami – tj możliwość dodawania elementów, usuwania elementów i właśnie przywracania własności kopca.

Kolejka priorytetowa z użyciem kopca

Skoro mamy wszystkie puzzle – stwórzmy nasz big picture!

Pierw klasa która będzie elementem kolejki:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class QueueItem:
    def __init__(self, name, priority):
        self.name = name
        self._priority = priority
        self.queue = None

    @property
    def priority(self):
        return self._priority

    @priority.setter
    def priority(self, priority):
        self._priority = priority
        self.queue.rebuild_queue()

    def set_queue(self, queue):
        self.queue = queue

    def __int__(self):
        return self.priority

    def __lt__(self, other):
        return self._priority < other.priority

    def __str__(self):
        return self.name

To co tu jest ważnego – to definicja __int__ oraz __lt__ – pozwalają one na to by nasza klasa była poprawnie obsługiwana jako element kopca – a dokładnie by mogła być porównywana po priorytecie. Zauważ że mamy również getter i setter na polu priority – pozwala to nam w przypadku zmiany priorytetu od razu powiadomić o tym kolejkę – zmiana priorytetu spowoduje że nasz kopiec straci swoją własność a więc trzeba go przebudować.

Skoro mamy już element to teraz właściwa kolejka:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class PriorityQueue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item: QueueItem):
        heappush(self.queue, item)
        item.set_queue(self)
        return self

    def rebuild_queue(self):
        heapify(self.queue)

    def dequeue(self):
        return heappop(self.queue)

    def __iter__(self):
        return iter(self.queue)

    def __len__(self):
        return len(self.queue)


a = QueueItem("First", 10)
b = QueueItem("Second", 4)
c = QueueItem("Third", 11)

q = PriorityQueue()
q.enqueue(a).enqueue(b).enqueue(c)

while q:
    print(q.dequeue())

Mamy tu użyte funkcje dodające do kopca i usuwające z niego – czyli heappush oraz heappop – one już same w sobie zapewniają że kopiec pozostanie kopcem – czyli zachowują własności kopca.

I teraz tak – jeśli by nasza kolejka nie była priorytetowa to wynik programu byłby jasny: First, Second, Third.

Natomiast teraz mamy priorytety – najmniejsza liczba określa najwyższy priorytet, więc wynik programu będzie:

Second, First, Third

Jeśli już po dodaniu elementu kolejki zmienimy mu priorytet jak np. tu:

1
2
3
4
5
6
7
8
9
10
11
a = QueueItem("First", 10)
b = QueueItem("Second", 4)
c = QueueItem("Third", 11)

q = PriorityQueue()
q.enqueue(a).enqueue(b).enqueue(c)

c.priority = 0

while q:
    print(q.dequeue())

To dzięki użyciu settera i metody rebuild_queue kopiec zostanie ponownie przeanalizowany pod względem zachowania własności a efekt programu będzie przewidywalny:

Third, Second, First

Zmierzając do brzegu

Użycie kopca do implementacji kolejki priorytetowej to standardowy zabieg pozwalający poprawić złożoność obliczeniową tej struktury danych.

W artykule mamy przykład kolejki typu „min” – pobieramy wartości są najmniejsze, można to łatwo zmienić po prostu zmieniając sposób porównywania elementów.

Dzięki za wizytę,
Mateusz Mazurek
Podziel się na:
    Facebook email PDF Wykop Twitter

3
Dodaj komentarz

avatar
1 Wątki
2 Odpowiedzi
0 Śledzący
 
Komentarz z największą liczbą reakcji
Najczęściej komentowany wątek
2 Komentarze autora
Mateusz M.Filip Ostatnie komentarze autora

This site uses Akismet to reduce spam. Learn how your comment data is processed.

  Subskrybuj  
Powiadom o
Filip
Gość
Filip

Czy lista jako parametr domyślny w pierwszym fragmencie kodu to dobry pomysł?