事件模型

把事件抽象为偏序集中的元素,用转移映射和线性扩展描述它与扫描模型的交互;坐标、类型、载荷只是表示层。

标签 数学 / 事件 / 偏序 / 线性扩展 / 扫描线 / 模型

定义

固定状态空间 𝑆 与有限全序时间轴 𝑇={1,…,𝑁}。一个事件模型由

ℰ︀=(𝐸,⪯,𝑈,ℓ)

组成,其中:

  • 𝐸 是有限事件集;
  • ⪯ 是 𝐸 上的偏序,表示事件之间的先后约束;
  • 𝑈:𝐸×𝑆→𝑆 把事件作用到状态上;
  • ℓ:𝐸→𝑇 是线性扩展,把事件排到时间轴。

此时 𝑁=|𝐸|。事件 𝑒∈𝐸 的作用是转移 𝑢𝑒:𝑆→𝑆,𝑢𝑒(𝑍)=𝑈(𝑒,𝑍)。若 𝑒𝑡=ℓ−1(𝑡),则 𝑒𝑡 一般表示 𝑡 时刻的若干个操作构成的集合。

表示层

坐标、类型、载荷不是事件模型的必要部分。若给定坐标映射 𝜅:𝐸→𝐾,则事件点就是 𝜅(𝑒);它通过“坐标先后 + 同一坐标上的优先级”诱导 ⪯。类型与载荷只用于定义 𝑈。

因此,同一个事件集 𝐸 与偏序 ⪯ 可以有多种坐标表示;每种表示与一个线性扩展 ℓ 一起给出一个事件模型 (𝐸,⪯,𝑈,ℓ)。按 𝑥、时间或右端点排序,都是选择不同线性扩展的方式。

常见误解

  • 认为事件就是修改操作:事件是 𝐸 中的元素,𝑍↦𝑈(𝑒,𝑍) 才是它对应的转移。
  • 认为事件必须带坐标:坐标只是诱导事件顺序的一种表示;抽象事件只需要偏序位置。
  • 认为事件必须带类型和载荷:它们只是定义 𝑈 的数据。
  • 认为查询必须是事件:查询也可以在切点读取;若把查询建成事件,需要扩展接口以携带输出。
  • 认为同一坐标的事件不需要排序:仍需用优先级或编号得到线性扩展。
  • 认为事件模型只属于扫描线:它描述一般的离散事件调度;扫描线只是选取线性扩展的一种方式。
源码位置