niyue

Archive for June, 2005|Monthly archive page

Jbpm和Shark比较的feature list

In java, software on June 21, 2005 at 7:19 AM

前一段时间做的一个jbpm和shark的feature对比,今天整理笔记突然又看到这张记录纸了,so post here and drop the paper.作比较的时候Shark是1.0版本,而Jbpm是2.0版本(现在已经出到3.0了)

 

Shark

Jbpm

持久层 Shark自己的一个ORM的方案DODS,感觉不是很好 大名鼎鼎的 Hibernate(Jbpm2中使用的是Hibernate 2.1,Jbpm3种使用的是Hibernate3)
灵活性 Shark给人的感觉就是庞大,需要独立的运行一个工作量引擎服务 相对更加灵活,和OSWorkflow有的一比,也可以作为嵌入式的工作流引擎
后台管理 其实这点和上面一点有点相对应了,灵活性差其实是由于提供的功能太多的缘故,Shark自带了一个管理程序,界面虽然差了一点,但是功能满全面的 Jbpm2中没有提供后台的管理,Jbpm3还没怎么用过,好像是有的,不知道具体功能如何
流程定义的图形设计器 Shark使用的WfMC定义的XPDL语言定义流程,有一个JaWE来图形化定义流程,不过XPDL是在是看起来很难懂 Jbpm2中没有流程图形定义器,不过Jbpm3中已经有了,是基于Eclipse的一个插件,可以使用它定义Jbpm使用的JPDL,而且不仅是插件形式,后面还会出stand alone的版本
表单定制 这个Shark可以借助XPDL来进行表单定制,没看太懂就是了 Jbpm2不支持,原来看了Jbpm的MailList里面说在考虑Jbpm3中会加入这方面的内容,现在似乎没有看到还
用户模型 好像必须采用Shark中的用户模型 灵活性的体现,任意的用户模型。Jbpm3.1的roadmap里面考虑自带一个简单的用户模型供使用
异构系统交互 Shark可以开CORBA的服务,这个方面的功能很强大 只能通过Java和异构系统的交互似乎,Java能做的Jbpm就行
学习成本 Shark使用的XPDL很难看懂… 相对简单
文档 感觉是一片空白,给的那几个pdf都不顶什么用,用两三个小时就全部看完了,组织的不是很好而且。相对其他的方面,这个是最大的缺点了 挺全面的文档,一个chapter一个chapter的,看起来也方便

面向图形编程

In programming on June 21, 2005 at 4:11 AM
以下是对jbpm面向图形编程(Graph Oriented Programming)概念一文的摘要笔记。
第四章 面向图形的编程
背景简介
4.1 缺失的一环
比较workflow,bpm和orchestration之间的异同。并指出三者之间的共同点就是执行过程中存在着等待的状态。
java中也存在着执行过程的挂起(suspend),但是这三者需要的挂起能够被持续化。
java没有内建的机制支持挂起的持续化主要是由于冯诺依曼体系结构。
这三者对于这一问题有各自不同的解决办法。
4.2 图形表示与开发过程
在我们提出解决方案之前,我们需要提到一个概念:过程的图形化表示。
于是我们希望能够找到一个解决方案,在这个方案中,执行的挂起与商业过程的图形表示相关。大多数解决方案都是采用的有向图。
解决方案应该符合迭代式的开发过程。分析人员使用UML类图画出分析模型。开发者使用这一分析模型作为起始并将它转变成为设计模型。而后继续添加更多的技术细节的话就会形成一个实现。
4.3 传统方法
传统方法是使用一个由很多构造元素组成的过程定义语言。每个构造元素都有其图形表示和运行行为。传统方法的缺点:
独立的系统:传统的解决方案都是将workflow,bpm或者orchestration打包为一个独立的系统。这就导致了在自己的应用中很难使用并且难于管理。
不完备的过程定义语言:仅仅是对于流控来说,目前的所有的标准和解决方案都还存在着缺陷。
没有建模自由:将图形表示和运行行为进行绑定,使得开发者失去了建模的自由。
图形化编程:将图形表示和运行行为进行绑定,最终都会成为visual programming的某种形式。这是非常耗时的一种软件开发方法。
4.4 什么是面向图形的编程
面向图形编程是解决执行过程的挂起和持续化的一种技术。它的核心思想在于使用一个图形化表示的运行模型来对一般的强制式的编程做一个补充。图形也被看作成为软件的一部分,在软件运行时,图形的执行过程与强制式编程的软件的运行过程进行了耦合。
这种可执行的过程图是由结点和变迁组成的。变迁有方向,并在图中连接两个结点。这种图基本可以看作是一个状态自动机,但是对于并发的执行路径它有着更好的支持。
这里使用token来表示执行路径的执行,后面介绍了一下在这个模型中token是如何表示图的执行的。其实我理解这里就是一种Petri网的应用,讲的满多的,具体可以看看Petri网方面的一些资料就和容易理解了。
模型对于传统方法的解决:
简单的API+职责链模式:用以替换传统方法的独立系统
从结点继承(Inheriting from node??):给过程定义语言极大的灵活性
添加“不可见的”action:给商业过程分析人员提供建模的自由
过程开发循环:替代图形化编程
4.5 面向图形编程的基础模型
Graph Oriented Programming as a building block

