日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

Python的數據結構與算法的隊列詳解(3)_python

作者：姜學遷 ? 更新時間： 2022-05-09 編程語言

模擬打印機任務隊列過程

計算機科學中也有眾多的隊列例子。比如計算機實驗室有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 時間段后，每循環一次相當于時間過了一秒。

雖然每次模擬的結果不一定相同。但對此我們不需要在意。這是由于隨機數的本質導致的。我們感興趣的是當參數改變時結果出現的趨勢。?

下面是一些結果：

在這里插入圖片描述
在這里插入圖片描述

我們根據模擬得到了打印機在兩種速度下，一小時內的任務執行情況的參考數據。可以很明顯的看到，當打印質量提升后，學生平均等待時間相比低質量情況下顯著增加，并且任務處理未完成的次數也出現了增加，所以設置打印機為低質量模式是最合適的。

總結

原文鏈接：https://blog.csdn.net/jiang1126/article/details/123337817

欄目分類
最近更新