模拟隊列列印問題

• Python資料結構——隊列 模拟隊列列印問題
• • 1. 問題描述
  • 2. 模拟步驟
  • 3. 程式實作
  • • 3.1 Printer類
    • 3.2 Task類
    • 3.3 主程式
  • 4. 完整程式
  • 5. 程式運作
  • 6. 讨論

Python資料結構——隊列 模拟隊列列印問題

本文旨在用Python模拟列印任務隊列。

1. 問題描述

學生向共享列印機發送列印請求，這些列印任務被存在一個隊列中，并且按照先到先得的順序執行。這樣的設定可能導緻很多問題。其中最重要的是，列印機能否處理一定量的工作。如果不能，學生可能會由于等待過長時間而錯過要上的課。

考慮計算機科學實驗室裡的這樣一個場景：在任何給定的一小時内，實驗室裡都有約10個學生。他們在這一小時内最多列印2 次，并且列印的頁數從1到20不等。實驗室的列印機比較老舊，每分鐘隻能以低品質列印10頁。可以将列印品質調高，但是這樣做會導緻列印機每分鐘隻能列印5頁。降低列印速度可能導緻學生等待過長時間。那麼，應該如何設定列印速度呢？

可以通過建構一個實驗室模型來解決該問題。我們需要為學生、列印任務和列印機建構對象。當學生送出列印任務時，我們需要将它們加入等待清單中，該清單是列印機上的列印任務隊列。當列印機執行完一個任務後，它會檢查該隊列，看看其中是否還有需要處理的任務。我們感興趣的是學生平均需要等待多久才能拿到列印好的文章。這個時間等于列印任務在隊列中的平均等待時間。

在模拟時，需要應用一些機率學知識。舉例來說，學生列印的文章可能有1-20頁。如果各頁數出現的機率相等，那麼列印任務的實際時長可以通過1-20的一個随機數來模拟。

如果實驗室裡有10個學生，并且在一小時内每個人都列印兩次，那麼每小時平均就有20個列印任務。在任意一秒，建立一個列印任務的機率是多少？回答這個問題需要考慮任務與時間的比值。每小時20個任務相當于每180秒1個任務。

20 個任務 1 小時 ∗ 1 小時 60 分 ∗ 1 分 60 秒 = 1 個任務 180 秒 \frac{20\text{個任務}}{1\text{小時}} * \frac{1\text{小時}}{60\text{分}} * \frac{1\text{分}}{60\text{秒}} = \frac{1\text{個任務}}{180\text{秒}} 1小時20個任務​∗60分1小時​∗60秒1分​=180秒1個任務​

可以通過1-180的一個随機數來模拟每秒内産生列印任務的機率。如果随機數正好是180，那麼就認為有一個列印任務被建立。注意，可能會出現多個任務接連被建立的情況，也可能很長一段時間内都沒有任務。這就是模拟的本質。我們希望在常用參數已知的情況下盡可能準确地模拟。

2. 模拟步驟

下面是主要的模拟步驟。

(1) 建立一個列印任務隊列。每一個任務到來時都會有一個時間戳。一開始，隊列是空的。

(2) 針對每一秒(currentSecond)，執行以下操作。

• 是否有新建立的列印任務？如果是，以currentSecond 作為其時間戳并将該任務加入到隊列中。
• 如果列印機空閑，并且有正在等待執行的任務，執行以下操作：
  • 從隊列中取出第一個任務并送出給列印機；
  • 用currentSecond減去該任務的時間戳，以此計算其等待時間；
  • 将該任務的等待時間存入一個清單，以備後用；
  • 根據該任務的頁數，計算執行時間。
• 列印機進行一秒的列印，同時從該任務的執行時間中減去一秒。

• 如果列印任務執行完畢，或者說任務需要的時間減為0，則說明列印機回到空閑狀态。

  (3) 當模拟完成之後，根據等待時間清單中的值計算平均等待時間。

3. 程式實作

建立3個類：Printer、Task和PrintQueue。它們分别模拟列印機、列印任務和隊列。

3.1 Printer類

Printer類需要檢查目前是否有待完成的任務。如果有，那麼列印機就處于工作狀态，并且其工作所需的時間可以通過要列印的頁數來計算。其構造方法會初始化列印速度，即每分鐘列印多少頁。tick方法會減量計時，并且在執行完任務之後将列印機設定成空閑狀态。

class Printer:
    def __init__(self, ppm):
        self.pagerate = ppm
        self.currentTask = None
        self.timeRemaining = 0

    def tick(self):
        if self.currentTask != None:
            self.timeRemaining = self.timeRemaining - 1
            if self.timeRemaining <= 0:
                self.currentTask = None
        
    def busy(self):
        if self.currentTask != None:
            return True
        else:
            return False

    def startNext(self, newtask):
        self.currentTask = newtask
        self.timeRemaining = newtask.getPages() * 60 / self.pagerate

           

3.2 Task類

Task類代表單個列印任務。當任務被建立時，随機數生成器會随機提供頁數，取值範圍是1-20。

使用random子產品中的randrange函數來生成随機數。

每一個任務都需要儲存一個時間戳，用于計算等待時間。這個時間戳代表任務被建立并放入列印任務隊列的時間。waitTime方法可以獲得任務在隊列中等待的時間。

import random