持续集成工具比较

In management, programming, software on June 11, 2005 at 2:12 AM

最近在考虑是不是放假期间大家一起协作的时候采用一些源代码管理工具和持续集成工具来协助更好的完成工作,因为原来没有这方面的经验,所以要花点时间考虑一下持续集成工具可能带来的好处,下面是CodeHaus做的一个持续集成方面的工具的Feature Matrix,很全面,可以参考一下。

Continuous Integration Server Feature Matrix

关于各种快速排序算法改进的综合报告

In programming on June 7, 2005 at 12:03 AM

关于各种快速排序算法改进的综合报告

快速排序算法是一种基于分治技术的重要的排序算法,自从它被发明以来,就受到了研究人员的广泛注意。多年以来,人们对这个基本算法进行了大量的改良。我搜集并查阅了一些相关的资料,在下文中对这些改进做出一些介绍。

一、基本的快速排序算法
快速排序算法是由C.A.R. Hoare在1961年发明的一种内排序算法,其大致思想如下[5]:
首先,在要排序的序列a中选取一个中轴值,而后将a分区成为两个部分,左边的部分b中的元素均小于或者等于中轴值,右边的部分c的元素均大于或等于中轴值(分)。而后通过递归调用快速排序的过程分别对这两个部分进行排序(治)。最后将这两部分产生的结果合并即可得到最后的排序序列(合)。
给n个数进行排序时,它平均要做出Θ(nlogn)次的比较,而在最坏的情况下则需要 Θ(n^2)次比较。不过一般来说,在实际上,快速排序算法要显著的快于其他的Θ(nlogn)的算法,主要是由于其内层循环在大多数设计中都能够很有效的实现,并且这一算法可以根据实际的数据在设计上做出改进以使得最坏情况发生的概率尽量减小。[3]

二、快速排序算法的几种改进
1. 三平均分区法[1][9]
关于这一改进的最简单的描述大概是这样的:与一般的快速排序方法不同,它并不是选择待排数组的第一个数作为中轴,而是选用待排数组最左边、最右边和最中间的三个元素的中间值作为中轴。这一改进对于原来的快速排序算法来说,主要有两点优势[1]:
(1) 首先,它使得最坏情况发生的几率减小了。
(2) 其次,未改进的快速排序算法为了防止比较时数组越界,在最后要设置一个哨点。如果在分区排序时,中间的这个元素(也即中轴)是与最右边数过来第二个元素进行交换的话,那么就可以省略与这一哨点值的比较。
关于这一改进还有不同的说法,或者说关于这一改进还有更进一步的改进,在继续的改进中不仅仅是为了选择更好的中轴才进行左中右三个元素的的比较,它同时将这三个数排好序后按照其顺序放回待排数组,这样就能够保证一个长度为n的待排数组在分区之后最长的子分区的长度为n-2,而不是原来的n-1。通过这一技巧,能使得算法的运行时间减少5%左右[9]。
对于三平均分区法还可以进一步扩展,在选取中轴值时,可以从由左中右三个中选取扩大到五个元素中或者更多元素中选取,一般的,会有(2t+1)平均分区法(median-of-(2t+1),三平均分区法英文为median-of-three)。在[9]中有对(2t+1)平均分区法改进的详细分析,不过文章比较长,读起来也比较困难,所以我就看了个开头。里面对三平均分区法也做了详细的分析,并做出了理论的一个估算,其平均复杂度为 ,小于上面所说的一般的快速排序算法的平均复杂度 [9]。

