G. Jagiella | ostatnia modyfikacja: 10.03.2021 |
Kolejka - struktura danych podobna do stosu, gdzie obiekty są ułożone "jeden za drugim". Obsługuje co najmniej dwie operacje:
enqueue(x) - dokłada obiekt x na koniec kolejki.dequeue() - ściąga element z początku kolejki i zwraca go.enqueue(x) i dequeue() są odpowiednikami (odpowiednio) stosowych operacji push(x) i pop(). Kolejka dla wygody może obsługiwać też inne operacje (np. size(), is_empty(), peek()).
Naturalnym "życiowym" odpowiednikiem kolejki jest kolejka w sklepie. Przykładowa, nieoptymalna implementacja kolejki znajduje się w pliku my_queue.py w materiałach do wykładu.
W kręgu stoi pewna ilość osób. Ustalamy $n$. Zaczynając od pierwszej osoby, odliczamy $n$ kolejnych osób (w ustalonym kierunku, np. zgodnie z ruchem wskazówek zegara) i usuwamy następną z kręgu. Następnie powtarzamy proces zaczynając odliczanie od następnej osoby, aż zostanie tylko jedna.
Przykład (niebieski - od kogo zaczynamy odliczanie, czerwony - usunięta osoba), $n = 3$:
Adam Barbara Cezary Dariusz Ewelina Franciszka
Adam Barbara Cezary Ewelina Franciszka
Adam Cezary Ewelina Franciszka
Cezary Ewelina Franciszka
Ewelina Franciszka
Ewelina
Bardziej algorytmicznie: ustawmy osoby w kolece. "Odliczenie" osoby polega na wyciągnięciu osoby z początku kolejki i ustawienie jej na końcu. Po odliczeniu $n$ osób, usuwamy pierwszą osobę z kolejki.
from my_queue import Queue
# Usuwa co n-tą osobę.
def wyliczanka(osoby, n): # osoby - lista osób
queue = Queue()
for osoba in osoby:
queue.enqueue(osoba)
while queue.size() > 1:
# cyklicznie przesuwamy osoby w kolejce
for i in range(n):
queue.enqueue(queue.dequeue())
# usuwamy n-tą osobę
queue.dequeue()
return queue.dequeue()
print(wyliczanka(["Adam", "Barbara", "Cezary", "Dariusz", "Ewelina", "Franciszka"], 3))
print(wyliczanka(["Adam", "Barbara", "Cezary", "Dariusz", "Ewelina", "Franciszka"], 2))
Ewelina Adam
Rozważmy myjnię samochodową. Do myjni przyjeżdzają brudne samochody, wymagające mycia przez pewną ilość minut. Gdy samochód przyjeżdza, a myjnia jest wolna, samochód zajmie ją na stosowną ilość minut. W przeciwnym wypadku stanie w kolejce. Gdy myjnia zwalnia się, zajmuje je pierwszy samochód w kolejce.
Nasz cel to zasymulowanie takiego procesu i zbadanie, ile wynosi średni czas oczekiwania samochodu na wolne stanowisko.
Bardziej algorytmicznie: naszą symulację będziemy prowadzić w jednominutowych odstępach. Na początku myjnia jest wolna, a kolejka samochodów jest pusta. Tworzymy następujące klasy:
Car - reprezentuje samochód. Gdy jest tworzony, posiada pewną ilość "brudu" (losowa liczba całkowita z przedziału [1, 5]), czyli ilości minut, potrzebnych do umycia samochodu. Pamięta także czas, w którym został stworzony (będzie to czas, w którym przyjechał do myjni).
CarWash - reprezentuje myjnię. Myjnia jest wolna lub zawiera aktualnie myty samochód.
Myjnia (opis bez szczegółów implementacji)
Parametrami symulacji są: liczba minut $n$, oraz szansa $r \in [0, 1]$ na to, że w danej minucie przyjedzie samochód.
Symulację prowadzimy w odstępach jednej minuty przez $n$ minut. W każdej minucie wykonujemy kolejne kroki:
- Najpierw losujemy, czy przyjechał samochód (z szansą $r$). Jeśli tak, kładziemy go do kolejki.
- Jeśli myjnia jest pusta, a w kolejce stoją samochody: usuwamy samochód z kolejki i kładziemy go do myjni.
- Myjnia, jeśli nie jest pusta, dokonuje jednominutowego mycia samochodu.
Następnie algorytm możemy modyfikować: jeśli każdy samochód nowuje czas, w jakim stanął w kolejce, możemy sprawdzić czas oczekiwania na mycia w momencie, gdy wkładamy samochód do myjni w kroku 2). Na zakończenie symulacji, możemy wyciągnąć średnią tych czasów.
Kody klas Car i CarWash:
import random
class Car:
def __init__(self, timestamp):
self.timestamp = timestamp
self.dirt = random.randrange(1, 6)
def wash(self):
self.dirt -= 1
def is_clean(self):
return self.dirt <= 0
def get_dirt(self):
return self.dirt
def waiting_time(self, current_time):
return current_time - self.timestamp
class CarWash:
def __init__(self):
self.current_car = None
def tick(self):
if self.current_car is None:
return
self.current_car.wash()
if self.current_car.is_clean():
self.current_car = None
def busy(self):
return self.current_car is not None
def __str__(self):
if not self.busy():
return "Car wash: idle"
return "Car wash: cleaning car, {} dirt remaining".format(self.current_car.get_dirt())
def start_next(self, new_car):
self.current_car = new_car
Oraz kod samej symulacji:
import random
from my_queue import Queue
# ! Odkomentowac poza notebookiem:
# from car import Car
# from carwash import CarWash
def simulate_car_wash(num_minutes, chance):
car_wash = CarWash()
queue = Queue()
total_time = 0
total_cars = 0
for cur_minute in range(num_minutes):
if random.random() < chance:
new_car = Car(cur_minute)
queue.enqueue(new_car)
print('queued a new car with {} dirt'.format(new_car.get_dirt()))
if not car_wash.busy() and not queue.is_empty():
new_car = queue.dequeue()
car_wash.start_next(new_car)
total_cars += 1
total_time += new_car.waiting_time(cur_minute)
print('started to wash a car with {} dirt'.format(new_car.get_dirt()))
print("Time: {} minutes, queued cars: {}".format(cur_minute, queue.size()))
print(str(car_wash))
car_wash.tick()
print("avg waiting time: {} m".format(total_time / total_cars))
simulate_car_wash(30, 0.2)
Time: 0 minutes, queued cars: 0 Car wash: idle Time: 1 minutes, queued cars: 0 Car wash: idle Time: 2 minutes, queued cars: 0 Car wash: idle Time: 3 minutes, queued cars: 0 Car wash: idle queued a new car with 3 dirt started to wash a car with 3 dirt Time: 4 minutes, queued cars: 0 Car wash: cleaning car, 3 dirt remaining Time: 5 minutes, queued cars: 0 Car wash: cleaning car, 2 dirt remaining queued a new car with 3 dirt Time: 6 minutes, queued cars: 1 Car wash: cleaning car, 1 dirt remaining started to wash a car with 3 dirt Time: 7 minutes, queued cars: 0 Car wash: cleaning car, 3 dirt remaining Time: 8 minutes, queued cars: 0 Car wash: cleaning car, 2 dirt remaining Time: 9 minutes, queued cars: 0 Car wash: cleaning car, 1 dirt remaining queued a new car with 3 dirt started to wash a car with 3 dirt Time: 10 minutes, queued cars: 0 Car wash: cleaning car, 3 dirt remaining Time: 11 minutes, queued cars: 0 Car wash: cleaning car, 2 dirt remaining queued a new car with 4 dirt Time: 12 minutes, queued cars: 1 Car wash: cleaning car, 1 dirt remaining started to wash a car with 4 dirt Time: 13 minutes, queued cars: 0 Car wash: cleaning car, 4 dirt remaining Time: 14 minutes, queued cars: 0 Car wash: cleaning car, 3 dirt remaining queued a new car with 3 dirt Time: 15 minutes, queued cars: 1 Car wash: cleaning car, 2 dirt remaining Time: 16 minutes, queued cars: 1 Car wash: cleaning car, 1 dirt remaining started to wash a car with 3 dirt Time: 17 minutes, queued cars: 0 Car wash: cleaning car, 3 dirt remaining Time: 18 minutes, queued cars: 0 Car wash: cleaning car, 2 dirt remaining Time: 19 minutes, queued cars: 0 Car wash: cleaning car, 1 dirt remaining Time: 20 minutes, queued cars: 0 Car wash: idle Time: 21 minutes, queued cars: 0 Car wash: idle Time: 22 minutes, queued cars: 0 Car wash: idle Time: 23 minutes, queued cars: 0 Car wash: idle Time: 24 minutes, queued cars: 0 Car wash: idle Time: 25 minutes, queued cars: 0 Car wash: idle queued a new car with 2 dirt started to wash a car with 2 dirt Time: 26 minutes, queued cars: 0 Car wash: cleaning car, 2 dirt remaining Time: 27 minutes, queued cars: 0 Car wash: cleaning car, 1 dirt remaining queued a new car with 1 dirt started to wash a car with 1 dirt Time: 28 minutes, queued cars: 0 Car wash: cleaning car, 1 dirt remaining Time: 29 minutes, queued cars: 0 Car wash: idle avg waiting time: 0.5714285714285714 m
Pytanie: dla jakiego parametru $r$ należy spodziewać się, że kolejka będzie rosnąć (tj. myjnia jest przepełniona)?
Myjnia myje "minutę brudu na minutę", a brudu pojawia się średnio $3r$ na minutę, zatem można spodziewać się, żę krytyczną wartością $r$ jest $1/3$.
Możliwe ulepszenia kodu: więcej myjni (stanowisk myjących) obsługujących tę samą kolejkę? Różna wydajność tych myjni? Wybór rozdzielczości symulacji (np. sekunda zamiast minuty)?