第四章 面向图形的编程
背景简介
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 面向图形编程的基础模型
最近在考虑是不是放假期间大家一起协作的时候采用一些源代码管理工具和持续集成工具来协助更好的完成工作，因为原来没有这方面的经验，所以要花点时间考虑一下持续集成工具可能带来的好处，下面是CodeHaus做的一个持续集成方面的工具的Feature Matrix，很全面，可以参考一下。
Continuous Integration Server Feature Matrix
关于各种快速排序算法改进的综合报告
快速排序算法是一种基于分治技术的重要的排序算法，自从它被发明以来，就受到了研究人员的广泛注意。多年以来，人们对这个基本算法进行了大量的改良。我搜集并查阅了一些相关的资料，在下文中对这些改进做出一些介绍。
一、基本的快速排序算法
快速排序算法是由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
准备综合一些资料写一篇Quicksort方面的介绍文章,搜集到了以下一些感觉不错的资料:
Quicksort From Wikipedia, the free encyclopedia.
Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, makes Θ(n log n) comparisons to sort n items. However, in the worst-case, it makes Θ(n2) comparisons. Typically, quicksort is significantly faster in practice than other O(n log n) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data it is possible to make design choices which minimize the possibility of requiring quadratic time.
- Quicksort or Samplesort Algorithm
- An elegant improvement of Quicksort
- Quicksort
- Quicksort algorithms with an early exit for sorted subfiles
- Data Structures and Algorithms: Quicksort
Visual Studio 2010 Concept IDE
刚看到这篇文章的时候还以为是MS官方的发文,没想仔细看一下到似乎只是一些fans写的文章(不过好像是高级fans^_^,连Allan Cooper都参与进来了),界面做的满清楚的,不过就是感觉太艳丽了.而且最关键的是,把若干个feature全部看完之后似乎没有什么特别的亮点,也都是现在一些已知甚至可以看到的东西,如果概念尚且如此,那实际又会有多少新想法呢?Eclipse发展到2010年不知道会是怎么样了…
这几天在做Agent的课程设计,这个MAS的原型是一个RSS的搜索引擎,我主要是做前端的一些东西,如用户界面等,比较麻烦的地方是Agent与web环境的交互,尤其是并发的问题.
由于后端的搜索同学还没有做好,所以要测前端的界面的时候要Mock一些数据来显示.由于同样是搜索,最先想到的就是调用Google的API获取一些数据到前端来显示.其实满早以前就试玩过一下Google的API,所以Licence Key什么都已经有了,现在只要下载一下api的sdk就可以了.不过发现Google的API网站居然下载不了(后面使用的yahoo的api sdk也同样下载不了),考虑到是否有可能被Great Firewall给禁止的问题,用了一个香港的代理服务器,果然可以了,sigh~
不过事情还没有结束,尽管下载了Google的API,但是用的时候发现报Connection Timeout的异常,连不上Google的Web Service,就连Google的API demo也一样连不上,怀疑是不是又被GFW给喀嚓了,于是就放弃了这个打算.不过到了晚上看新闻的时候,突然想起来yahoo也公布了自己的api给开发者使用,就又有了试一试的想法.yahoo的api和google大致相同(我只用过java的),所以很快就上手了,三下五除二就搞定了一段简单的搜索代码,效果看上去还不错呵呵,就是有一个问题,怎么每次得到的都是10个搜索结果??
这段在做一个Agent的原型系统,希望能够做成一个rss的搜索引擎.Agent的平台用的是JADE,现在已经出到3.3版了,应该算满成熟了吧,不过我使用的过程中发现似乎还是有bug.在创建Agent容器的时候发生错误:ContainerController containerController = runtime.createAgentContainer(profile);
一直想不出这里为什么会找不到主容器,看了JADE的源代码,发现这里可以把日志输出到文件,仔细看了一下才发现原来是JADE的url的解析似乎有些问题,目录中包含的空格被当作了url的分隔符~,解决方法:将目录中的空格去掉^_^
jade.core.IMTPException: RMI exception [nested RemoteException occurred in server thread; nested exception is:
java.rmi.UnmarshalException: error unmarshalling arguments; nested exception is:
java.net.MalformedURLException: no protocol: 5.5/webapps/agent/WEB-INF/classes/]
摘自iBATIS SQL Maps 开发指南
Clinton Begin 著
刘 涛 译
Map类型输入参数
假如没必要写一个Java Bean作为参数，而要传入的参数又不只一个时，可以使用Map类（如HashMap，TreeMap等）作为参数对象。例如：
<statement id=”insertProduct” parameterClass=”java.util.Map”>
select * from PRODUCT
where PRD_CAT_ID = #catId#
and PRD_CODE = #code#
</statement>
可以注意到mapped statement的形式完全没有区别！上面的例子中，如果把Map对象作为输入参数去调用mapped statement，Map对象必须包含键值“catId”和“code”。键值引用的对象必须是合适的类型，以上面的例子来说，必须是Integer和String。Result Map（参见以下章节）也支持使用Map类型作为结果参数。要获得更多信息，请参见“Result Map”和“使用SQL Map API编程”部分。
Map类型也可以使用别名。例如，可以用“map”来代替“java.util.Map”。这些别名参见下面的“支持Parameter Map和Result Map的数据类型”表格。
复杂类型集合的属性
Result Map还可以装入代表复杂类型对象集合（List）的属性，用以表示在数据库中相互关系为多对多或一对多的数据。拥有集合属性的类作为“一”的一方，而在集合中的对象作为“多”的一方。用来装入对象集合的mapped statement和上面例子一样。唯一的不同是，让SQL Map架构装入复杂类型集合（List）的业务对象的属性必须是java.util.List或java.util.Collection类型。例如，如果Category拥有Product对象的List，mapped-statement就像下面的例子（假设Category类有一个叫productList的属性，类型是java.util.List）：
<resultMap id=”get-category-result” class=”com.ibatis.example.Category”>
<result property=”id” column=”CAT_ID”/>
<result property=”description” column=”CAT_DESCRIPTION”/>
<result property=”productList” column=”CAT_ID” select=” getProductsByCatId”/>
</resultMap>
<resultMap id=”get-product-result” class=”com.ibatis.example.Product”>
<result property=”id” column=”PRD_ID”/>
<result property=”description” column=”PRD_DESCRIPTION”/>
</resultMap>
<statement id=”getCategory” parameterClass=”int” resultMap=”get-category-result”>
select * from CATEGORY where CAT_ID = #value#
</statement>
<statement id=”getProductsByCatId” parameterClass=”int” resultMap=”get-product-result”>
select * from PRODUCT where PRD_CAT_ID = #value#
</statement>
订阅
阅读列表
