fbpx

Mateusz Mazurek – programista z pasją

Czyli o użyciu Pythona i kilku innych technologii do tworzenia świetnej jakości aplikacji w oparciu o stabilny proces dostarczania oprogramowania.

Algorytmika Inżynieria oprogramowania Programowanie

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”.


Czekaj, stop!

Podoba Ci się to co tworzę? Jeśli tak to zapraszam Cię do zapisania się na newsletter:
a w ramach prezentu otrzymasz całkowicie za darmo, dokument PDF „6 (nie zawsze oczywistych) błędów popełnianych podczas nauki programowania” który jest jednym z efektów ponad siedmioletniej pracy oraz obserwacji rozwoju niejednego programisty.Jeśli to Cię interesuje to zapraszam również na swoje social media.

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

A może wolisz nowości na mail?

0 0 głos
Oceń artykuł:)
Subskrybuj
Powiadom o
guest

Witryna wykorzystuje Akismet, aby ograniczyć spam. Dowiedz się więcej jak przetwarzane są dane komentarzy.

5 komentarzy
Inline Feedbacks
View all comments
Filip

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

Mateusz Rus

Bardzo dobrze opisane zagadnienie Mateusz!
Oby tak dalej :)

Pozdrawiam.

Mateusz Hyla

Nie jest to tak bardzo proste do zrozumienia. Kolejkę w zasadzie prosto zrozumieć ale nie do końca czaje kopiec czy implementacje kolejki priorytetowej na podstawie kopca. Nie mniej jednak jest to dobry artykuł.

Pozdrawiam.

Halo, halo, czekaj chwilę, nie zamykaj!

Super się cieszę że tu jesteś! Bloga tego prowadzę już jakiś czas, uwielbiam pisać i dzielić się wiedzą ale moja pasja do tego jest bez sensu jeśli nie mam czytelników :(

W tej chwili chciałbym Cię zaprosić do zapisania się na newsletter i bycia na bieżąco z tym co przygotowuję. W zamiana za okazane zaufanie dostaniesz dostęp do dokumentu PDF

6(nie zawsze oczywistych) błędów popełnianych podczas nauki programowania”

całkowicie ZA DARMO – wiem, szok i niedowierzanie że daje coś za darmo. Ale ja serio lubię się dzielić wiedzą! Zostaw po prostu swój mail tu – link do zapisania się.