手撸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.002s

ISortPolicy.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)

有疑问加站长微信联系（非本文作者）

手撸golang 行为型设计模式策略模式

手撸golang 行为型设计模式策略模式

缘起

策略模式

场景

设计

单元测试

测试输出

ISortPolicy.go

tBubbleSortPolicy.go

tSelectSortPolicy.go

tQuickSortPolicy.go

策略模式小结

Recommend

石头，砂砾和水：谈谈 clubhouse

数据同步工具Sqoop和DataX

bazel macro 的开发

Springboot集成Spring Security实现JWT认证

微服务架构-从理想到现实(210206)

如何使用Builder模式构建线程池

GitHub超级火！任意爬取，超全开源爬虫工具箱

“民工歌神”吴恩师的互联网奇幻漂流

一块GPU模拟猴子大脑，普通台式机变超算，英国大学研究登上Nature子刊

为什么“自学”总是那么难?

About Joyk

手撸golang 行为型设计模式 策略模式

手撸golang 行为型设计模式 策略模式

缘起

策略模式

场景

设计

单元测试

测试输出

ISortPolicy.go

tBubbleSortPolicy.go

tSelectSortPolicy.go

tQuickSortPolicy.go

策略模式小结

Recommend

About Joyk

手撸golang 行为型设计模式策略模式

手撸golang 行为型设计模式策略模式