随笔-14  评论-25  文章-1  trackbacks-0
  2006年6月7日
在一个项目里面有这么一个技术需求:
1.集合中元素个数,10M
2.根据上限和下限从一个Set中过滤出满足要求的元素集合.

实际这个是个很典型的技术要求, 之前的项目也遇见过,但是因为当时的类库不多, 都是直接手写实现的. 方式基本等同于第一个方式.

在这个过程中, 我写了四个方式, 基本记录到下面.
第一个方式:对Set进行迭代器遍历, 判断每个元素是否都在上限和下限范围中.如果满足则添加到结果集合中, 最后返回结果集合.
            测试效果:集合大小100K, 运算时间 3000ms+
过滤部分的逻辑如下:
 1     void filerSet(Set<BigDecimal> targetSet, String lower, String higher) {
 2         BigDecimal bdLower = new BigDecimal(Double.parseDouble(lower));
 3         BigDecimal bdHigher = new BigDecimal(Double.parseDouble(higher));
 4 
 5         Set<BigDecimal> returnSet = new HashSet<BigDecimal>();
 6         for (BigDecimal object : targetSet) {
 7             if (isInRange(object, bdLower, bdHigher)) {
 8                 returnSet.add(object);
 9             }
10         }
11     }
12 
13     private boolean isInRange(BigDecimal object, BigDecimal bdLower,
14             BigDecimal bdHigher) {
15         return object.compareTo(bdLower) >= 0
16                 && object.compareTo(bdHigher) <= 0;
17     }
第二个方式: 借助TreeSet, 原始集合进行排序, 然后直接subset.
            测试效果: 集合大小10M, 运算时间: 12000ms+(获得TreeSet) , 200ms(获得结果)
过滤部分的逻辑如下(非常繁琐):
  1     Set<BigDecimal> getSubSet(TreeSet<BigDecimal> targetSet, String lower,
  2             String higher) {
  3 
  4         BigDecimal bdLower = new BigDecimal(Double.parseDouble(lower));
  5         BigDecimal bdHigher = new BigDecimal(Double.parseDouble(higher));
  6 
  7         if ((bdHigher.compareTo(targetSet.first()) == -1)
  8                 || (bdLower.compareTo(targetSet.last()) == 1)) {
  9             return null;
 10         }
 11 
 12         boolean hasLower = targetSet.contains(bdLower);
 13         boolean hasHigher = targetSet.contains(bdHigher);
 14         if (hasLower) {
 15             if (hasHigher) {
 16                 System.out.println("get start:" + bdLower);
 17                 System.out.println("get end:" + bdHigher);
 18                 return targetSet.subSet(bdLower, true, bdHigher, true);
 19             } else {
 20                 BigDecimal newEnd = null;
 21                 System.out.println("get start:" + bdLower);
 22                 SortedSet<BigDecimal> returnSet = null;
 23                 if (bdHigher.compareTo(targetSet.last()) != -1) {
 24                     newEnd = targetSet.last();
 25                 } else {
 26                     SortedSet<BigDecimal> newTargetSet = targetSet
 27                             .tailSet(bdLower);
 28                     for (BigDecimal object : newTargetSet) {
 29                         if (object.compareTo(bdHigher) == 1) {
 30                             newEnd = object;
 31                             break;
 32                         } else if (object.compareTo(bdHigher) == 0) {
 33                             newEnd = object;
 34                             break;
 35                         }
 36                     }
 37                 }
 38                 returnSet = targetSet.subSet(bdLower, true, newEnd, true);
 39                 if (newEnd.compareTo(bdHigher) == 1) {
 40                     returnSet.remove(newEnd);
 41                 }
 42                 return returnSet;
 43             }
 44 
 45         } else {
 46             if (hasHigher) {
 47                 System.out.println("get end:" + bdHigher);
 48                 TreeSet<BigDecimal> newTargetSet = (TreeSet<BigDecimal>) targetSet
 49                         .headSet(bdHigher, true);
 50                 BigDecimal newStart = null;
 51                 SortedSet<BigDecimal> returnSet = null;
 52 
 53                 if (bdLower.compareTo(targetSet.first()) == -1) {
 54                     newStart = targetSet.first();
 55                 } else {
 56                     for (BigDecimal object : newTargetSet) {
 57                         if (object.compareTo(bdLower) != -1) {
 58                             newStart = object;
 59                             break;
 60                         }
 61                     }
 62                 }
 63                 returnSet = targetSet.subSet(newStart, true, bdHigher, true);
 64 
 65                 return returnSet;
 66             } else {
 67                 System.out.println("Not get start:" + bdLower);
 68                 System.out.println("Not get end:" + bdHigher);
 69                 BigDecimal newStart = null;
 70                 BigDecimal newEnd = null;
 71                 if (bdHigher.compareTo(targetSet.last()) != -1) {
 72                     newEnd = targetSet.last();
 73                 }
 74                 if (bdLower.compareTo(targetSet.first()) == -1) {
 75                     newStart = targetSet.first();
 76                 }
 77                 for (BigDecimal object : targetSet) {
 78                     if (newStart == null) {
 79                         if (object.compareTo(bdLower) != -1) {
 80                             newStart = object;
 81                             if (newEnd != null) {
 82                                 break;
 83                             }
 84                         }
 85                     }
 86 
 87                     if (newEnd == null) {
 88                         if (object.compareTo(bdHigher) != -1) {
 89                             newEnd = object;
 90                             if (newStart != null) {
 91                                 break;
 92                             }
 93                         }
 94                     }
 95                 }
 96 
 97                 if (newStart == null) {
 98                     if (newEnd == null) {
 99                         if ((bdHigher.compareTo(targetSet.first()) == -1)
100                                 || (bdLower.compareTo(targetSet.last()) == 1)) {
101                             return null;
102                         }
103                         return targetSet;
104                     } else {
105                         SortedSet<BigDecimal> newTargetSet = targetSet.headSet(
106                                 newEnd, true);
107                         if (newEnd.compareTo(bdHigher) == 1) {
108                             newTargetSet.remove(newEnd);
109                         }
110                         return newTargetSet;
111                     }
112                 } else {
113                     if (newEnd == null) {
114                         SortedSet<BigDecimal> newTargetSet = targetSet.tailSet(
115                                 newStart, true);
116                         return newTargetSet;
117                     } else {
118                         SortedSet<BigDecimal> newTargetSet = targetSet.subSet(
119                                 newStart, true, newEnd, true);
120                         if (newEnd.compareTo(bdHigher) == 1) {
121                             newTargetSet.remove(newEnd);
122                         }
123                         return newTargetSet;
124                     }
125                 }
126             }
127         }
128     }
第三种方式: 使用Apache Commons Collections, 直接对于原始Set进行filter.
            测试效果:集合大小10M,过滤结果1M, 运算时间: 1000ms+
