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 混沌中立 閱讀(7370) |
評論 (10) |
編輯 收藏
在幾年之前,在大學里面的時候,認為系統的架構設計,就像建筑設計一樣,會把骨架搭成,然后有具體人員進行詳細的開發.
在后來,工作中,慢慢有了一些變化,因為原先的想法不太切合實際,系統就是在變化之中的,如果固定了骨架,那就很難的敏捷面對變化.
所以,系統的架構設計,應該是面向接口的設計,確定各個部分之間的數據接口和方法接口.這樣,即使有了變化,只要遵循接口的定義,就還是可以面對變化.
最近,又有了想法的變化.架構的設計,應該就是規則和規約的設計.設計出一系列,統一的,和諧的規則,在這些規則之前圈住的部分,實際就是系統的全貌.
接口的設計,實際只是規則和規約設計的一個部分.
架構的設計,不應該只是程序方面的事情,同時也包含了心理學方面和社會學方面的一些規則.例如:團隊在面對變化時候,需要采用的規則和流程.
只有包含了這些非程序上的規則之后,才能保證架構風格的統一協調.
以上,是我對系統設計的想法的轉變過程.記錄于此,以供回溯.
posted @
2009-09-02 10:53 混沌中立 閱讀(247) |
評論 (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 混沌中立 閱讀(1353) |
評論 (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.tkk7.com/Files/GandofYan/sudoku.rar
附件2：輸入輸出文件的example
http://www.tkk7.com/Files/GandofYan/temp.rar
posted @
2006-07-13 16:19 混沌中立 閱讀(2163) |
評論 (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=(R+1)/N
R:包內類的關系數目（與包外部的類沒有關系）
N:包內類的數量
被分析package的具體和抽象類（和接口）的數量，用于衡量package的可擴展性。
依賴于被分析package的其他package的數量，用于衡量pacakge的職責。
被分析package的類所依賴的其他package的數量，用于衡量package的獨立性。
被分析package中的抽象類和接口與所在package所有類數量的比例，取值范圍為0－1。
A=Cc/N
用于衡量package的不穩定性，取值范圍為0－1。I＝0表示最穩定，I＝1表示最不穩定。
I＝Ce/（Ce＋Ca）
??? ??? ? 被分析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 Complexity （CC） = 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 混沌中立 閱讀(1512) |
評論 (3) |
編輯 收藏