class Task:
    def __init__(self, time):
        self.timestamp = time
        self.pages = random.randrange(1, 21)
    
    def getStamp(self):
        return self.timestamp

    def getPages(self):
        return self.pages
    
    def waitTime(self, currenttime):
        return currenttime - self.timestamp

           

3.3 主程式

主模拟程式實作了之前描述的算法。printQueue對象是隊列抽象資料類型的執行個體。布爾輔助函數newPrintTask判斷是否有新建立的列印任務。我們再一次使用random子產品中的randrange函數來生成随機數，不過這一次的取值範圍是1-180。平均每180秒有一個列印任務。通過從随機數中選取180，可以模拟這個随機事件。該模拟程式允許設定總時間和列印機每分鐘列印多少頁。

import random

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("Average Wait %6.2f secs %3d tasks remaining." % (averageWait, printQueue.size()))


def newPrintTask():
    num = random.randrange(1, 181)
    if num == 180:
        return True
    else:
        return False

           

4. 完整程式

import random

class Queue:
    def __init__(self):
        self.items = []
    
    def isEmpty(self):             # 判斷是否為空
        return self.items == []
    
    def enqueue(self, item):       # 壓入隊列（這裡将清單位置0作為隊列尾部）
        self.items.insert(0, item)

    def dequeue(self):             # 彈出（這裡将清單末尾作為隊列頭部）
        return self.items.pop()

    def size(self):                # 傳回隊列中元素數目
        return len(self.items)


class Printer:
    def __init__(self, ppm):
        self.pagerate = ppm
        self.currentTask = None
        self.timeRemaining = 0

    def tick(self):
        if self.currentTask != None:
            self.timeRemaining = self.timeRemaining - 1
            if self.timeRemaining <= 0:
                self.currentTask = None
        
    def busy(self):
        if self.currentTask != None:
            return True
        else:
            return False

    def startNext(self, newtask):
        self.currentTask = newtask
        self.timeRemaining = newtask.getPages() * 60 / self.pagerate


class Task:
    def __init__(self, time):
        self.timestamp = time
        self.pages = random.randrange(1, 21)
    
    def getStamp(self):
        return self.timestamp

    def getPages(self):
        return self.pages
    
    def waitTime(self, currenttime):
        return currenttime - self.timestamp


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("Average Wait %6.2f secs %3d tasks remaining." % (averageWait, printQueue.size()))


def newPrintTask():
    num = random.randrange(1, 181)
    if num == 180:
        return True
    else:
        return False

           

5. 程式運作

首先，模拟60分鐘（3600秒）内列印速度為每分鐘5頁。并且，我們進行10次這樣的模拟。由于模拟中使用了随機數，是以每次傳回的結果都不同。

>>> for i in range(10):
        simulation(3600, 5)

Average Wait  23.85 secs   0 tasks remaining.
Average Wait 164.55 secs   3 tasks remaining.
Average Wait  36.53 secs   0 tasks remaining.
Average Wait 211.04 secs   3 tasks remaining.
Average Wait  65.12 secs   0 tasks remaining.
Average Wait 114.25 secs   5 tasks remaining.
Average Wait 126.95 secs   3 tasks remaining.
Average Wait 313.94 secs   6 tasks remaining.
Average Wait  50.41 secs   0 tasks remaining.
Average Wait 109.14 secs   1 tasks remaining.
           

現在把列印速度改成每分鐘10頁，然後再模拟10次。由于加快了列印速度，是以我們希望一小時内能完成更多列印任務。

>>> for i in range(10):
        simulation(3600, 10)

Average Wait  18.12 secs   2 tasks remaining.
Average Wait  14.25 secs   0 tasks remaining.
Average Wait  21.76 secs   0 tasks remaining.
Average Wait  12.29 secs   2 tasks remaining.
Average Wait  24.60 secs   0 tasks remaining.
Average Wait  63.46 secs   0 tasks remaining.
Average Wait   4.86 secs   0 tasks remaining.
Average Wait  40.50 secs   1 tasks remaining.
Average Wait  11.96 secs   1 tasks remaining.
Average Wait  20.46 secs   0 tasks remaining.
           

6. 讨論

在之前的内容中，我們試圖解答這樣一個問題：如果提高列印品質并降低列印速度，列印機能否及時完成所有任務？我們編寫了一個程式來模拟随機送出的列印任務，待列印的頁數也是随機的。

上面的輸出結果顯示，按每分鐘5頁的列印速度，任務的等待時間在23.85秒和313.94秒之間，相差約5分鐘。提高列印速度之後，等待時間在4.86秒和63.46秒之間。此外，在每分鐘5頁的速度下，10次模拟中有6次沒有按時完成所有任務。

可見，降低列印速度以提高列印品質，并不是明智的做法。學生不能等待太長時間，當他們要趕去上課時尤其如此。5分鐘的等待時間實在是太長了。

這種模拟分析能幫助我們回答很多“如果”問題。隻需改變參數，就可以模拟感興趣的任意行為。以下是幾個例子。

• 如果實驗室裡的學生增加到20個，會怎麼樣？
• 如果是周六，學生不需要上課，他們是否願意等待？
• 如果每個任務的頁數變少了，會怎麼樣？

這些問題都能通過修改本例中的模拟程式來解答。但是，模拟的準确度取決于它所基于的假設和參數。真實的列印任務數量和學生數目是準确構模組化拟程式必不可缺的資料。