过滤部分的代码如下:
 1 //过滤的主体逻辑
 2     void filterSet(Set<BigDecimal> targetSet, String lower, String higher) {
 3         final BigDecimal bdLower = new BigDecimal(Double.parseDouble(lower));
 4         final BigDecimal bdHigher = new BigDecimal(Double.parseDouble(higher));
 5 
 6         Predicate predicate = new Predicate() {
 7             public boolean evaluate(Object object) {
 8                 BigDecimal bDObject = (BigDecimal) object;
 9                 return bDObject.compareTo(bdLower) >= 0
10                         && bDObject.compareTo(bdHigher) <= 0;
11             }
12         };
13 
14         CollectionUtils.filter(targetSet, predicate);
15     }

第四种方式:使用Guava(google Collections), 直接对于原始Set进行Filter
            测试效果:集合大小10M,过滤结果1M, 运算时间: 100ms-
过滤部分的代码如下:
 1 //guava filter
 2 
 3     Set<BigDecimal> filterSet(Set<BigDecimal> targetSet, String lower,
 4             String higher) {
 5         final BigDecimal bdLower = new BigDecimal(Double.parseDouble(lower));
 6         final BigDecimal bdHigher = new BigDecimal(Double.parseDouble(higher));
 7 
 8         Set<BigDecimal> filterCollection = Sets.filter(targetSet,
 9                 new Predicate<BigDecimal>() {
10                     @Override
11                     public boolean apply(BigDecimal input) {
12                         BigDecimal bDObject = (BigDecimal) input;
13                         return bDObject.compareTo(bdLower) >= 0
14                                 && bDObject.compareTo(bdHigher) <= 0;
15                     }
16                 });
17 
18         return filterCollection;
19     }


四种方式对比如下:
第一种方式:  仅依赖于JAVA原生类库 遍历时间最慢, 代码量很小
第二种方式:  仅依赖于JAVA原生类库 遍历时间比较慢(主要慢在生成有序Set), 代码量最多
第三种方式:  依赖于Apache Commons Collections, 遍历时间比较快, 代码量很少
第四种方式:  依赖于Guava, 遍历时间最快, 代码量很少

基于目前个人的技术水平和视野, 第四种方式可能是最佳选择.

记录一下, 以后可能还会有更好的方案.




posted @ 2014-06-21 23:33 混沌中立 阅读(7223) | 评论 (10)编辑 收藏
在几年之前,在大学里面的时候,认为系统的架构设计,就像建筑设计一样,会把骨架搭成,然后有具体人员进行详细的开发.

