2006年7月13日
在一个项目里面有这么一个技术需求:
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 混沌中立 阅读(7325) |
评论 (10) |
编辑 收藏
在几年之前,在大学里面的时候,认为系统的架构设计,就像建筑设计一样,会把骨架搭成,然后有具体人员进行详细的开发.
在后来,工作中,慢慢有了一些变化,因为原先的想法不太切合实际,系统就是在变化之中的,如果固定了骨架,那就很难的敏捷面对变化.
所以,系统的架构设计,应该是面向接口的设计,确定各个部分之间的数据接口和方法接口.这样,即使有了变化,只要遵循接口的定义,就还是可以面对变化.
最近,又有了想法的变化.架构的设计,应该就是规则和规约的设计.设计出一系列,统一的,和谐的规则,在这些规则之前圈住的部分,实际就是系统的全貌.
接口的设计,实际只是规则和规约设计的一个部分.
架构的设计,不应该只是程序方面的事情,同时也包含了心理学方面和社会学方面的一些规则.例如:团队在面对变化时候,需要采用的规则和流程.
只有包含了这些非程序上的规则之后,才能保证架构风格的统一协调.
以上,是我对系统设计的想法的转变过程.记录于此,以供回溯.
posted @
2009-09-02 10:53 混沌中立 阅读(226) |
评论 (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 混沌中立 阅读(1330) |
评论 (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 混沌中立 阅读(2136) |
评论 (4) |
编辑 收藏