3.2队列的应用：打印任务-（Python进阶-数据结构与算法）课件

队列的应用：打印任务 数据结构与算法（Python版） ❖ 多人共享一台打印机 ， 采取“先到先服务 ”的队列策略来执行打印任务 ❖ 在这种设定下 ， 一个首要的问题就是： 这种打印作业系统的容量有多大？ 在能够接受的等待时间内，系统能容纳多少用户 以多高频率提交多少打印任务？ 数据结构与算法（Python版） 模拟算法：打印任务 00 ❖ 一个具体的实例配置如下： 一个实验室，在任意的一个小时内，大约有10名 学生在场，这一小时中，每人会发起2次左右的打印，每次1 ~20页 ❖ 打印机的性能是： 以草稿模式打印的话，每分钟10页， 以正常模式打印的话，打印质量好，但速度下降 为每分钟5页。 数据结构与算法（Python版） 模拟算法：打印任务 00 ❖ 问题是： 怎么设定打印机的模式 ， 让大家 都不会等太久的前提下尽量提高打印质量 ? ❖ 这是一个典型的决策支持问题 ， 但无法通 过规则直接计算 ❖ 我们要用一段程序来模拟这种打印任务场 景 ， 然后对程序运行结果进行分析 ， 以支 持对打印机模式设定的决策。 数据结构与算法（Python版） 模拟算法：打印任务 00 ❖ 首先对问题进行抽象 ， 确定相关的对象和 过程 抛弃那些对问题实质没有关系的学生性别、年龄 、打印机型号、打印内容、纸张大小等等众多细 节 数据结构与算法（Python版） 如何对问题建模？ 00 ❖ 对象：打印任务、 打印队列、打印机 打印任务的属性：提交时间、打印页数 打印队列的属性：具有FIFO性质的打印任务队列 打印机的属性：打印速度、是否忙 数据结构与算法（Python版） 如何对问题建模？ 00 ❖ 过程：生成和提交打印任务 确定生成概率：实例为每小时会有10个学生提交 的20个作业，这样，概率是每180秒会有1个作 业生成并提交，概率为每秒1/180。 确定打印页数：实例是1～20页， 那么就是1~ 20页之间概率相同。 数据结构与算法（Python版） 如何对问题进行建模？ 00 ❖ 过程：实施打印 当前的打印作业：正在打印的作业 打印结束倒计时：新作业开始打印时开始倒计时 ,回0表示打印完毕，可以处理下一个作业 ❖ 模拟时间： 统一的时间框架：以最小单位（秒）均匀流逝的 时间，设定结束时间 同步所有过程：在一个时间单位里，对生成打印 任务和实施打印两个过程各处理一次 数据结构与算法（Python版） 如何对问题进行建模？ 00 ❖ 创建打印队列对象 ❖ 时间按照秒的单位流逝 按照概率生成打印作业，加入打印队列 如果打印机空闲，且队列不空，则取出队首作业 打印，记录此作业等待时间 如果打印机忙，则按照打印速度进行1秒打印 如果当前作业打印完成，则打印机进入空闲 ❖ 时间用尽 ， 开始统计平均等待时间 数据结构与算法（Python版） 打印任务问题：模拟流程 00 ❖ 作业的等待时间 生成作业时，记录生成的时间戳 开始打印时，当前时间减去生成时间即可 ❖ 作业的打印时间 生成作业时，记录作业的页数 开始打印时，页数除以打印速度即可 数据结构与算法（Python版） 打印任务问题：模拟流程 00 00 打印任务问题： Python代码1 数据结构与算法（Python版） 打印新作业 打印1秒 任务倒计时 打印任务 打印速度 打印忙？ 打印任务问题： Python代码2 数据结构与算法（Python版） 1/180概率生成作业 00 生成时间戳 打印页数 等待时间 打印任务问题： Python代码3 00 数据结构与算法（Python版） 时间流逝 模拟 ❖ 按5PPM、 1小时的设定 ，模拟运行10次 总平均等待时间93.1秒，最长的平均等待164秒 ,最短的平均等待26秒 有3次模拟，还有作业没开始打印 数据结构与算法（Python版） 打印任务问题：运行和分析1 00 ❖ 提升打印速度到10PPM、 1小时的设定 总平均等待时间12秒，最长的平均等待35秒，最 短的平均等待0秒，就是一提交就打印了 而且，所有作业都打印了 数据结构与算法（Python版） 打印任务问题：运行和分析2 00 ❖ 为了对打印模式设置进行决策 ， 我们用模 拟程序来评估任务等待时间 通过两种情况模拟仿真结果的分析，我们认识到 如果有那么多学生要拿着打印好的程序源代码赶 去上课的话 那么，必须得牺牲打印质量，提高打印速度。 ❖ 模拟系统对现实的仿真 在不耗费现实资源的情况下——有时候真实的实验 是无法进行的 可以以不同的设定，反复多次模拟 来帮助我们进行决策。 数据结构与算法（Python版） 打印任务问题：讨论 00 ❖ 打印任务模拟程序还可以加进不同设定， 来进行更丰富的模拟 学生数量加倍了会怎么样？ 如果在周末，学生不需