手撸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)
有疑问加站长微信联系（非本文作者）
