缘起

最近复习设计模式
拜读谭勇德的<<设计模式就该这样学>>
本系列笔记拟采用golang练习之

策略模式

  1. 策略模式（Strategy Pattern）又叫作政策模式（Policy Pattern），
  2. 它将定义的算法家族分别封装起来，
  3. 让它们之间可以互相替换，
  4. 从而让算法的变化不会影响到使用算法的用户，
  5. 属于行为型设计模式。
  7. (摘自 谭勇德 <<设计模式就该这样学>>)

场景

  • 某学员成绩管理系统, 需要对学员成绩进行排序
  • 码农王二狗根据<<我的第一本算法书>>里的描述, 使用冒泡排序算法实现了成绩排序功能
  • Leader审查代码时, 认为王二狗的实现虽然完成了功能, 但不够sexy, 要求改进
  • 于是王二狗继续翻查算法书, 又加上了选择排序和快速排序算法.
  • 为兼容性和可扩展性考虑, 王二狗根据策略模式, 把排序算法都抽象成统一接口, 等Leader说哪个好, 就用那个.

设计

  • ISortPolicy: 排序算法接口
  • tBubbleSortPolicy: 冒泡排序算法, 实现ISortPolicy接口
  • tSelectSortPolicy: 选择排序算法, 实现ISortPolicy接口
  • tQuickSortPolicy: 快速排序算法, 实现ISortPolicy接口. 内部顺便实现了一个LIFO栈 - tIntStack.

单元测试

policy_pattern_test.go, 生成若干随机整数, 然后分别使用冒泡, 选择, 快速排序算法进行排序

  1. package behavioral_patterns
  3. import (
  4.     plc "learning/gooop/behavioral_patterns/policy"
  5.     "math/rand"
  6.     "testing"
  7.     "time"
  8. )
  10. func Test_PolicyPattern(t *testing.T) {
  11.     size := 20
  12.     data := make([]int, size)
  13.     r := rand.New(rand.NewSource(time.Now().Unix()))
  14.     for i, _ := range data {
  15.         data[i] = r.Intn(100)
  16.     }
  17.     t.Logf("UnsortedData \t= %v", data)
  19.     fnMakeCopy := func() []int{
  20.         copies := make([]int, size)
  21.         for i,v := range data {
  22.             copies[i] = v
  23.         }
  24.         return copies
  25.     }
  27.     fnTestPolicy := func(policy plc.ISortPolicy) {
  28.         sorted := policy.Sort(fnMakeCopy())
  29.         t.Logf("%s \t= %v", policy.Name(), sorted)
  30.     }
  32.     fnTestPolicy(plc.NewBubbleSortPolicy())
  33.     fnTestPolicy(plc.NewSelectSortPolicy())
  34.     fnTestPolicy(plc.NewQuickSortPolicy())
  35. }

测试输出

  1. $ go test -v policy_pattern_test.go 
  2. === RUN   Test_PolicyPattern
  3.     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]
  4.     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]
  5.     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]
  6.     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]
  7. --- PASS: Test_PolicyPattern (0.00s)
  8. PASS
  9. ok      command-line-arguments  0.002s

ISortPolicy.go

排序算法接口

  1. package policy
  3. type ISortPolicy interface {
  4.     Name() string
  5.     Sort(data []int) []int
  6. }

tBubbleSortPolicy.go

冒泡排序算法, 实现ISortPolicy接口

  1. package policy
  3. // 冒泡排序
  4. type tBubbleSortPolicy struct {
  5. }
  7. func NewBubbleSortPolicy() ISortPolicy {
  8.     return &tBubbleSortPolicy{}
  9. }
  11. func (self *tBubbleSortPolicy) Name() string {
  12.     return "BubbleSort"
  13. }
  15. func (self *tBubbleSortPolicy) Sort(data []int) []int {
  16.     if data == nil {
  17.         return nil
  18.     }
  20.     size := len(data)
  21.     if size <= 1 {
  22.         return data
  23.     }
  25.     for {
  26.         i := size - 1
  27.         changed := false
  29.         for {
  30.             if i <= 0 {
  31.                 break
  32.             }
  33.             j := i - 1
  35.             if data[j] > data[i] {
  36.                 data[i],data[j] = data[j],data[i]
  37.                 changed = true
  38.             }
  40.             i--
  41.         }
  43.         if !changed {
  44.             break
  45.         }
  46.     }
  48.     return data
  49. }

tSelectSortPolicy.go

