Python的隊(duì)列實(shí)例分析

這篇“Python的隊(duì)列實(shí)例分析”文章的知識(shí)點(diǎn)大部分人都不太理解，所以小編給大家總結(jié)了以下內(nèi)容，內(nèi)容詳細(xì)，步驟清晰，具有一定的借鑒價(jià)值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來(lái)看看這篇“Python的隊(duì)列實(shí)例分析”文章吧。

模擬打印機(jī)任務(wù)隊(duì)列過(guò)程

計(jì)算機(jī)科學(xué)中也有眾多的隊(duì)列例子。比如計(jì)算機(jī)實(shí)驗(yàn)室有10臺(tái)計(jì)算機(jī)，它們都與同一臺(tái)打印機(jī)相連。當(dāng)學(xué)生需要打印的時(shí)候，他們的打印任務(wù)會(huì)進(jìn)入一個(gè)隊(duì)列。該隊(duì)列中的第一個(gè)任務(wù)就是即將執(zhí)行的打印任務(wù)。如果一個(gè)任務(wù)排在隊(duì)列的最后面，那么它必須等到所有前面的任務(wù)都執(zhí)行完畢后才能執(zhí)行。

學(xué)生向共享打印機(jī)發(fā)送打印請(qǐng)求，這些打印任務(wù)被存在一個(gè)隊(duì)列中，并且按照先到先得的順序執(zhí)行。這樣的設(shè)定可能導(dǎo)致很多問(wèn)題。其中最重要的是，打印機(jī)能否處理一定量的工作。如果不能，學(xué)生可能會(huì)由于等待過(guò)長(zhǎng)時(shí)間而錯(cuò)過(guò)要上的課。

考慮計(jì)算機(jī)實(shí)驗(yàn)室里的這樣一個(gè)場(chǎng)景：在任何給定的一小時(shí)內(nèi)，實(shí)驗(yàn)室里都有10個(gè)學(xué)生。他們?cè)谶@ 一小時(shí)內(nèi)最多打印2次，并且打印的頁(yè)數(shù)從1到20頁(yè)不等。實(shí)驗(yàn)室的打印機(jī)比較老舊，每分鐘只能以低質(zhì)量打印10頁(yè)。也可以將打印質(zhì)量調(diào)高，但是這樣做會(huì)導(dǎo)致打印機(jī)每分鐘只能打印5頁(yè)。降低打印速度可能導(dǎo)致學(xué)生等待過(guò)長(zhǎng)時(shí)間。那么，應(yīng)該如何設(shè)置打印速度呢？

可以通過(guò)構(gòu)建一個(gè)模型來(lái)解決該問(wèn)題。我們需要為學(xué)生、打印任務(wù)和打印機(jī)構(gòu)建對(duì)象。當(dāng)學(xué)生提交打印任務(wù)時(shí)，我們需要將它們加入打印機(jī)的任務(wù)隊(duì)列中。當(dāng)打印機(jī)執(zhí)行完一個(gè)任務(wù)后，它會(huì)檢查該隊(duì)列，看看其中是否還有需要處理的任務(wù)。我們感興趣的是學(xué)生平均需要等待多久才能拿到打印好的文章。這個(gè)時(shí)間等于打印任務(wù)在隊(duì)列中的平均等待時(shí)間。

在模擬時(shí)，需要應(yīng)用一些概率學(xué)知識(shí)。舉例來(lái)說(shuō)，學(xué)生打印的文章可能有1~20頁(yè)。如果各頁(yè)數(shù)出現(xiàn)的概率相等，那么打印任務(wù)的實(shí)際時(shí)長(zhǎng)可以通過(guò)模擬1~20的一個(gè)文章頁(yè)數(shù)隨機(jī)數(shù)來(lái)計(jì)算得出。

如果實(shí)驗(yàn)室里有10個(gè)學(xué)生，并且在一小時(shí)內(nèi)每個(gè)人都打印兩次，那么每小時(shí)平均就有20個(gè)打印任務(wù)。 在任意一秒，創(chuàng)建一個(gè)打印請(qǐng)求的概率是多少？ 回答這個(gè)問(wèn)題需要考慮任務(wù)與時(shí)間的比值。每小時(shí)20個(gè)任務(wù)相當(dāng)于每180秒1個(gè)任務(wù)。