在后来,工作中,慢慢有了一些变化,因为原先的想法不太切合实际,系统就是在变化之中的,如果固定了骨架,那就很难的敏捷面对变化.
所以,系统的架构设计,应该是面向接口的设计,确定各个部分之间的数据接口和方法接口.这样,即使有了变化,只要遵循接口的定义,就还是可以面对变化.


最近,又有了想法的变化.架构的设计,应该就是规则和规约的设计.设计出一系列,统一的,和谐的规则,在这些规则之前圈住的部分,实际就是系统的全貌.
接口的设计,实际只是规则和规约设计的一个部分.
架构的设计,不应该只是程序方面的事情,同时也包含了心理学方面和社会学方面的一些规则.例如:团队在面对变化时候,需要采用的规则和流程.
只有包含了这些非程序上的规则之后,才能保证架构风格的统一协调.


以上,是我对系统设计的想法的转变过程.记录于此,以供回溯.




posted @ 2009-09-02 10:53 混沌中立 阅读(209) | 评论 (0)编辑 收藏
面对着满屏幕的程序
是三年前,项目刚刚启动的时候,同事写的代码.
三年过去了,项目由第一期变成了第七期.

这段代码还是在这里,有个属性是list,其中每个cell都是一个长度18的String数组.
数组里面放置了所需要导出到页面table的内容.

现在要开始修改了,需要向页面的table中增加4列.
繁琐的让人要命的工作,需要跟踪这个循环,判断每个pattern下面,这个长度18的数组里面放了哪些内容.

好吧,对象化维护从数组开始,把数组对折,因为这个数组时一个比较数组,前面9个元素是之前的情况,后面9个事之后的情况.
用一个bean,放入两次就可以了.但是bean中,需要一个标志,标识是之前的情况还是之后的情况.

同时需要一个transform方法,把之前从几个来源过来的情况,变成bean的属性.
接下来需要一个values方法,把bean里面的属性直接按顺序转化成数组.
本期新增的4个属性,直接放入bean中就可以了.

这样原来很复杂的数组,就可以简单的用对象来解决.外部的接口完全没有变化.

维护程序,从把数组(特别是异型数组)对象化开始.

posted @ 2009-08-20 13:43 混沌中立 阅读(1305) | 评论 (1)编辑 收藏
这个小的project是前一个阶段,待业在家的时候,迷恋sudoku的时候,自己写来玩的。
正好当时在看Uncle Bob的《Agile Software Development: Principles, Patterns, and Practices》 (敏捷软件开发:原则、模式与实践),所以就按照自己对书中的一些概念和方法的理解,结合自己之前的开发经验写出来一段小的代码。

代码行数: < 900
类的个数: 18
抽象类的个数:2
工厂类的个数:1
包的个数:5

一些关于类和包作用的说明:
1.Cell:表示一个Cell,是一个游戏中的一个单元格。
  Cell主要由3个部分组成,Point,Value,Status.
2.Point:表示一个坐标,主要格式为:(2,3).
  !!!注意:由于个人比较懒,所以开始的错误被贯彻了下来。
  这个错误就是(2,3)表示的是由最左上的位置为坐标原点,第二行和第三列所确定的那个单元格。也就是纵坐标在前,横坐标在后了。
3.Value:表示一个值
4.Status:表示Cell的状态,只有两个状态,一个是NotSure,另一个是Sure.

5.AbstractCells:表示一些cell的集合,主要有三个子类
     BlockCells:表示一个由多个Cell组成的块,例如一个2*2由4个Cell组成的块,或者一个2*3由6个Cell组成的块
     HorizonCells:表示一个横行,即:从(0,0)到(0,n)坐标确定的所有Cell的集合。
     VerticalCells:表示一个纵行,即:从(0,0)到(n,0)坐标确定的所有Cell的集合。
6.AbstractPolicy:就是游戏的策略。
   这个主要表示的是:4*4的游戏,还是9*9的游戏。
   可以在以后对此类进行继承和扩展,例如16*16的游戏我就没有实现。
   主要扩展3个方法:
                  1)getValueRange,返回当前policy的value的个数。4*4的游戏的getValueRange返回的就应该是4。
          2)getStep:表示当前policy中相邻的两个BlockCells的坐标差。
          3)getIncrease:说不明白了:)(只可意会不可言传。)
