打印机算法--队列（python）

文章目录

1.案例描述

在计算机科学实验室里考虑下面的情况：

• 平均每天大约10名学生在任何给定时间在实验室工作。
• 这些学生通常在此期间打印两次
• 这些任务的长度范围从1到20页。
• 实验室中的打印机较旧，每分钟以草稿质量可以处理10页。打印机可以切换以提供更好的质量，但是它将每分钟只能处理五页。

较慢的打印速度可能会使学生等待太久。应使用什么页面速率？

2.案例分析

我们可以通过建立一个模拟实验来决定：

我们将需要为学生，打印任务和打印机构建表示如下图。

当学生提交打印任务时，我们将把他们添加到等待列表中，一个打印任务的队列。

当打印机完成任务时，它将检查队列，以检查是否有剩余的任务要处理。

我们感兴趣的是学生等待他们的论文打印的平均时间。这等于任务在队列中等待的平均时间量

如果实验室中有 10 个学生，每人打印两次，则平均每小时有 20 个打印任务。在任何给定的秒，打印任务将被创建的机会是什么？

回答这个问题的方法是考虑任务与时间的比率，每小时 20 个任务意味着平均每 180 秒将有一个任务：

对于每一秒，我们可以通过生成1到 180 之间的随机数来模拟打印任务发生的机会。

如果数字是 180，我们说一个任务已经创建。请注意，可能会在一下子创建许多任务，或者需要等待一段时间才有任务。

这就是模拟的本质。你想模拟具实的情况就需要尽可能接近一般参数。

3.模拟流程

1.创建打印任务的队列，每个任务都有个时间戳。队列启动的时候为空。

2.每秒(currentSecond)：

• 是否创建新的打印任务？如果是，将 currentSecond作为时间戳添加到队列。
• 如果打印机不忙并且有任务在等待- 从打印机队列中删除一个任务并将其分配给打印机- 从 currentSecond中减去时间戳，以计算该任务的等待时间。- 将该任务的等待时间附件到列表中稍后处理。- 根据打印任务的页数，确定需要多少时间。
• 打印机需要一秒打印，所以得从该任务的所需的等待时间减去一秒。
• 如果任务已经完成，换句话说，所需的时间已经达到零，打印机空闲。

3.模拟完成后，从生成的等待时间列表中计算平均等待时间。

作业的等待时间：生成作业时，记录生成的时间戳； 开始打印时，当前时间减去生成时间即可

作业的打印时间：生成作业时，记录作业的页数；开始打印时，页数除以打印速度（页/秒）即可。

4.代码

from pythonds.basic.queue import Queue

import random

classPrinter:def__init__(self,ppm):
        self.pagerate = ppm #打印速度   页/分钟
        self.currentTask =None#打印任务
        self.timeRemaining =0#打印倒计时deftick(self):#打印倒计时 打印1秒 逐秒流逝if self.currentTask!=None:
            self.timeRemaining  = self.timeRemaining -1if self.timeRemaining <=0:
                self.currentTask =None#打印任务完成defbusy(self):if self.currentTask!=None:#正在打印当前任务returnTrueelse:returnFalsedefstartNext(self,newtask):
        self.currentTask = newtask
        self.timeRemaining = newtask.getPages()*60/self.pagerate #任务需要的打印时间 初始化倒计时 秒为单位classTask:def__init__(self,time):
         self.timestamp = time #生成该打印任务的时间 生成时间戳
         self.pages = random.randrange(1,21)#打印任务的页数1-20页等概率出现defgetStamp(self):return self.timestamp
     
     defgetPages(self):return self.pages
     
     defwaitTime(self,currenttime):#任务等待时间return currenttime - self.timestamp

defnewPrintTask():
    num = random.randrange(1,181)#每秒 以 1/180的概率生成一个新任务if num ==180:#180出现的概率是 1/180returnTrueelse:returnFalsedefsimulation(numSeconds,pagesPerMinute):
    
    labprinter = Printer(pagesPerMinute)
    printQueue = Queue()
    waitingtimes =[]#每个任务的等待时间for currentSecond inrange(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)#%6.2f 6控制小数点前数字宽度 2是小数点后保留的位数#printQueue.size() 一小时过后 任务队列中还有多少未处理的任务 print("Average Wait %6.2f secs %3d tasks remaining."%(averageWait,printQueue.size()))