2. 根据分区大小调整算法[7][8]
这一方面的改进是针对快速排序算法的弱点进行的。快速排序对于小规模的数据集性能不是很好。可能有人认为可以忽略这个缺点不计,因为大多数排序都只要考虑大规模的适应性就行了。但是快速排序算法使用了分治技术,最终来说大的数据集都要分为小的数据集来进行处理。由此可以得到的改进就是,当数据集较小时,不必继续递归调用快速排序算法,而改为调用其他的对于小规模数据集处理能力较强的排序算法来完成。[7] Introsort就是这样的一种算法,它开始采用快速排序算法进行排序,当递归达到一定深度时就改为堆排序来处理。这样就克服了快速排序在小规模数据集处理中复杂的中轴选择,也确保了堆排序在最坏情况下O(n log n)的复杂度。[8]
另一种优化改进是当分区的规模达到一定小时,便停止快速排序算法。也即快速排序算法的最终产物是一个“几乎”排序完成的有序数列。数列中有部分元素并没有排到最终的有序序列的位置上,但是这种元素并不多。可以对这种“几乎”完成排序的数列使用插入排序算法进行排序以最终完成整个排序过程。因为插入排序对于这种“几乎”完成的排序数列有着接近线性的复杂度。这一改进被证明比持续使用快速排序算法要有效的多。
另一种快速排序的改进策略是在递归排序子分区的时候,总是选择优先排序那个最小的分区。这个选择能够更加有效的利用存储空间从而从整体上加速算法的执行。[7]

3. 不同的分区方案考虑[8]
对于快速排序算法来说,实际上大量的时间都消耗在了分区上面,因此一个好的分区实现是非常重要的。尤其是当要分区的所有的元素值都相等是,一般的快速排序算法就陷入了最坏的一种情况,也即反复的交换相同的元素并返回最差的中轴值。无论是任何数据集,只要它们中包含了很多相同的元素的话,这都是一个严重的问题,因为许多“底层”的分区都会变得完全一样。
对于这种情况的一种改进办法就是将分区分为三块而不是原来的两块:一块是小于中轴值的所有元素,一块是等于中轴值的所有元素,另一块是大于中轴值的所有元素。另一种简单的改进方法是,当分区完成后,如果发现最左和最右两个元素值相等的话就避免递归调用而采用其他的排序算法来完成。

4. 并行的快速排序[4][6]
由于快速排序算法是采用分治技术来进行实现的,这就使得它很容易能够在多台处理机上并行处理。
在大多数情况下,创建一个线程所需要的时间要远远大于两个元素比较和交换的时间,因此,快速排序的并行算法不可能为每个分区都创建一个新的线程。一般来说,会在实现代码中设定一个阀值,如果分区的元素数目多于该阀值的话,就创建一个新的线程来处理这个分区的排序,否则的话就进行递归调用来排序。[4][6]
下图就是一个并行快速排序算法伪代码,P0…n-1就是要排序的数组,s是并行算法中设定的阀值。

图 1 并行快速排序算法[4]
对于这一并行快速排序算法也有其改进。该算法的主要问题在于,分区的这一步骤总是要在子序列并行处理之前完成,这就限制了整个算法的并行程度。解决方法就是将分区这一步骤也并行处理。改进后的并行快速排序算法使用2n个指针来并行处理分区这一步骤,从而增加算法的并行程度。

三、总结
总的来说,对于快速排序算法的改进主要集中在三个方面[1]:
1 选取一个更好的中轴值
2 根据产生的子分区大小调整算法
3 不同的划分分区的方法
本文中主要介绍了其中的前两个方面,而第三个方面由于我没有找到足够的相关的资料所以介绍的较为简略。另外本文还加入了并行的快速算法的介绍,从另一个方面来介绍一下对于快速排序算法的可能的改进。

四、参考文献
[1] Roger L. Wainwright. Quicksort Algorithms with an early exit for sorted subfiles, 1987
[2] Anany Levitin 著, 潘彦 译. 算法设计与分析基础, 2004
[3] Quicksort from Wikipedia. http://en.wikipedia.org/wiki/Quick_sort
[4] Parallel Quicksort. http://www.osys.se/Archive/Papers/parallel-sort/node3.html
[5] Quicksort. http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/quick/quicken.htm
[6] Quicksort or Sample Sort Algorithm. http://www.netlib.org/utk/lsi/pcwLSI/text/node302.html
[7] Quicksort, http://www.fearme.com/misc/alg/node47.html#1242
[8] Quicksort, http://www.absoluteastronomy.com/encyclopedia/Q/Qu/Quicksort.htm
[9] H.-H. Chern and H.-K. Hwang. Transitional Behaviors of the Average Cost of Quick Sort with Median-of-(2t + 1), 2001