[Android] Otto源码简析

用例

本文主要按照如下例子展开:

初始化

首先来看看Bus bus = new Bus()这一句,对应的源码如下所示:

默认参数为enforcer = ThreadEnforcer.MAIN,identifier = DEFAULT_IDENTIFIER,handlerFinder = HandlerFinder.ANNOTATED。我们来看看这些参数是什么意思。

ThreadEnforcer

ThreadEnforcer是一个接口,enforce()方法用于检查当前线程是否为指定的线程类型:

不带参数的构造函数bus()使用默认的ThreadEnforcer.MAIN,表示enforce()方法必须在主线程上执行。

identifier

identifier仅为bus的名字,debug用。

handlerFinder

HandlerFinder用于在注册/反注册的时候查找Subscriber和Producer,后文会对其展开源码级别的解析。不带参数的构造函数bus()使用默认的HandlerFinder.ANNOTATED,表示使用注解来进行查找。

除上述以外,bus类还有两个成员变量handlersByType和producersByType:

分别用于通过event的类型(class类型)来查找event handle和event producer。

注册/反注册事件

如下所示,要A成为订阅者订阅AnswerAvailableEvent,只需将其注册到bus,然后使用@Subscribe注解标记回调方法即可。回调方法要求可见性为public,有且仅有一个参数,类型为订阅的event。

@Subscribe

首先看一下@Subscribe注解:

RetentionPolicy.RUNTIME表示它是运行时的注解,ElementType.METHOD表示用于注解方法。

bus.register

再看一下register流程:

总的来说register做了三件事情:触发新的Producer;注册新的event-handler关系;触发旧的Producer。另外有两点要注意一下:

  • 由于在一般使用场景下,发送/处理event远比注册/反注册操作频繁,所以在保证线程安全的情况下,使用CopyOnWriteArraySet作为保存event和handler的容器,可以大大提高效率。
    CopyOnWrite容器在读的时候不会加锁,写的时候先复制一份,写完再替换原容器。如果容器正在写操作时发生了读操作(或者正在读的时候发生了写操作),读操作的对象为容器的快照(snapshot)。
  • 由于register方法没有加锁,所以在3-1中,尽管已经检查了handlers是否存在,但仍需使用putIfAbsent来保存handler。

EventProducer和EventHandler

注意到bus通过HandlerFinder来查找object上的producer和subscriber,接下来看一下HandlerFinder的实现:

其中findAllProducers方法返回某event type对应的EventProducer,findAllSubscribers返回某event type对应的EventHandler集合。先看一下EventProducer和EventHandler。

EventProducer是一个producer方法的包装类,源码如下:

其中produceEvent方法用于获得event。可以看出为什么Otto要求produce函数不能有参数。

与EventProducer类似,EventHandler是一个event handler方法(事件回调)的包装类,源码如下:

其中handleEvent方法用于在object上调用handle方法(事件回调),传入event对象。可以看出为什么Otto要求event handler函数仅能有一个参数。

dispatchProducerResultToHandler

dispatchProducerResultToHandler方法用于将Producer产生的event分发给对应的handler。源码如下所示:

逻辑比较简单,主要是使用了Producer的produceEvent()方法获得event对象后,调用EventHandler的handleEvent()方法。

bus.unregister

Bus类的unregister方法用于解除目标对象和bus之间的关联关系,包括对象上的producer方法,subscriber方法,源码如下所示:

投递事件

一次简单的事件投递操作如下所示:

我们来看一下post方法的源码实现:

注意几点:

  • 发送一个Event时,订阅了Event父类的Subscriber方法也会被调用。
  • 事件会被放到调用者所在线程的队列里依次分发。

下面分点进行详述。

flattenHierarchy

进行post操作时,首先会通过flattenHierarchy方法获得event的父类或者接口:

从上可知flattenHierarchy()通过getClassesFor()利用深度优先遍历导出了concreteClass的所有父类。

Dispatch Queue

通过post方法投递的event首先会放在当前线程所在的Dispatch Queue中,然后依次分发。Bus类有如下成员属性:

eventsToDispatch是一个ThreadLocal对象,通过initialValue()方法,eventsToDispatch每次在新的线程上调用的时候都会生成新的ConcurrentLinkedQueue实例。event是通过enqueueEvent(event, wrapper)方法放到queue中的,下面看看enqueueEvent()的实现:

offer()方法会会将EventWithHandler对象放到当前线程的queue的尾部。offer方法和add方法的区别在于,当无法插入(例如空间不够)的情况发生时会发挥false,热不是抛出异常。EventWithHandler类对event和handler的关系进行了简单的包装,实现如下:

接下来看看dispatchQueuedEvents方法的实现:

