/**
* @author : ahuaxuan
* @date 2009-10-27
*/
很早之前(应该是一年以前),ahuaxuan在用dfa实现文字过滤一文中使用确定有限自动机实现了词典的高速查询。其实在当时那段时间里,由于对状态机有了一定的研究,ahuaxuan也触类旁通的理解了工作流引擎的核心体制。于是当时就用python写了一个小巧的工作流引擎的示例,在这之前ahuaxuan没有看过任何工作流引擎的实现,该实现纯属思维的自我延伸。
现在我来说说我的实现。
状态机的本质是状态的迁移,即从A状态+某个动作===》B状态。到这里我们还要来看看这张图。
从这张图中我们可以看到,状态(大写字母)+动作(小写字母)可以到达新的状态。那么对于程序员来说,我们要做的就是将这种机制用程序表达出来。比如说我们最常想到的是什么?矩阵!
这很好理解,但是对于工作流引擎来说,由于状态的迁移涉及到:当前状态+动作+条件===》新状态。
所以用二维的矩阵无法表示出这种逻辑。那么我们可以将矩阵中的元素替换为条件数组。
这样,我们可以通过当前状态+动作得到一个条件数组,然后再遍历这个条件数组,条件数组中的元素即是条件和满足条件的下一个状态(虽然本质上是一个三维数组,但是在这里还是看成矩阵+数组元素比较符合逻辑)。
这里需要画一个图,一个矩阵,矩阵中的元素是一个条件数组
没错,这是一种方案,但是这里有一个问题,那就是每次做状态迁移的时候,我们必须知道某个状态在矩阵一维上的index,已经某个动作在矩阵二维上的index.有了这两个index我们才能得到条件数组。所以这里还有一个繁琐的转换操作操作。来看一段伪代码:
conditions = matrix[getStatusIndex[‘A’], getActionIndex[‘a’]]
For condiction in conditions:
If condition match input:
Return Condition.nextStatus
核心流程大概就是这样,当
那么除了矩阵这种数据结构,我们还有其他的数据结构可以用来表示: “当前状态+动作+条件===》新状态”吗。
当然有,那就是使用树结构。在了解了三维数组的实现之后,再来看树实现,应该和容易了,那就直接上图, 将上图的矩阵转换成树结构之后,我们可以得到如下的树结构。
那现在我们来审视一下现在的问题,打个比方,我们现在手里有两张牌,一张是状态A,一张是动作a,我们如何通过这两种牌来得到条件集合呢,最简单的方法是首先遍历第二层节点,找到A,然后再遍历A的子节点,找到a。通过两次for循环找到了条件集合,而条件集合中包含着下一个状态。
那么有没有更简单更快速的方式可以直接找到条件集合,而直接跳过两次遍历呢。有,ahuaxuan的想法是tree+hash.也就是通过A的hash值,我们可以直接找到tree上的A节点。然后再通过a的hash值,我们可以直接找到A的子中的a节点。得到a节点之后我们就可以条件集合。那么我们可以用什么样的数据结构来实现一个这样的模型呢。这里面有hash运算,那么我们首先选择HashMap来创建这么一颗树。
我们来看一下这个定义:
Map<String, Map<String, Map<String, List<Transition>>>> dfa。
那么我们如何根据A,和a来得到一个条件集合呢?
Dfa.get[“processName”].get[“A”].get[“a”]
通过这样的方式,我们就可以根据当前状态和当前的动作得到一个条件集合。然后遍历这个条件集合就是找到满足“输入“的条件,该条件会指向下一个状态。
我们来看一下代码实现:
首先我们来构造这么一个状态机:
private void constructDfa(List<WfProcess> processList) {
for (WfProcess pro : processList) {
Map<String, Map<String, List<Transition>>> pmap = new HashMap<String, Map<String,List<Transition>>>();
dfa.put(pro.getName(), pmap);
for (State sta : pro.getStates()) {
Map<String, List<Transition>> smap = new HashMap<String, List<Transition>>();
pmap.put(String.valueOf(sta.getName()), smap);
for (Action action : sta.getActions()) {
List<Transition> transitions = new ArrayList<Transition>();
for (String transName : action.getTransNames()) {
transitions.add(pro.getTransitions().get(transName));
}
smap.put(String.valueOf(action.getName()), transitions);
}
}
}
}
接着我们来看看如何根据这个状态机来做状态迁移:
public String getNextState(String processName, String stateId, String actionId, Map<String, String> conditions) {
List<Transition> transitions = dfa.get(processName).get(String.valueOf(stateId)).get(String.valueOf(actionId));
for (Transition trans : transitions) {
if (match(trans.getConditions(), conditions)) {
return trans.getToState();
}
}
StringBuilder sb = new StringBuilder();
sb.append("There is no state for process : ").append(processName);
sb.append(", stateId : ").append(stateId);
sb.append(", actionId : ").append(actionId);
sb.append(", conditions : ").append(conditions);
throw new WorkFlowStateException(sb.toString());
}
通过这种tree + hash的方式,我们可以很容易的进行状态的迁移,不需要那么多for循环。但是for循环确实有这样的实现。
今天早上下载了osworkflow的代码,稍微看了一下AbstractWorkflow的doAction方法。
发现osworkflow就是通过循环来实现状态的迁移的,比如说上图中树结构的状态可以用以下伪代码:
For state in states:
If state.name == inputStateName:
For action in state.actions:
If action.name == inputActionName:
for transition in action.transitions:
…………………………………………………………………
通过这种方式,用户传入inputStateName和inputActionName, osworkflow得到了一组transition,并根据条件选择某个transition, 这样也实现了状态的转移。
从这里面可以看出,osworkflow是利用广度优先的原则,先找到符合条件的state,然后再找到符合条件的action,以此类推。
说到这里,通过这种状态机实现工作流引擎的方式基本的完全的,较为清晰的呈现在我们眼前了。
未完待续
- 大小: 16.2 KB
- 大小: 21.8 KB
分享到:
相关推荐
这项工作旨在确定氢氧化钠浓度对用生黏土制得的砖的干燥动力学的影响,并对该动力学进行建模。 结果表明,由于缺乏游离水,干燥动力学受水的扩散控制。 干燥时间随NaOH含量的增加而线性增加,而体积收缩率则下降,...
采用响应面法对由硅藻土制取水玻璃的工艺进行优化,进而选择最佳工艺参数在常压干燥下成功合成了SiO2气凝胶材料。试验结果表明:当碱硅比为3∶10,NaOH溶液浓度为10%,反应温度为90℃时,水玻璃模数测定值与SiO2溶出...
为比较不同材料所制成的多孔混凝土对有机污水净化的效果,采用了不同的材料来制作3种混凝土反应柱,一为普通硅酸盐水泥与粗砂制作的混凝土,二为复合硅酸盐水泥与粗砂制作的混凝土,三为复合硅酸盐水泥与红粘土制 作的...
android 源码学习. 资料部分来源于合法的互联网渠道收集和整理,供大家学习参考与交流。本人不对所涉及的版权问题或内容负法律责任。如有侵权,请通知本人删除。感谢CSDN官方提供大家交流的平台
android 源码学习. 资料部分来源于合法的互联网渠道收集和整理,供大家学习参考与交流。本人不对所涉及的版权问题或内容负法律责任。如有侵权,请通知本人删除。感谢CSDN官方提供大家交流的平台
android 源码学习. 资料部分来源于合法的互联网渠道收集和整理,供大家学习参考与交流。本人不对所涉及的版权问题或内容负法律责任。如有侵权,请通知本人删除。感谢CSDN官方提供大家交流的平台
C语言诞生于美国的贝尔实验室,由丹尼斯·里奇(Dennis MacAlistair Ritchie)以肯尼斯·蓝·汤普森(Kenneth Lane Thompson)设计的B语言为基础发展而来,在它的主体设计完成后,汤普森和里奇用它完全重写了UNIX,且随着UNIX的发展,c语言也得到了不断的完善。为了利于C语言的全面推广,许多专家学者和硬件厂商联合组成了C语言标准委员会,并在之后的1989年,诞生了第一个完备的C标准,简称“C89”,也就是“ANSI C”,截至2020年,最新的C语言标准为2018年6月发布的“C18”。 [5] C语言之所以命名为C,是因为C语言源自Ken Thompson发明的B语言,而B语言则源自BCPL语言。 1967年,剑桥大学的Martin Richards对CPL语言进行了简化,于是产生了BCPL(Basic Combined Programming Language)语言。
android 源码学习. 资料部分来源于合法的互联网渠道收集和整理,供大家学习参考与交流。本人不对所涉及的版权问题或内容负法律责任。如有侵权,请通知本人删除。感谢CSDN官方提供大家交流的平台
Google翻译.txt
汽车车灯检测机械臂设计.doc
网络购物中心项目源码.rar是一个压缩文件包,包含了一个基于Web技术的电子商务平台的全部源代码和相关资源。这个源码包旨在提供一个功能全面、界面友好的在线购物体验,它集成了商品浏览、搜索、购买、支付以及用户管理等核心电商功能。该项目采用了当下流行的开发框架和编程语言,比如使用HTML5, CSS3, JavaScript, PHP和MySQL数据库等技术,确保了网站的响应速度和跨浏览器兼容性。对于即将毕业的学生或者正在寻找实践项目的课程设计者来说,这个源码包是一个宝贵的资源。它不仅提供了一个实际应用的平台以供学习和研究,还允许用户根据需求进行定制和扩展,如添加新的功能模块或优化现有的代码结构。此外,项目文档详细记录了系统架构、功能实现和部署流程,为初学者提供了清晰的指引。通过分析和修改这份源码,学生可以深化对Web开发的理解,提高编程能力,并且有机会将理论知识转化为实际操作技能。此源码包适合作为计算机科学与技术、软件工程、信息技术等相关专业的毕业设计或课程设计项目,能够帮助学生在完成学业的同时,积累实战经验,增强就业竞争力。无论是作为学习的起点,还是作为未来职业生涯的一个跳板,网络购物
C语言诞生于美国的贝尔实验室,由丹尼斯·里奇(Dennis MacAlistair Ritchie)以肯尼斯·蓝·汤普森(Kenneth Lane Thompson)设计的B语言为基础发展而来,在它的主体设计完成后,汤普森和里奇用它完全重写了UNIX,且随着UNIX的发展,c语言也得到了不断的完善。为了利于C语言的全面推广,许多专家学者和硬件厂商联合组成了C语言标准委员会,并在之后的1989年,诞生了第一个完备的C标准,简称“C89”,也就是“ANSI C”,截至2020年,最新的C语言标准为2018年6月发布的“C18”。 [5] C语言之所以命名为C,是因为C语言源自Ken Thompson发明的B语言,而B语言则源自BCPL语言。 1967年,剑桥大学的Martin Richards对CPL语言进行了简化,于是产生了BCPL(Basic Combined Programming Language)语言。
这是Sora AI Videos的案例站点,使用此项目可以帮助你快速构建Sora AI的演示项目。
2015园林业务齐发展,区域拓展加速(20页).zip
机械臂的物体识别与抓取技术研究.pdf
1.版本:matlab2014/2019a/2021a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。
年终抽奖系统的模型,需要需要特殊定值,可以留言
1.版本:matlab2014/2019a/2021a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。
实战多种网站、电商数据爬虫。包含:淘宝商品、微信公众号、大众点评、闲鱼、阿里任务、百度贴吧、豆瓣电影、包图网、全景网、豆瓣音乐、某省药监局、搜狐新闻、机器学习文本采集、fofa资产采集、汽车之家️️️