可以通過(guò)1~180的一個(gè)隨機(jī)數(shù)來(lái)模擬每秒內(nèi)產(chǎn)生打印請(qǐng)求的概率(1/180的概率)。如果隨機(jī)數(shù)正好是180，那么就認(rèn)為有 一個(gè)打印請(qǐng)求被創(chuàng)建。注意，可能會(huì)出現(xiàn)多個(gè)請(qǐng)求接連被創(chuàng)建的情況，也可能很長(zhǎng)一段時(shí)間內(nèi)都沒(méi)有請(qǐng)求。這就是模擬的本質(zhì)。我們希望在常用參數(shù)已知的情況下盡可能準(zhǔn)確地模擬。

主要模擬步驟：

1.創(chuàng)建一個(gè)打印任務(wù)隊(duì)列。每一個(gè)任務(wù)到來(lái)時(shí)都會(huì)有一個(gè)時(shí)間戳。一開(kāi)始，隊(duì)列是空的。

2.針對(duì)每一秒（currentSecond），執(zhí)行以下操作。

• 是否有新創(chuàng)建的打印任務(wù)？如果是，以 currentSecond 作為其時(shí)間戳并將該任務(wù)加入到隊(duì)列中。

• 如果打印機(jī)空閑，并且有正在等待執(zhí)行的任務(wù)，執(zhí)行以下操作：

• 從隊(duì)列中取出第一個(gè)任務(wù)并提交給打印機(jī)；

• 用 currentSecond 減去該任務(wù)的時(shí)間戳，以此計(jì)算其等待時(shí)間；

• 將該任務(wù)的等待時(shí)間存入一個(gè)列表，用來(lái)作為計(jì)算平均等待時(shí)間的數(shù)據(jù)；

• 根據(jù)該任務(wù)的頁(yè)數(shù)，計(jì)算執(zhí)行時(shí)間。

• 打印機(jī)進(jìn)行一秒的打印，同時(shí)從該任務(wù)的執(zhí)行時(shí)間中減去一秒。

• 如果打印任務(wù)執(zhí)行完畢，即任務(wù)的執(zhí)行時(shí)間減為0，則說(shuō)明打印機(jī)回到空閑狀態(tài)。

3.當(dāng)模擬完成之后，根據(jù)等待時(shí)間列表中的值計(jì)算平均等待時(shí)間。

構(gòu)建隊(duì)列程序

class Queue:
    def __init__(self):
        self.items = []            # 構(gòu)建空隊(duì)列
    def isEmpty(self):
        return self.items ==[]     # 判斷是否為空
    def enqueue(self,item):
        self.items.insert(0, item) # 在隊(duì)列尾部(列表左端)插入元素
    def dequeue(self):
        return self.items.pop()    # 在隊(duì)列頭部(列表右端)移出元素
    def size(self):
        return len(self.items)     # 隊(duì)列(列表)長(zhǎng)度

模擬打印程序

import random
# 模擬打印機(jī)
class Printer:
    # 打印機(jī)初始化
    def __init__(self, ppm):
        self.pagerate = ppm      # 打印速度 頁(yè)/分鐘
        self.currentTask = None  # 現(xiàn)有任務(wù)
        self.timeRemain = 0      # 該任務(wù)所需時(shí)間
    # 打印任務(wù)倒計(jì)時(shí) 0代表打印完成
    def tick(self):
        # 如果打印機(jī)正在執(zhí)行任務(wù)
        if self.currentTask != None:
            # 該任務(wù)執(zhí)行時(shí)間 = 執(zhí)行時(shí)間 - 1（執(zhí)行時(shí)間倒計(jì)時(shí)）
            self.timeRemaining = self.timeRemaining - 1   
            if self.timeRemaining <= 0:     # 該任務(wù)執(zhí)行時(shí)間 <= 0
                self.currentTask = None     # 該任務(wù)執(zhí)行完畢
    # 判斷打印機(jī)是否空閑
    def busy(self):
        if self.currentTask != None:
            return True
        else:
            return False
    # 打印機(jī)接受新任務(wù)
    def startNext(self, newtask):
        self.currentTask = newtask
        # 新打印任務(wù)需要時(shí)間 = 新任務(wù)頁(yè)數(shù) * (60 / 每分鐘打印多少頁(yè)的速度)
        # (60 / 每分鐘打印多少頁(yè)的速度) = 每打印一頁(yè)所需要的秒數(shù)
        self.timeRemaining = newtask.getPages() * (60 / self.pagerate)

# 模擬單個(gè)任務(wù)的屬性
class Task:
    # 任務(wù)初始化
    def __init__(self, time):
        self.timestamp = time                # 創(chuàng)建任務(wù)的時(shí)間點(diǎn)
        self.pages = random.randrange(1, 21) # 任務(wù)頁(yè)數(shù) 在 1~20 間隨機(jī)生成
    def getStamp(self):
        return self.timestamp  # 獲取任務(wù)創(chuàng)建的時(shí)間點(diǎn)
    def getPages(self):
        return self.pages      # 獲取任務(wù)的頁(yè)數(shù)
    def waitTime(self, currenttime):
        # 任務(wù)的等待時(shí)間 = 當(dāng)前時(shí)間 - 任務(wù)創(chuàng)建的時(shí)間點(diǎn)
        return currenttime - self.timestamp   