值得注意的是,所有subscribe方法抛出的异常都会在这里捕获,捕获到异常以后event分发过程即停止,直到下一次在该线程上调用post为止。

结构图

综上,Otto的总体结构可用下图表示:

根据输入历史进行智能提示的一种简单解决方案的python实现

需求

假设某个时间段内输入历史为:

现用户输入a

系统应自动提示下一个用户可能输入的字母ab或者c

解决方案

这个问题可以简化成一个排序问题。对用户的每个输入历史进行权重计算,最后按权重排序,输出排序高的项。

关键在于怎么计算这个权重。

权重计算考虑的因素有以下几个:

  1. 因子的组成
  2. 因子的权重计算
  3. 各因子的权重如何组合成总权重

这里考虑3种因子:

  1. 出现的次数
  2. 出现的时间
  3. 是否连续出现

出现的次数

设为 occ_w, occ_w=该项在统计的历史中出现的次数

出现的时间

设为 pos_w, pos_w=(该项在统计历史中出现的位置/总统计数量)^2

是否连续出现

设为 ctu_w, 如果上一个项跟本项相同,则ctu_w=上一项的总权重/2。否则ctu_w=0

设总权重为w, w = occ_w + pos_w + ctu_w

实现

参考以下python代码:

ps:没有跟其他方法进行效果对比,纯做着玩。

用python编写1024游戏(4)

上一篇blog,我们来用python实现ai版1024游戏。


如前文所述,关键在于 获得最优滑动方向 这一步。整理一下思路:

此方法会调用一个用递归实现的深度优先搜索:

直接将其翻译成python代码:

其中 evaluation_func 是关键。如何定义这个函数呢?前文提到:

其中 H(x) 是评估函数。我们要思考究竟是什么因素影响了当前的局面,什么才算对自己有利。

这里这里的讨论可以总结出以下两点:

  • 最大值尽量靠在边角
  • 尽可能地沿着某个方向呈等比数列排列

于是我们可以这样设计:

各种因子的实现为:






递归深度为2时,运行一次大概要4-5min。当我设置递归深度为1时,进行了n次实验(n>50),胜率大概在50%左右。跟这里提及的算法效果比起来简直一个天上一个地下。

如何设计更好的评估函数呢?如何制定更完善的搜索策略呢?这有点超出我目前的能力范围了。。。

完整代码我放到Gist上,如下所示:

用python编写1024游戏(3)

这篇blog后,我们来尝试实现ai版的1024游戏。

背景

先来认识两个概念:树状搜索(Tree-Searching)和评价函数(Evaluate Function)

树状搜索

以象棋为例子、下棋的过程可以看作是棋局变化的过程。假设某时刻某个棋局,接下来可以移动棋子的方式有k种,每种移动方式会导致另外一种棋局。故整个下棋的过程可以用一棵n叉树来描述。目前的局面称为“根局面”(Root Position)或“根结点”(Root Node),后续分支称为“后续局面”(Successor Position)或“后续结点”(Successor Nodes)。

理论上可以从最初的局面开始生成n叉树,直至所有叶子节点满足游戏结束的条件为止,但随着生成层次增加,计算的次数迅速上升,往往会超出当前应用场景的接受范围。所以在一些复杂的游戏当中,会对搜索层次进行限制。同时,可以对某些特定算法进行“剪枝”优化,根据某些条件终止当前路径的搜索以减少分支数。

评估函数

假设当前局面对应的n叉树已经生成,如何选择对自己最有利的下一步呢?在此我们引入一个评估函数,该函数输入一个局面,返回对该局面的评估值,表示当前路径下可以获得的优势。我们对下一步所有可能出现的情况进行评估,然后根据评估值最大的局面来走棋。

注意到某局面的评估值依赖于下一步的所有可能出现的局面的评估值(是它们的和),这些可能出现的局面又依赖于在下一步可能出现的局面的评估值。所以我们需要从叶子节点开始计算评估值,然后回溯到顶层的同时更新父节点的评估值。

思路

首先,很明显,玩1024的过程可以用一棵n叉树来描述。游戏状态的变化按照规则:

设棋盘大小为4*4, 每一回合的平均空格数为4*4/2,大部分回合都可以朝4个方向滑动,那么随着搜索层数的增长,节点的个数如下增长:

仅四层节点个数便达到百万级别(我没算错的话),所以我们必须采用启发式搜索。


接下来我们大致写出整个ai游戏过程:

具体其中的 ai下棋 过程:

用循环和判断语句描述一下:


关键在 获得最优滑动方向 这一步。具体化一下:

其中 评估当前局面 思路如下所示:

