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.
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.
A chcąc pokazać to bardziej informatycznie można by użyć np. takiego schematu:
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!
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.
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 :)
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…
Kopiec to drzewiasta struktura danych.
Kopiec to takie drzewo binarne w którym:
Więc kopiec mógłby wyglądać tak:
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.
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
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.
Ostatnio tygodnie były tak bardzo wypełnione, że nie udało mi się napisać nawet krótkiego podsumowanie. Więc dziś zbiorczo podsumuję luty… Read More
Zapraszam na krótkie podsumowanie miesiąca. Książki W styczniu przeczytałem "Homo Deus: Historia jutra". Książka łudząco podoba do wcześniejszej książki tego… Read More
Cześć! Zapraszam na podsumowanie roku 2023. Książki Zacznijmy od książek. W tym roku cel 35 książek nie został osiągnięty. Niemniej… Read More
Zapraszam na krótkie podsumowanie miesiąca. Książki W grudniu skończyłem czytać Mein Kampf. Nudna książka. Ciekawsze fragmenty można by było streścić… Read More
Cześć, ostatnio w Internecie pojawiło się dużo artykułów, które nie były przychylne pracy zdalnej. Z drugiej strony większość komentarzy pod… Read More
Zapraszam na krótkie podsumowanie miesiąca. Książki W listopadzie dokończyłem cykl "Z mgły zrodzony" Sandersona. Tylko "Stop prawa" mi nie do… Read More
Pokaż komentarze
Czy lista jako parametr domyślny w pierwszym fragmencie kodu to dobry pomysł?
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:)
O, albo użyć argsów:)
Bardzo dobrze opisane zagadnienie Mateusz!
Oby tak dalej :)
Pozdrawiam.
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.