python實(shí)現(xiàn)隊(duì)列的代碼回顧
class Queue():
# Queue() 創(chuàng)建一個空的新隊(duì)列。 它不需要參數(shù)，并返回一個空隊(duì)列。
def __init__(self):
self.items = []
# enqueue(item) 將新項(xiàng)添加到隊(duì)尾。 它需要 item 作為參數(shù)，并不返回任何內(nèi)容。
def enqueue(self, item):
self.items.insert(0, item)
# dequeue() 從隊(duì)首移除項(xiàng)。它不需要參數(shù)并返回 item。 隊(duì)列被修改。
def dequeue(self):
item = self.items.pop()
return item
# isEmpty() 查看隊(duì)列是否為空。它不需要參數(shù)，并返回布爾值。
def isEmpty(self):
return 0 == len(self.items)
# size() 返回隊(duì)列中的項(xiàng)數(shù)。它不需要參數(shù)，并返回一個整數(shù)。
def size(self):
length = len(self.items)
return length
問題描述
假設(shè)實(shí)驗(yàn)室里有一臺打印機(jī)供學(xué)生共性。當(dāng)學(xué)生向共享打印機(jī)發(fā)送打印任務(wù)時，任務(wù)被放置在隊(duì)列中以便以先來先服務(wù)的方式被處理。如何才能通過python程序模擬的方式得到每次提交任務(wù)的平均等待時間呢？（平均等待時間不包括打印本身的時間，僅指在隊(duì)列中排隊(duì)的時間。）
我們假定：
- 學(xué)生們每次打印的頁數(shù)在1到20頁之間。
- 打印機(jī)平均每小時會收到20個打印請求，即平均每180秒1個請求。
- 每秒新增任務(wù)的可能性相等，即任務(wù)的產(chǎn)生為獨(dú)立同分布
- 打印機(jī)的打印速度恒定。
總體模擬思路
當(dāng)學(xué)生提交打印任務(wù)時，我們將把他們添加到打印任務(wù)的等待隊(duì)列。當(dāng)打印機(jī)完成任務(wù)時，它將檢查隊(duì)列，將剩余的任務(wù)中隊(duì)首的那一個彈出并處理。學(xué)生等待他們的任務(wù)打印的平均時間也等于任務(wù)在隊(duì)列中等待的平均時間。
我們將對每個任務(wù)入隊(duì)和出隊(duì)的時間戳進(jìn)行記錄，由此得到該任務(wù)在隊(duì)列中的等待時間。
對任務(wù)的模擬
任務(wù)類應(yīng)包括以下幾個功能：隨機(jī)生成頁數(shù)、記錄入隊(duì)時間戳、返回需要打印的頁數(shù)、根據(jù)當(dāng)前時間戳返回等待的時間。
class Task:
#任務(wù)初始化
def __init__(self, time):
# time 為傳入的任務(wù)創(chuàng)建時間，也就是入隊(duì)時間
self.in_time = time
self.pages = random.randrange(1,21) # 隨機(jī)生成1到20頁之間的頁數(shù)
#返回任務(wù)需要打印的頁數(shù)
def getPage(self):
return self.pages
def waitTime(self, out_time):
# out_time為當(dāng)前時間戳
return out_time - self.in_time
對打印機(jī)的模擬
打印機(jī)類應(yīng)包括以下幾個功能：設(shè)定打印速度（多少秒每頁）、載入新任務(wù)并計(jì)算新任務(wù)剩余打印時間、記錄當(dāng)前任務(wù)的剩余打印時間、打?。礈p少已載入任務(wù)的剩余打印時間）。
class Printer:
#打印機(jī)初始化
def __init__(self, timeperpage):
#timeperpage 為每頁打印所需要的時間，設(shè)定好后便是恒定的值
self.timeperpage = timeperpage
self.current_task = None #記錄當(dāng)前正在處理的任務(wù)
self.remaining_time = 0 #記錄當(dāng)前任務(wù)的剩余處理時間
#返回打印機(jī)中是否有任務(wù)
def isBusy(self):
return self.current_task != None
#載入新的任務(wù)
def loadTask(self, next_task):
# next_task 為新的任務(wù)
self.current_task = next_task
self.remaining_time = next_task.getPage()*self.timeperpage #計(jì)算新的剩余打印時間
#打印
def printTask(self):
if self.isBusy(): #有任務(wù)需要處理
self.remaining_time -= 1 # 打印，也就是將剩余打印時間減一
if self.remaining_time <= 0: # 當(dāng)前任務(wù)打印結(jié)束
self.current_task = None
else: #空閑中
pass
借助隊(duì)列模擬打印情況，并計(jì)算平均等待時間
由于任務(wù)的產(chǎn)生為獨(dú)立同分布，我們可以在每一秒上運(yùn)行1到180間隨機(jī)數(shù)生成，當(dāng)值為1時產(chǎn)生新任務(wù)請求，以模擬每180秒一個新任務(wù)的任務(wù)產(chǎn)生速度。
def simulation(total_time, timeperpage):
# total_time為總的實(shí)驗(yàn)時間，timeperpage為每頁打印所需要的時間
waiting_time = [] #記錄每個任務(wù)的等待時間
printer = Printer(timeperpage) #初始化打印機(jī)
waitQueue = Queue() #初始化任務(wù)等待隊(duì)列
for second in range(total_time):
rand_num = random.randrange(1,181) #產(chǎn)生1到180之間的隨機(jī)數(shù)
if rand_num == 1:
new_task = Task(second) #產(chǎn)生新任務(wù)
waitQueue.enqueue(new_task) #新任務(wù)進(jìn)入等待隊(duì)列
if (not printer.isBusy()) and (not waitQueue.isEmpty()): #打印機(jī)空閑并且有任務(wù)在等待
next_task = waitQueue.dequeue() # 彈出下一個任務(wù)
waiting_time.append(new_task.waitTime(second)) # 計(jì)算并記錄等待時間
printer.loadTask(next_task) #載入新的任務(wù)
printer.printTask() #打印
average_time = sum(waiting_time)/len(waiting_time)
return average_time
完整實(shí)驗(yàn)代碼如下：
import random
class Queue():
# Queue() 創(chuàng)建一個空的新隊(duì)列。 它不需要參數(shù)，并返回一個空隊(duì)列。
def __init__(self):
self.items = []
# enqueue(item) 將新項(xiàng)添加到隊(duì)尾。 它需要 item 作為參數(shù)，并不返回任何內(nèi)容。
def enqueue(self, item):
self.items.insert(0, item)
# dequeue() 從隊(duì)首移除項(xiàng)。它不需要參數(shù)并返回 item。 隊(duì)列被修改。
def dequeue(self):
item = self.items.pop()
return item
# isEmpty() 查看隊(duì)列是否為空。它不需要參數(shù)，并返回布爾值。
def isEmpty(self):
return 0 == len(self.items)
# size() 返回隊(duì)列中的項(xiàng)數(shù)。它不需要參數(shù)，并返回一個整數(shù)。
def size(self):
length = len(self.items)
return length
class Task:
#任務(wù)初始化
def __init__(self, time):
# time 為傳入的任務(wù)創(chuàng)建時間，也就是入隊(duì)時間
self.in_time = time
self.pages = random.randrange(1,21) # 隨機(jī)生成1到20頁之間的頁數(shù)
#返回任務(wù)需要打印的頁數(shù)
def getPage(self):
return self.pages
def waitTime(self, out_time):
# out_time為當(dāng)前時間戳
return out_time - self.in_time
class Printer:
#打印機(jī)初始化
def __init__(self, timeperpage):
#timeperpage 為每頁打印所需要的時間，設(shè)定好后便是恒定的值
self.timeperpage = timeperpage
self.current_task = None #記錄當(dāng)前正在處理的任務(wù)
self.remaining_time = 0 #記錄當(dāng)前任務(wù)的剩余處理時間
#返回打印機(jī)中是否有任務(wù)
def isBusy(self):
return self.current_task != None
#載入新的任務(wù)
def loadTask(self, next_task):
# next_task 為新的任務(wù)
self.current_task = next_task
self.remaining_time = next_task.getPage()*self.timeperpage #計(jì)算新的剩余打印時間
#打印
def printTask(self):
if self.isBusy(): #有任務(wù)需要處理
self.remaining_time -= 1 # 打印，也就是將剩余打印時間減一
if self.remaining_time <= 0: # 當(dāng)前任務(wù)打印結(jié)束
self.current_task = None
else: #空閑中
pass
def simulation(total_time, timeperpage):
# total_time為總的實(shí)驗(yàn)時間，timeperpage為每頁打印所需要的時間
waiting_time = [] #記錄每個任務(wù)的等待時間
printer = Printer(timeperpage) #初始化打印機(jī)
waitQueue = Queue() #初始化任務(wù)等待隊(duì)列
for second in range(total_time):
rand_num = random.randrange(1,181) #產(chǎn)生1到180之間的隨機(jī)數(shù)
if rand_num == 1:
new_task = Task(second) #產(chǎn)生新任務(wù)
waitQueue.enqueue(new_task) #新任務(wù)進(jìn)入等待隊(duì)列
if (not printer.isBusy()) and (not waitQueue.isEmpty()): #打印機(jī)空閑并且有任務(wù)在等待
next_task = waitQueue.dequeue() # 彈出下一個任務(wù)
waiting_time.append(new_task.waitTime(second)) # 計(jì)算并記錄等待時間
printer.loadTask(next_task) #載入新的任務(wù)
printer.printTask() #打印
average_time = sum(waiting_time)/len(waiting_time)
return average_time
def main():
timeperpage = 5
total_time = 36000 #10小時
print("-----------------")
for i in range(10):
average_time = simulation(total_time,timeperpage)
print("平均等待打印時間為：%.5f 秒"%average_time)
print("-----------------")
if __name__ == "__main__":
main()
我們選定10小時為模擬時間，當(dāng) timeperpage 為 1 時，運(yùn)行結(jié)果：
-----------------
平均等待打印時間為：0.11966 秒
-----------------
平均等待打印時間為：0.46847 秒
-----------------
平均等待打印時間為：0.31754 秒
-----------------
平均等待打印時間為：0.38251 秒
-----------------
平均等待打印時間為：0.46087 秒
-----------------
平均等待打印時間為：0.30808 秒
-----------------
平均等待打印時間為：0.24670 秒
-----------------
平均等待打印時間為：0.40659 秒
-----------------
平均等待打印時間為：0.27869 秒
-----------------
平均等待打印時間為：0.30055 秒
-----------------
當(dāng) timeperpage 為 5 時，運(yùn)行結(jié)果：
-----------------
平均等待打印時間為：11.33854 秒
-----------------
平均等待打印時間為：8.60104 秒
-----------------
平均等待打印時間為：13.73057 秒
-----------------
平均等待打印時間為：9.30270 秒
-----------------
平均等待打印時間為：9.01156 秒
-----------------
平均等待打印時間為：12.09268 秒
-----------------
平均等待打印時間為：13.05405 秒
-----------------
平均等待打印時間為：8.96023 秒
-----------------
平均等待打印時間為：13.79907 秒
-----------------
平均等待打印時間為：9.56500 秒
-----------------
當(dāng) timeperpage 為 10 時，運(yùn)行結(jié)果：
-----------------
平均等待打印時間為：44.32461 秒
-----------------
平均等待打印時間為：58.77295 秒
-----------------
平均等待打印時間為：44.65238 秒
-----------------
平均等待打印時間為：49.37629 秒
-----------------
平均等待打印時間為：54.00000 秒
-----------------
平均等待打印時間為：47.69378 秒
-----------------
平均等待打印時間為：49.18557 秒
-----------------
平均等待打印時間為：54.68367 秒
-----------------
平均等待打印時間為：58.63158 秒
-----------------
平均等待打印時間為：56.18391 秒
-----------------
每頁所需時間越短，說明打印機(jī)速度越快，因而平均等待時間越短。這與實(shí)驗(yàn)數(shù)據(jù)是相符的。
