Python之队列模拟算法（打印机问题）

曾经终败给现在 2022-02-19 00:45 397阅读 0赞

**模拟打印机问题：**  
如果平均每天任意一个小时实验室里都有10个学生，并且每人需要发起2次打印任务，平均每小时就有20个打印任务，即平均每180秒生成一个打印任务，那么，在任意一秒，产生一个打印任务的概率就是1/180，每个打印任务的页数从1到20页不等，计算平均等待时长。

**以下为主要的模拟过程：**  
1、创建一个打印任务队列。每个任务在生成时被赋予一个“时间节点”。队列在开始时是空的。  
2、对于每一秒(打印过程中的当前秒currentSecond)：  
(1)是否有新的打印任务生成？如果有，把它加入打印队列，并把当前秒作为其“时间节点”。  
(2)如果打印机空闲并且有任务正在等待队列中：  
① 从打印队列中移除下一个打印任务并且将其提交给打印机；  
② 从当前秒中减去当前任务的“时间节点”值，计算得到该任务的等待时间；  
③ 将该任务的等待时间添加到一个列表中，用于后续操作；  
④ 基于打印任务的页数，求出需要多长的打印时间。  
(3)如果此时打印机在工作中，那对于打印机而言，就工作了一秒钟；对于打印任务而言,它离打印结束又近了一秒钟(剩余打印时间减1)。  
(4)如果此时打印任务已经完成，也即是剩余打印时间为0时，打印机就进入空闲状态。  
3、在整个模拟算法完成后，依据生成的等待时间列表中的数据，计算平均打印时间。

**完整代码：**

import random
    
    # 自定义队列类
    class Queue(object):
        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(object):
        def __init__(self, ppm):
            self.pagerate = ppm                 #页面打印速率
            self.currentTask = None             #初始化当前任务
            self.timeRemaining = 0              #初始化剩余时间
        
        # 计算正在执行的打印任务的剩余时长，即减去当前秒(1秒时长)后的时长
        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(object):
        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 simulation(numSeconds, pagesPerMinute):
        labprinter = Printer(pagesPerMinute)        #实例化打印机类，参数为页/分钟
        printQueue = Queue()                        #创建打印队列
        waitingtimes = []                           #初始化等待时长列表
        for currentSecond in range(numSeconds):     #在指定时长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)              #生成随机数，平均3分钟有一个任务
        if num == 180:                              
            return True                             #有打印任务
        else:
            return False                            #没有打印任务
    
    if __name__ == '__main__':
        for i in range(10):                         #获取10次打印情况
            simulation(3600, 5)                     #获取1小时内，每分钟打印5张的打印情况

**结果为：**

Average Wait  58.35 secs   0 tasks remaining.
    Average Wait  85.43 secs   0 tasks remaining.
    Average Wait  83.68 secs   4 tasks remaining.
    Average Wait 107.12 secs   0 tasks remaining.
    Average Wait  71.05 secs   0 tasks remaining.
    Average Wait  30.77 secs   3 tasks remaining.
    Average Wait 143.09 secs   0 tasks remaining.
    Average Wait 195.75 secs   4 tasks remaining.
    Average Wait 265.95 secs   1 tasks remaining.
    Average Wait  70.94 secs   0 tasks remaining.