Mateusz Mazurek – programista z pasją

Python, architektura, ciekawostki ze świata IT

    • Algorytmika Inżynieria oprogramowania Programowanie

    Kolejka priorytetowa z użyciem kopca

    Mateusz M. Opublikowane w
    🕑 6 minuty czytania

    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, dwa dokumenty PDF „6 (nie zawsze oczywistych) błędów popełnianych podczas nauki programowania” który jest jednym z efektów ponad siedmioletniej pracy i obserwacji rozwoju niejednego programisty oraz „Wstęp do testowania w Pythonie”, będący wprowadzeniem do biblioteki PyTest.
    Jeśli to Cię interesuje to zapraszam również na swoje social media.

    Jak i do ewentualnego postawienia mi kawy :)
    Postaw mi kawę na buycoffee.to

    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?

    Podobne artykuły:

    Otagowano:
    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ł?

    4
    Odpowiedz
    Mateusz M.

    W sumie to średni:) Tzn sam parametr może zostać, ale nie przypisywać go do zmiennej queue a na self.queue wykonać metodę extend i tym samym przelać elementy z parametru do wewnętrznej kolejki:)

    1
    Odpowiedz
    Mateusz M.

    O, albo użyć argsów:)

    0
    Odpowiedz
    Mateusz Rus

    Bardzo dobrze opisane zagadnienie Mateusz!
    Oby tak dalej :)

    Pozdrawiam.

    2
    Odpowiedz
    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.

    1
    Odpowiedz