# 模擬學(xué)生創(chuàng)建的新打印請(qǐng)求
def newPrintTask():
    # 打印請(qǐng)求是一個(gè)隨機(jī)事件
    # 通過(guò)1~180之間的一個(gè)隨機(jī)數(shù)來(lái)模擬每秒內(nèi)產(chǎn)生打印請(qǐng)求的概率
    # 如果隨機(jī)數(shù)正好是180，那么就認(rèn)為有一個(gè)打印請(qǐng)求被創(chuàng)建。
    num = random.randrange(1, 181)
    if num == 180:
        return True
    else:
        return False

# 模擬打印過(guò)程
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 個(gè)任務(wù)等待處理"
          % (averageWait, printQueue.size()))

模擬打印過(guò)程（有注釋）

def simulation(numSeconds, pagesPerMinute):
    # numSeconds-時(shí)間段
    # pagesPerMinute-打印速度，頁(yè)/分鐘
    labprinter = Printer(pagesPerMinute)  # 創(chuàng)建打印機(jī)
    printQueue = Queue()                  # 創(chuàng)建打印機(jī)任務(wù)隊(duì)列
    waitingtimes = []                     # 創(chuàng)建等待時(shí)間數(shù)據(jù)樣本列表
    for currentSecond in range(numSeconds):  # 一次循環(huán)代表一秒
        if newPrintTask():                   # 如果 有打印請(qǐng)求創(chuàng)建
            task = Task(currentSecond)       # 創(chuàng)建打印任務(wù)并記錄當(dāng)前時(shí)間點(diǎn)
            printQueue.enqueue(task)         # 打印任務(wù)進(jìn)入打印機(jī)任務(wù)隊(duì)列
        # 如果 打印機(jī)空閑 并且 打印機(jī)任務(wù)隊(duì)列有任務(wù)
        if(not labprinter.busy())and(not printQueue.isEmpty()):
            nexttask = printQueue.dequeue()  # 從隊(duì)列取出新任務(wù)
            # 根據(jù)當(dāng)前時(shí)間點(diǎn)計(jì)算新任務(wù)在任務(wù)隊(duì)列里的等待時(shí)間 并將等待時(shí)間記錄進(jìn)樣本列表
            waitingtimes.append(nexttask.waitTime(currentSecond))
            labprinter.startNext(nexttask)   # 開(kāi)始執(zhí)行新任務(wù) 打印機(jī)進(jìn)入忙碌狀態(tài)
        labprinter.tick()  # 每循環(huán)一次 當(dāng)前打印任務(wù)執(zhí)行倒計(jì)時(shí)減少一秒
    averageWait = sum(waitingtimes)/len(waitingtimes)
    print("平均等待 %6.2f 秒，還有 %3d 個(gè)任務(wù)等待處理" % (averageWait, printQueue.size()))

需要注意的是，時(shí)間戳是我們根據(jù)循環(huán)模擬出來(lái)的，我們給定了 numSeconds 時(shí)間段后，每循環(huán)一次相當(dāng)于時(shí)間過(guò)了一秒。

雖然每次模擬的結(jié)果不一定相同。但對(duì)此我們不需要在意。這是由于隨機(jī)數(shù)的本質(zhì)導(dǎo)致的。我們感興趣的是當(dāng)參數(shù)改變時(shí)結(jié)果出現(xiàn)的趨勢(shì)。

下面是一些結(jié)果：

我們根據(jù)模擬得到了打印機(jī)在兩種速度下，一小時(shí)內(nèi)的任務(wù)執(zhí)行情況的參考數(shù)據(jù)?？梢院苊黠@的看到，當(dāng)打印質(zhì)量提升后，學(xué)生平均等待時(shí)間相比低質(zhì)量情況下顯著增加，并且任務(wù)處理未完成的次數(shù)也出現(xiàn)了增加，所以設(shè)置打印機(jī)為低質(zhì)量模式是最合適的。

以上就是關(guān)于“Python的隊(duì)列實(shí)例分析”這篇文章的內(nèi)容，相信大家都有了一定的了解，希望小編分享的內(nèi)容對(duì)大家有幫助，若想了解更多相關(guān)的知識(shí)內(nèi)容，請(qǐng)關(guān)注億速云行業(yè)資訊頻道。