手撸 golang 行为型设计模式 策略模式
缘起
最近温习设计模式
拜读谭勇德的 << 设计模式就该这样学 >>
本系列笔记拟采纳 golang 练习之
策略模式
策略模式（Strategy Pattern）又叫作政策模式（Policy Pattern），它将定义的算法家族别离封装起来，让它们之间能够相互替换，从而让算法的变动不会影响到应用算法的用户，属于行为型设计模式。(摘自 谭勇德 << 设计模式就该这样学 >>)场景
- 某学员问题管理系统, 须要对学员问题进行排序
- 码农王二狗依据 << 我的第一本算法书 >> 里的形容, 应用冒泡排序算法实现了问题排序功能
- Leader 审查代码时, 认为王二狗的实现尽管实现了性能, 但不够 sexy, 要求改良
- 于是王二狗持续翻查算法书, 又加上了抉择排序和疾速排序算法.
- 为兼容性和可扩展性思考, 王二狗依据 策略模式, 把排序算法都形象成对立接口, 等 Leader 说哪个好, 就用那个.
设计
- ISortPolicy: 排序算法接口
- tBubbleSortPolicy: 冒泡排序算法, 实现 ISortPolicy 接口
- tSelectSortPolicy: 抉择排序算法, 实现 ISortPolicy 接口
- tQuickSortPolicy: 疾速排序算法, 实现 ISortPolicy 接口. 外部顺便实现了一个 LIFO 栈 – tIntStack.
单元测试
policy_pattern_test.go, 生成若干随机整数, 而后别离应用冒泡, 抉择, 疾速排序算法进行排序
package behavioral_patterns
import (
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)
PASS
ok command-line-arguments 0.002sISortPolicy.go
排序算法接口
package policy
type 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 policy
import "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)