这是一个深度优先搜索,可以用递归或者栈来实现,后续文章会有实例代码。


注意到 当前有意义的滑动方向 这一步。如何获得这个方向序列呢?我们来思考一下。“局面改变”是指:

于是我们可以获得两个判断“可移动”的条件


接下来观察 计算评估函数值部分。设评估值为H, 影响因子(决定评估值得因素)的值为A, B, C…,它们的权重为a, b, c, …,则有:

可以写成:

其中x代表当前局面。

我们暂时简单地设计一些影响因子函数,例如“当前局面的剩余空格数”,“当前累计的总分”,“形成可组合的对数”等等。然后根据实验来调整权重。


好了,说完思路,接下来将采用python实现。

用python编写1024游戏 (2)

续上篇文章,我们来一步步实现1024游戏。

总体设计

考虑到实现的难度和效率,改进了一下整体思路:

首先直接把它翻译成python代码:

设计数据结构

然后设计一下用到的数据结构:

由于我用的python版本没有enum类型,所以用class代替。

这里的棋盘类我使用一维数组来作为内部存储实现。要注意get和set方法中坐标到下标的换算方式。

其中:

是用来判断棋盘边界的。

实现

接下来是几个关键函数的实现:

随机放置2或4

这个函数会随着空值元素减少效率变低,应该有优化的算法。其中的0.1控制着2和4出现的比例。

检测当前棋盘的状态是否可变

改变棋盘状态

由于滑动的方向有四个,各个方向的处理办法都不一样。留意到上下、左右可以成组,组内操作的方向是反的。但组间的操作却是转置的。

考虑到棋盘本身可以看做一个矩阵,可以用一个线性变换将棋盘统一到某一方向,然后应用同一种操作,然后再变换回来。这样子虽然避免了重复的分支操作,但是程序的复杂度上升,效率也受到影响。

换一个思路,我们尝试提取不同方向下的不同点:定位和遍历。例如向左滑动和向右滑动,它们的定位方法是一样的,但是遍历方向相反。向下和向上滑动的遍历方向也是相反的,定位方法一样。向左滑动和向上滑动的遍历方向一样,但是定位方法确实相反的(一个i行j列,一个j行i列。于是我们对上述两种操作再针对不同滑动方向赋予不同的实现,从而使操作得到统一。

完整代码

代码放在了Github Gist上,如下所示:

用python编写1024游戏 (1)

我们从整体到局部地设计这个游戏。

首先,整个游戏过程可以简化如下:

再想具体一点,可以变成这样:

思考一下 进行 这一步,可以变成:

改写一下,加上判断条件,如下:

具体一下随机出现一个数字这一步,有:

再思考一下滑动这一步,有:

再具体思考一下更改棋盘状态这一步,可得:

其中序列中元素合并步骤具体为:

注意这一步在具体实现时可以同时进行。具体如下:

其中计分的规则是:

回到一开始判断未结束步骤,具体地:

初始化步骤具体为:

综上,可以写出整体的游戏设计思路:

好了,说完思路,接下来将采用python实现。

简单的溯源系统框架

需求

师兄开会回来,传达了上级的精神和需求:我们要做溯源系统,产品在生产线上流转的信息都要保留下来,并且在生产线上的任意一个环节都可以查看到之前的所有溯源信息。于是,经讨论和研究,我们勾勒出了一个溯源系统的原型。

思路

溯源是指产品的溯源。产品的溯源信息可以理解成产品从溯源路径的起点到终点之间经过的各个环节的信息的集合。可以用下图表示:

flow1

如图,产品在经过“大棚”、“冷库”和“运输车”时,产品性质会发变化,新的溯源信息会产生。可以这样想象:每个单位的产品(某一件或者某一批)携带着一个溯源信息栈,每经过一个“溯源控制点”,控制点就会产生“溯源信息”并将其放到信息栈中。在任意时刻,只需将栈按顺序pop出,即可从近到远地获取到产品的溯源信息。如下图所示:

flow2

粒度缩小一点,如下图所示,cp1~cp4为生产流程中的控制点:

flow3

于是,我们可以大致勾勒出该溯源系统的原型。

原型

实体关系

实体关系图如下所示:

实体

  • Product:产品实体,代表一个单位的产品,关联多个ProductionFlow。
  • ProductionFlow:由多个ControlPoint组成,代表着一种工序,对应多个产品。
  • ControlPoint:代表可以产生溯源信息的“点”,按顺序排列,组成工序。
  • ControlPointInfo:ControlPoint产生的数据实体。
  • ControlPointInfoStack:跟某个产品绑定在一起的承载ControlPointInfo的数据结构。

业务流程

(待补充)

时序图如下所示: