手撸golang 行为型设计模式 策略模式
缘起
最近温习设计模式
拜读谭勇德的<<设计模式就该这样学>>
本系列笔记拟采纳golang练习之
策略模式
策略模式（Strategy Pattern）又叫作政策模式（Policy Pattern），它将定义的算法家族别离封装起来，让它们之间能够相互替换，从而让算法的变动不会影响到应用算法的用户，属于行为型设计模式。(摘自 谭勇德 <<设计模式就该这样学>>)场景
- 某学员问题管理系统, 须要对学员问题进行排序
- 码农王二狗依据<<我的第一本算法书>>里的形容, 应用冒泡排序算法实现了问题排序功能
- Leader审查代码时, 认为王二狗的实现尽管实现了性能, 但不够sexy, 要求改良
- 于是王二狗持续翻查算法书, 又加上了抉择排序和疾速排序算法.
- 为兼容性和可扩展性思考, 王二狗依据策略模式, 把排序算法都形象成对立接口, 等Leader说哪个好, 就用那个.
设计
- ISortPolicy: 排序算法接口
- tBubbleSortPolicy: 冒泡排序算法, 实现ISortPolicy接口
- tSelectSortPolicy: 抉择排序算法, 实现ISortPolicy接口
- tQuickSortPolicy: 疾速排序算法, 实现ISortPolicy接口. 外部顺便实现了一个LIFO栈 - tIntStack.
单元测试
policy_pattern_test.go, 生成若干随机整数, 而后别离应用冒泡, 抉择, 疾速排序算法进行排序
package behavioral_patternsimport ( plc "learning/gooop/behavioral_patterns/policy" "math/rand" "testing" "time")func Test_PolicyPattern(t *testing.T) { size := 20 data := make([]int, size) r := rand.New(rand.NewSource(time.Now().Unix())) for i, _ := range data { data[i] = r.Intn(100) } t.Logf("UnsortedData \t= %v", data) fnMakeCopy := func() []int{ copies := make([]int, size) for i,v := range data { copies[i] = v } return copies } fnTestPolicy := func(policy plc.ISortPolicy) { sorted := policy.Sort(fnMakeCopy()) t.Logf("%s \t= %v", policy.Name(), sorted) } fnTestPolicy(plc.NewBubbleSortPolicy()) fnTestPolicy(plc.NewSelectSortPolicy()) fnTestPolicy(plc.NewQuickSortPolicy())}测试输入
$ go test -v policy_pattern_test.go === RUN Test_PolicyPattern policy_pattern_test.go:17: UnsortedData = [19 17 28 36 80 84 70 7 80 68 2 96 94 26 22 31 80 49 49 69] policy_pattern_test.go:29: BubbleSort = [2 7 17 19 22 26 28 31 36 49 49 68 69 70 80 80 80 84 94 96] policy_pattern_test.go:29: SelectSort = [2 7 17 19 22 26 28 31 36 49 49 68 69 70 80 80 80 84 94 96] policy_pattern_test.go:29: QuickSort = [2 7 17 19 22 26 28 31 36 49 49 68 69 70 80 80 80 84 94 96]--- PASS: Test_PolicyPattern (0.00s)PASSok command-line-arguments 0.002sISortPolicy.go
排序算法接口
package policytype ISortPolicy interface { Name() string Sort(data []int) []int}tBubbleSortPolicy.go
冒泡排序算法, 实现ISortPolicy接口
package policy// 冒泡排序type tBubbleSortPolicy struct {}func NewBubbleSortPolicy() ISortPolicy { return &tBubbleSortPolicy{}}func (self *tBubbleSortPolicy) Name() string { return "BubbleSort"}func (self *tBubbleSortPolicy) Sort(data []int) []int { if data == nil { return nil } size := len(data) if size <= 1 { return data } for { i := size - 1 changed := false for { if i <= 0 { break } j := i - 1 if data[j] > data[i] { data[i],data[j] = data[j],data[i] changed = true } i-- } if !changed { break } } return data}tSelectSortPolicy.go
抉择排序算法, 实现ISortPolicy接口
package policy// 抉择排序type tSelectSortPolicy struct {}func NewSelectSortPolicy() ISortPolicy { return &tSelectSortPolicy{}}func (self *tSelectSortPolicy) Name() string { return "SelectSort"}func (self *tSelectSortPolicy) Sort(data []int) []int { if data == nil { return nil } size := len(data) if size <= 1 { return data } i := 0 for { if i >= size - 1 { break } p, m := self.min(data, i + 1, size - 1) if m < data[i] { data[p], data[i] = data[i], data[p] } i++ } return data}func (self *tSelectSortPolicy) min(data []int, from int, to int) (p int, v int) { i := from p = from v = data[from] if to <= from { return p, v } for { i++ if i > to { break } if data[i] < v { p = i v = data[i] } } return p, v}tQuickSortPolicy.go
疾速排序算法, 实现ISortPolicy接口. 外部顺便实现了一个LIFO栈.
package policyimport "errors"// 疾速排序type tQuickSortPolicy struct { mLeftStack *tIntStack mRightStack *tIntStack}func NewQuickSortPolicy() ISortPolicy { return &tQuickSortPolicy{ newIntStack(),newIntStack(), }}// LIFO栈type tIntStack struct { tail *tIntNode size int}type tIntNode struct { Value int Prev *tIntNode}func newIntNode(value int) *tIntNode { return &tIntNode { value, nil, }}func newIntStack() *tIntStack { return &tIntStack{ nil, 0, }}func (self *tIntStack) Push(i int) { node := newIntNode(i) node.Prev = self.tail self.tail = node self.size++}func (self *tIntStack) Pop() (error,int) { if self.size > 0 { self.size-- node := self.tail self.tail = self.tail.Prev return nil, node.Value } else { return errors.New("empty stack"), 0 }}func (self *tIntStack) Size() int { return self.size}func (self *tQuickSortPolicy) Name() string { return "QuickSort"}func (self *tQuickSortPolicy) Sort(data []int) []int { self.qsort(data, 0, len(data) - 1) return data}func (self *tQuickSortPolicy) qsort(data []int, from int, to int) { if to <= from { return } // only two if to == from + 1 { if data[to] < data[from] { data[from], data[to] = data[to], data[from] } return } // get pivot iPivot := (from + to) / 2 vPivot := data[iPivot] // split left and right left := 0 right := 0 for i := from; i <= to; i++ { if i == iPivot { continue } v := data[i] if v <= vPivot { self.mLeftStack.Push(v) left++ } else { self.mRightStack.Push(v) right++ } } // pop right stack p := to for i := right; i > 0; i-- { e,v := self.mRightStack.Pop() if e != nil { panic(e) } data[p] = v p-- } // pop pivot data[p] = vPivot p-- // pop left stack for i := left; i > 0; i-- { e,v := self.mLeftStack.Pop() if e != nil { panic(e) } data[p] = v p-- } // qsort left and right self.qsort(data, from, from + left - 1) self.qsort(data, to - right + 1, to)}策略模式小结
策略模式的长处（1）策略模式合乎开闭准则。（2）防止应用多重条件转移语句，如if...else语句、switch...case语句（3）应用策略模式能够进步算法的保密性和安全性。策略模式的毛病（1）客户端必须晓得所有的策略，并且自行决定应用哪一个策略类。（2）代码中会产生十分多策略类，减少保护难度。(摘自 谭勇德 <<设计模式就该这样学>>)(end)