Python的數據結構與算法之隊列詳解
模擬打印機任務隊列過程
計算機科學中也有眾多的隊列例子。比如計算機實驗室有10臺計算機，它們都與同一臺打印機相連。當學生需要打印的時候，他們的打印任務會進入一個隊列。該隊列中的第一個任務就是即將執行的打印任務。如果一個任務排在隊列的最後面，那麼它必須等到所有前面的任務都執行完畢後才能執行。
學生向共享打印機發送打印請求，這些打印任務被存在一個隊列中，並且按照先到先得的順序執行。這樣的設定可能導致很多問題。其中最重要的是，打印機能否處理一定量的工作。如果不能，學生可能會由於等待過長時間而錯過要上的課。
考慮計算機實驗室裡的這樣一個場景：在任何給定的一小時內，實驗室裡都有10個學生。他們在這 一小時內最多打印2次，並且打印的頁數從1到20頁不等。實驗室的打印機比較老舊，每分鐘隻能以低質量打印10頁。也可以將打印質量調高，但是這樣做會導致打印機每分鐘隻能打印5頁。降低打印速度可能導致學生等待過長時間。那麼，應該如何設置打印速度呢？
可以通過構建一個模型來解決該問題。我們需要為學生、打印任務和打印機構建對象。當學生提交打印任務時，我們需要將它們加入打印機的任務隊列中。當打印機執行完一個任務後，它會檢查該隊列，看看其中是否還有需要處理的任務。我們感興趣的是學生平均需要等待多久才能拿到打印好的文章。這個時間等於打印任務在隊列中的平均等待時間。
在模擬時，需要應用一些概率學知識。舉例來說，學生打印的文章可能有1~20頁。如果各頁數出現的概率相等，那麼打印任務的實際時長可以通過模擬1~20的一個文章頁數隨機數來計算得出。
如果實驗室裡有10個學生，並且在一小時內每個人都打印兩次，那麼每小時平均就有20個打印任務。 在任意一秒，創建一個打印請求的概率是多少？ 回答這個問題需要考慮任務與時間的比值。每小時20個任務相當於每180秒1個任務。
可以通過1~180的一個隨機數來模擬每秒內產生打印請求的概率(1/180的概率)。如果隨機數正好是180，那麼就認為有 一個打印請求被創建。註意，可能會出現多個請求接連被創建的情況，也可能很長一段時間內都沒有請求。這就是模擬的本質。我們希望在常用參數已知的情況下盡可能準確地模擬。
主要模擬步驟：
1.創建一個打印任務隊列。每一個任務到來時都會有一個時間戳。一開始，隊列是空的。
2.針對每一秒（currentSecond），執行以下操作。
- 是否有新創建的打印任務？如果是，以 currentSecond 作為其時間戳並將該任務加入到隊列中。
- 如果打印機空閑，並且有正在等待執行的任務，執行以下操作：
- 從隊列中取出第一個任務並提交給打印機；
- 用 currentSecond 減去該任務的時間戳，以此計算其等待時間；
- 將該任務的等待時間存入一個列表，用來作為計算平均等待時間的數據；
- 根據該任務的頁數，計算執行時間。
- 打印機進行一秒的打印，同時從該任務的執行時間中減去一秒。
- 如果打印任務執行完畢，即任務的執行時間減為0，則說明打印機回到空閑狀態。
3.當模擬完成之後，根據等待時間列表中的值計算平均等待時間。
構建隊列程序
class Queue:
def __init__(self):
self.items = [] # 構建空隊列
def isEmpty(self):
return self.items ==[] # 判斷是否為空
def enqueue(self,item):
self.items.insert(0, item) # 在隊列尾部(列表左端)插入元素
def dequeue(self):
return self.items.pop() # 在隊列頭部(列表右端)移出元素
def size(self):
return len(self.items) # 隊列(列表)長度
模擬打印程序
import random
# 模擬打印機
class Printer:
# 打印機初始化
def __init__(self, ppm):
self.pagerate = ppm # 打印速度 頁/分鐘
self.currentTask = None # 現有任務
self.timeRemain = 0 # 該任務所需時間
# 打印任務倒計時 0代表打印完成
def tick(self):
# 如果打印機正在執行任務
if self.currentTask != None:
# 該任務執行時間 = 執行時間 - 1（執行時間倒計時）
self.timeRemaining = self.timeRemaining - 1
if self.timeRemaining <= 0: # 該任務執行時間 <= 0
self.currentTask = None # 該任務執行完畢
# 判斷打印機是否空閑
def busy(self):
if self.currentTask != None:
return True
else:
return False
# 打印機接受新任務
def startNext(self, newtask):
self.currentTask = newtask
# 新打印任務需要時間 = 新任務頁數 * (60 / 每分鐘打印多少頁的速度)
# (60 / 每分鐘打印多少頁的速度) = 每打印一頁所需要的秒數
self.timeRemaining = newtask.getPages() * (60 / self.pagerate)
# 模擬單個任務的屬性
class Task:
# 任務初始化
def __init__(self, time):
self.timestamp = time # 創建任務的時間點
self.pages = random.randrange(1, 21) # 任務頁數 在 1~20 間隨機生成
def getStamp(self):
return self.timestamp # 獲取任務創建的時間點
def getPages(self):
return self.pages # 獲取任務的頁數
def waitTime(self, currenttime):
# 任務的等待時間 = 當前時間 - 任務創建的時間點
return currenttime - self.timestamp
# 模擬學生創建的新打印請求
def newPrintTask():
# 打印請求是一個隨機事件
# 通過1~180之間的一個隨機數來模擬每秒內產生打印請求的概率
# 如果隨機數正好是180，那麼就認為有一個打印請求被創建。
num = random.randrange(1, 181)
if num == 180:
return True
else:
return False
# 模擬打印過程
def simulation(numSeconds, pagesPerMinute):
labprinter = Printer(pagesPerMinute)
printQueue = Queue()
waitingtimes = []
for currentSecond in range(numSeconds):
if newPrintTask():
task = Task(currentSecond)
printQueue.enqueue(task)
if(not labprinter.busy())and(not printQueue.isEmpty()):
nexttask = printQueue.dequeue()
waitingtimes.append(nexttask.waitTime(currentSecond))
labprinter.startNext(nexttask)
labprinter.tick()
averageWait = sum(waitingtimes)/len(waitingtimes)
print("平均等待 %6.2f 秒，還有 %3d 個任務等待處理"
% (averageWait, printQueue.size()))
模擬打印過程（有註釋）
def simulation(numSeconds, pagesPerMinute):
# numSeconds-時間段
# pagesPerMinute-打印速度，頁/分鐘
labprinter = Printer(pagesPerMinute) # 創建打印機
printQueue = Queue() # 創建打印機任務隊列
waitingtimes = [] # 創建等待時間數據樣本列表
for currentSecond in range(numSeconds): # 一次循環代表一秒
if newPrintTask(): # 如果 有打印請求創建
task = Task(currentSecond) # 創建打印任務並記錄當前時間點
printQueue.enqueue(task) # 打印任務進入打印機任務隊列
# 如果 打印機空閑 並且 打印機任務隊列有任務
if(not labprinter.busy())and(not printQueue.isEmpty()):
nexttask = printQueue.dequeue() # 從隊列取出新任務
# 根據當前時間點計算新任務在任務隊列裡的等待時間 並將等待時間記錄進樣本列表
waitingtimes.append(nexttask.waitTime(currentSecond))
labprinter.startNext(nexttask) # 開始執行新任務 打印機進入忙碌狀態
labprinter.tick() # 每循環一次 當前打印任務執行倒計時減少一秒
averageWait = sum(waitingtimes)/len(waitingtimes)
print("平均等待 %6.2f 秒，還有 %3d 個任務等待處理" % (averageWait, printQueue.size()))
需要註意的是，時間戳是我們根據循環模擬出來的，我們給定瞭 numSeconds 時間段後，每循環一次相當於時間過瞭一秒。
雖然每次模擬的結果不一定相同。但對此我們不需要在意。這是由於隨機數的本質導致的。我們感興趣的是當參數改變時結果出現的趨勢。
下面是一些結果：
我們根據模擬得到瞭打印機在兩種速度下，一小時內的任務執行情況的參考數據。可以很明顯的看到，當打印質量提升後，學生平均等待時間相比低質量情況下顯著增加，並且任務處理未完成的次數也出現瞭增加，所以設置打印機為低質量模式是最合適的。
總結
本篇文章就到這裡瞭，希望能夠給你帶來幫助，也希望您能夠多多關註WalkonNet的更多內容!