7.Game:进行Policy的场所(我一直想抛弃这个类)
8.TestGame:游戏运行的地方,包括从PolicyFactory取得指定的Policy,设置输入输出文件的路径。
9.PolicyFactory:取得Policy的工厂。
    getPolicy(int x) :这个方法获得的是正方形的sudoku的策略。例如:4*4的,9*9,16*16。
    getPolicy(int x, int y):这个方法获得的是长方形的Sudoku的策略。例如:9*12的。


虽然是尽量避免bad code smell,但是由于能力有限,还是出现了一些不好的地方。
例如:之间的关联关系还是很多,而且很强;抽象的方法和抽象类的个数偏少等等。

里面实现了三个解决sudoku的方法:
1.在一个Cell中出现的Value,不会在和这个Cell处在同一个AbstractCells中的所有Cell中出现;
2.如果一个Cell中,所有可能出现的Value的个数为1,那么Cell的Value必然是这个最后的Value;
2.如果一个Value,如果在当前AbstractCells的所有其他的Cell中都不可能出现,那么它必然是最后一个Cell的Value。

附件1:src code
http://www.blogjava.net/Files/GandofYan/sudoku.rar
附件2:输入输出文件的example
http://www.blogjava.net/Files/GandofYan/temp.rar

posted @ 2006-07-13 16:19 混沌中立 阅读(2096) | 评论 (4)编辑 收藏
如同Tom DeMacro说的:无法控制的东西就不能管理,无法测量的东西就无法控制。
软件的度量对于设计者和开发者非常重要,之前只是对这些有一个简单的了解。今天看来,了解的还远远不够。
  • Cyclomatic Complexity (圈复杂性)
  • Response for Class (类的响应)
  • Weighted methods per class (每个类重量方法)
一个系统中的所有类的这三个度量能够说明这个系统的设计上的一些问题(不是全部),这三个度量越大越不好。
如果一个类这三个度量很高,证明了这个类需要重构了。

以第一个度量来说,有下面的一个表格:

CC Value

Risk

1-10

Low risk program

11-20

Moderate risk

21-50

High risk

>50

Most complex and highly unstable method


CC数值高,可以通过减少if else(switch case也算)判断来达到目的;
可以通过减少类与其他类的调用来减少RFC;
通过分割大方法和大类来达到减少WMPC.

而Uncle Bob和Jdepend的度量标准应该算是另一个度量系统。

  • 关系内聚性(H)
用包中的每个类平均的内部关系数目作为包内聚性的一种表示方式。用于表示包和它的所有类之间的关系。
H=(R+1)/N
R:包内类的关系数目(与包外部的类没有关系)
N:包内类的数量

  • Number of Classes (Cc)
被分析package的具体和抽象类(和接口)的数量,用于衡量package的可扩展性。

  • Afferent Couplings (Ca)
依赖于被分析package的其他package的数量,用于衡量pacakge的职责。
  • Efferent Couplings (Ce)
被分析package的类所依赖的其他package的数量,用于衡量package的独立性。
  • Abstractness (A)
被分析package中的抽象类和接口与所在package所有类数量的比例,取值范围为0-1。
A=Cc/N
  • Instability (I)
用于衡量package的不稳定性,取值范围为0-1。I=0表示最稳定,I=1表示最不稳定。
I=Ce/(Ce+Ca)
  • Distance (D)
          被分析package和理想曲线A+I=1的垂直距离,用于衡量package在稳定性和抽象性之间的平衡。理想          的package要么完全是抽象类和稳定(x=0,y=1),要么完全是具体类和不稳定(x=1,y=0)。
          取值范围为0-1,D=0表示完全符合理想标准,D=1表示package最大程度地偏离了理想标准。
          D = |A+I-1|/0.70710678
          注:0.70710678*0.70710678 =2,既为“根号2“

我认为D是一个综合的度量,架构和设计的改善可以通过D数值的减少来体现,反之就可以认为是设计和架构的退化。


读过http://javaboutique.internet.com/tutorials/metrics/index.html之后的一些想法

另一篇中文的内容相近的文章可以参考http://www.jdon.com/artichect/coupling.htm

不过第二篇的中文文章中间关于Cyclomatic Complexity,有一个情况遗漏了
public void findApplications(String id, String name){

if(id!=null && name!=null) {
//do something
}else{
//do something
}
}
这种情况的CC不是2+1,而是2+1+1,依据是公式(1)。公式(2)应该是公式(1)的简化版。
Cyclomatic ComplexityCC) = no of decision points + no of logical operations +1        (1)

Cyclomatic Complexity (CC) = number of decision points +1 (2)

参考了JDepend的参数和Uncle Bob的《
Agile Software Development: Principles, Patterns, and Practices(敏捷软件开发:原则、模式与实践)
posted @ 2006-06-07 10:52 混沌中立 阅读(1426) | 评论 (3)编辑 收藏