跳到主内容
芝麻园地

D02 · 预测 · 操作 · 解释结构选择

队列实验:按顺序批处理资料与观察环形回绕

批量检查中有一份失败,后面的资料就没处理;重试又把同一次消费重复算成成功。先分清任务身份、入队尝试和处理状态。

返回实战路线 →

先说明你的预测

  • WorkQueue 用 collections.deque 封装 FIFO。每个入队实例最多开始一次,状态依次为等待、处理中、成功或失败;失败后仍可消费后续项。
  • 显式重试创建新的 attempt ID,并保留与旧失败尝试的关联;不把它算成同一次消费。单进程顺序处理,仅检查样例并生成报告,不自动入库。
  • 环形队列是独立的固定容量模型:满队列不能覆盖等待项,空队列不能读出伪任务,头尾按容量回绕。它不是本期必写的通用容器。

这是确定性教学模型,状态检查只核对模型不变量,不检查你的预测答案、不执行 Python,也不证明掌握。模型操作次数与浏览器耗时、Python 实现成本分别理解。

受控数据结构模型

手动观察模型

每次操作只改变受控样例。这里不运行学生 Python、不读取磁盘,也不以操作次数或模型状态签发掌握证明。

单进程批处理:每次单步开始或结束一个尝试

一个逻辑任务可以有不同 attempt;新重试排到队尾。下一步始终继续最早等待项。

  1. attempt-1 · job-A · 等待 · 开始序号: — · 结束序号: —
  2. attempt-2 · job-B · 等待 · 开始序号: — · 结束序号: —
  3. attempt-3 · job-C · 等待 · 开始序号: — · 结束序号: —

独立环形队列模型

这里的 R 编号与上面的批处理任务独立。改变容量会清空环形样例。满/空时 head 都可能等于 tail,要结合 size。

head=0, tail=0, size=0, capacity=4

  1. [0] ∅ ← head ← tail
  2. [1] ∅
  3. [2] ∅
  4. [3] ∅

A、B、C 依次等待;B 预设检查失败。环形模型独立为空。 · 当前模型不变量: 一致

操作计数与模型范围

检查 FIFO 开始顺序、每个 attempt 一次、四态一致、重试身份及环形满空/占位关系;不是本地运行验收。

入队尝试
3
开始
0
已结束
0
失败
0
新重试
0
环形入队
0
环形出队
0
等待
3
处理中
0
环形占用
0

本地 deque 两端入队/出队通常 O(1),任务本身检查成本另算。模型计数只统计入队、开始、结束、失败、重试和环形操作;浏览器状态快照/界面复制成本不代表队列算法。

计数来自模型定义,不是浏览器耗时;模型为显示和保存状态产生的复制不计作底层容器操作。

本次执行轨迹(最多保留 40 条)

  1. A、B、C 依次等待;B 预设检查失败。环形模型独立为空。

这里只检查模型自身状态,未执行你的 Python,也不判断预测是否正确。

未检查或已失效

分级学习提示

提示是固定教学内容,使用情况会记入学习记录。

提示 1

记录每次入队的 attempt ID。相同业务任务重试时,应沿用旧 attempt 还是新建一次?

提示 2

把开始处理和结束处理分成两步。失败也是一种终态,不能让它阻止下一个等待项开始。

提示 3

检查开始顺序等于入队顺序、每个 attempt 只开始一次。环形下标用模运算,并用 size 区分 head==tail 时的满和空。

我的 Python 草稿

这里只保存和导出草稿,不运行代码,也不与起始工程同步。修改草稿、输入或策略后,原模型结果与自报记录会失效。

本机学习记录

只保存在当前浏览器,可导出;不跨设备同步,不证明掌握。F01 与六任务旧记录会迁移保留。

  • 已打开 D02: —
  • 模型检查: 未检查或已失效
  • 本地测试自报: —
  • 最高提示层级: 0/3
  • 已查看参考: —
  • 无帮助变式自报: —

到同一校园资料整理器中实现

from collections import deque

class WorkQueue:
    def __init__(self):
        self._waiting = deque()

    def enqueue(self, task):
        raise NotImplementedError

    def step(self, checker=None):
        raise NotImplementedError

独立快照在 M1 基础上只保留本实验的故障;M2 起始工程包含三个实验的待修部分。参考代码与自己的作品分开。

下载本实验起始工程

python check_environment.py
python -m unittest tests.test_d02 -v
python -m unittest discover -s tests -v

使用 Python 3.11+ 与标准库,在新目录解压后运行。起始包预期失败以包内逐项清单为准。测试通过的参考实现只证明材料可运行,自己的代码仍需真实执行。

独立变式

独立实现 challenges.run_print_queue(initial_jobs, during_first=()):让首项失败,处理中追加一项,再继续处理全部任务。自行补断言核对 FIFO、无漏项和失败后继续,并解释为何不该用撤销栈组织打印顺序。

python -m unittest tests.test_m2_variants -v

在 tests/test_student_counterexamples.py 中替换跳过占位,补自己的反例与解释。看过提示或参考的本次记录不会标记为无帮助完成。

成本与模型边界

本地 deque 两端入队/出队通常 O(1),任务本身检查成本另算。模型计数只统计入队、开始、结束、失败、重试和环形操作;浏览器状态快照/界面复制成本不代表队列算法。

参考解释与答案

查看参考解释(会记录使用)

FIFO 决定等待项开始的顺序,不保证每项成功。把一个 attempt 的四态与新重试分开,才能检查不重复消费。模型用头位置取下一个等待项;它不以数组复制开销证明高效出队,也不承诺信号量等待队列的调度规则。

下载本实验参考实现(答案) · 版本与来源摘要

课名索引与相关实验