离散时间事件模拟

似乎前面一次 scala 的课程上这个话题就有所涉猎,我们这里讨论一下其中设计的基本层次,然后探讨一下这种理念如何应用到其他的问题上。

原始的问题是:给定一个(数字)电路,如何模拟其行为。电路的基本组成原件包括线路和门,门是用来连接线路的基本单位,一般都知道三类逻辑运算:非门、与门和或门,它们实现的时候並非能立即反应输入的变化,而是存在一定的 delay,我们的模拟就是希望看到改变一个电路的输入以后需要多长时间我们会在输出上看到最终的结果。从这个角度来说,我们很可能需要至少 3 个层次上的抽象:

  • 模拟本身实际上是对一个事件队列进行处理,它提供了对事件进行处理的基本方法,比如时间的抽象,又比如注册一个事件以及将模拟进行下去(依次执行事件),事实上不同问题的模拟在这一层次上是共用的
  • 电路模拟的基本抽象,它包括线路和基本的门的实现,因为结果存在于线路上电信号的值,模拟研究的对象即这些输入输出线路上值的变化过程,因此这一层次上我们需要为线路提供一些行为(什么时候改变值或者读取这些值),以及注册这些行为的方法,也就是基本门电路对线路的操作(注册值发生变化时的行为)
  • 电路本身的抽象,通过门电路的组合,我们可以获得更加复杂的电路,这一层次上我们通过上层提供的 DSL 实现需要测试的电路

离散时间事件模拟本质上就是要维护一个事件的队列,依次调用每个事件即可,但是事件的出现一般是“相对”的,一个事件引起“一段时间以后”发生另一个事件,他们很少有“绝对”发生时间的需要,但是这并不是说后发生事件引发的事件一定在之前事件引发的事件之后,因此对事件的注册过程本身需要应对一个一般性的插入(而不仅仅是从尾部插入)的行为,实现上可以用:

  • 低效简单的链表做个队列,通过类似 binary/linear search 的策略找到合适的位置插入新的事件,每个事件是 Int, Action 的两元组,前者用来确定插入位置,后者可以认为是个零元函数
  • 更高效的策略大概是用一个 heap 来做优先级队列

Simulator 自己提供的 API 就是在这之上的注册函数,它自身维护一个 currentTime 状态,通过一个 register 函数在 currentTime + offset 位置上插入一个 Action,改变这个队列,然后通过 next/run 来执行队列里面的 actions,通常 next 是为了进行单位时间/单一行为模拟,将队列中小于等于 currentTime 的 actions 执行或者仅仅执行下一个行为,并改变 currentTime 到下个时刻;run 一般是反复执行 next(有些模拟可能会导致队列为空)。

在这层抽象以上就是对具体的 domain 进行的抽象:有一些什么东西应该设计成为状态对象?状态的迁移需要一些什么基本的 action?

  • 电路的状态其实无外于 true/false,其行为就是设置这个状态;存在的门电路起到了关联这些状态的作用,因此提供了额外的 Action 将设置状态这个行为从输入端传播到输出端
  • 又比如传染病模拟中,每个人自身的状态(健康,感染,免疫和死亡)以及其迁移获得的行为构成了这层抽象需要实现的主要问题

模拟的可视化可以认为是对某个 domain 模拟过程的一种 view,如果从 MVC 这个观点来看,Simulator 这层上实现了基本的 controller,到 domain 那层上实现了具体的 controller 和 model,可视化其实就是对 model 的 view:

  • 简单的 view 可以通过为状态设计一个额外的 action 在模拟的过程中实现:比如电路模拟我们一般需要知道每个线路状态的变化,实际操作中我们是在线路上放个探针用来测量电压的变化,因此简单的说如果每个线路对象自己拥有一组 Action,在状态改变时执行的话,探针无非就是为其添加一个显示状态的 action
  • 每个状态对象本身的 Action 一般是相对静态的情况下比较有用,如果是这些行为本身是动态的,这样可能不是太合适(有些行为必须能修改状态对象自身的 Action)
  • 更一般的做法是通过 simulator 执行一步,将状态对象的状态读出进行渲染,如果单个状态渲染比较费时,可能需要设置 dirty bit(这个可以作为对象自身的 action 来修改)然后仅对更新的对象重新渲染
流行病模拟
流行病模拟

——————
And he removed that day the he goats that were ringstraked and spotted, and all the she goats that were speckled and spotted, and every one that had some white in it, and all the brown among the sheep, and gave them into the hand of his sons.

Advertisements
离散时间事件模拟

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s