选择排序算法, 实现ISortPolicy接口

  1. package policy
  3. // 选择排序
  4. type tSelectSortPolicy struct {
  5. }
  7. func NewSelectSortPolicy() ISortPolicy {
  8.     return &tSelectSortPolicy{}
  9. }
  11. func (self *tSelectSortPolicy) Name() string {
  12.     return "SelectSort"
  13. }
  15. func (self *tSelectSortPolicy) Sort(data []int) []int {
  16.     if data == nil {
  17.         return nil
  18.     }
  20.     size := len(data)
  21.     if size <= 1 {
  22.         return data
  23.     }
  25.     i := 0
  26.     for {
  27.         if i >= size - 1 {
  28.             break
  29.         }
  31.         p, m := self.min(data, i + 1, size - 1)
  32.         if m < data[i] {
  33.             data[p], data[i] = data[i], data[p]
  34.         }
  36.         i++
  37.     }
  39.     return data
  40. }
  42. func (self *tSelectSortPolicy) min(data []int, from int, to int) (p int, v int) {
  43.     i := from
  44.     p = from
  45.     v = data[from]
  47.     if to <= from {
  48.         return p, v
  49.     }
  51.     for {
  52.         i++
  53.         if i > to {
  54.             break
  55.         }
  57.         if data[i] < v {
  58.             p = i
  59.             v = data[i]
  60.         }
  61.     }
  63.     return p, v
  64. }

tQuickSortPolicy.go

快速排序算法, 实现ISortPolicy接口. 内部顺便实现了一个LIFO栈.

  1. package policy
  3. import "errors"
  5. // 快速排序
  6. type tQuickSortPolicy struct {
  7.     mLeftStack *tIntStack
  8.     mRightStack *tIntStack
  9. }
  11. func NewQuickSortPolicy() ISortPolicy {
  12.     return &tQuickSortPolicy{
  13.         newIntStack(),newIntStack(),
  14.     }
  15. }
  17. // LIFO栈
  18. type tIntStack struct {
  19.     tail *tIntNode
  20.     size int
  21. }
  23. type tIntNode struct {
  24.     Value int
  25.     Prev *tIntNode
  26. }
  28. func newIntNode(value int) *tIntNode {
  29.     return &tIntNode {
  30.         value, nil,
  31.     }
  32. }
  34. func newIntStack() *tIntStack {
  35.     return &tIntStack{
  36.         nil,
  37.         0,
  38.     }
  39. }
  41. func (self *tIntStack) Push(i int) {
  42.     node := newIntNode(i)
  43.     node.Prev = self.tail
  44.     self.tail = node
  45.     self.size++
  46. }
  48. func (self *tIntStack) Pop() (error,int) {
  49.     if self.size > 0 {
  50.         self.size--
  51.         node := self.tail
  52.         self.tail = self.tail.Prev
  53.         return nil, node.Value
  55.     } else {
  56.         return errors.New("empty stack"), 0
  57.     }
  58. }
  60. func (self *tIntStack) Size() int {
  61.     return self.size
  62. }
  64. func (self *tQuickSortPolicy) Name() string {
  65.     return "QuickSort"
  66. }
  68. func (self *tQuickSortPolicy) Sort(data []int) []int {
  69.     self.qsort(data, 0, len(data) - 1)
  70.     return data
  71. }
  74. func (self *tQuickSortPolicy) qsort(data []int, from int, to int)  {
  75.     if to <= from {
  76.         return
  77.     }
  79.     // only two
  80.     if to == from + 1 {
  81.         if data[to] < data[from] {
  82.             data[from], data[to] = data[to], data[from]
  83.         }
  84.         return
  85.     }
  87.     // get pivot
  88.     iPivot := (from + to) / 2
  89.     vPivot := data[iPivot]
  91.     // split left and right
  92.     left := 0
  93.     right := 0
  94.     for i := from; i <= to; i++ {
  95.         if i == iPivot {
  96.             continue
  97.         }
  99.         v := data[i]
  100.         if v <= vPivot {
  101.             self.mLeftStack.Push(v)
  102.             left++
  103.         } else {
  104.             self.mRightStack.Push(v)
  105.             right++
  106.         }
  107.     }
  109.     // pop right stack
  110.     p := to
  111.     for i := right; i > 0; i-- {
  112.         e,v := self.mRightStack.Pop()
  113.         if e != nil {
  114.             panic(e)
  115.         }
  116.         data[p] = v
  117.         p--
  118.     }
  120.     // pop pivot
  121.     data[p] = vPivot
  122.     p--
  124.     // pop left stack
  125.     for i := left; i > 0; i-- {
  126.         e,v := self.mLeftStack.Pop()
  127.         if e != nil {
  128.             panic(e)
  129.         }
  130.         data[p] = v
  131.         p--
  132.     }
  134.     // qsort left and right
  135.     self.qsort(data, from, from + left - 1)
  136.     self.qsort(data, to - right + 1, to)
  137. }

策略模式小结

  1. 策略模式的优点
  2. （1）策略模式符合开闭原则。
  3. （2）避免使用多重条件转移语句，如if...else语句、switch...case语句
  4. （3）使用策略模式可以提高算法的保密性和安全性。
  6. 策略模式的缺点
  7. （1）客户端必须知道所有的策略，并且自行决定使用哪一个策略类。
  8. （2）代码中会产生非常多策略类，增加维护难度。
  10. (摘自 谭勇德 <<设计模式就该这样学>>)

(end)