策略模式

概述

状态模式(Strategy pattern,也称为算法簇模式)的主要实现逻辑为,构建多个策略类用于封装不同的算法,并将这些算法的其中一个以引用形式注入给上下文对象,以使上下文对象可以将其行为委托给策略类处理。相较于状态模式内部封装了状态切换,上下文对象的行为多数委托给状态对象加以处理,策略模式委托给策略类的处理通常只是单个行为,即算法,并且,设置策略(即替换算法)的过程由外部调用者完成。

《设计模式:可复用面向对象软件的基础》一书将状态模式描述为:

Define a family of algorithms, encapsulate each one, and make them interchangeable. Strategy lets the algorithm vary independently fromclients that use it.

经典实现

策略模式包含下列组件:

  • Context: 以引用对象形式持有某个 ConcreteStrategy,对外暴露的交互接口通过将行为委托给 ConcreteStrategy 实现。
  • Strategy: 策略类,定义算法的抽象接口。
  • ConcreteStrategy: 具体策略子类,实现 Strategy 抽象类中定义的算法。

以下代码使用策略模式实现了排序算法,通过 ArrayList 实例的 setSortStragery 方法即可切换排序算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
abstract class SortPolicy{
constructor(context){
this.context = context;// 通过引用属性访问 Context 实例,可访问实例属性,以处理状态切换操作;可改为传参实现
}
sort(){}
};

// 冒泡排序,比较相邻元素,将最小值左移
class BubbleSort extends SortPolicy {
sort(){
const arr = this.context.target;
const len = arr.length;
for ( let i = 0; i < len; i++ ){
for ( let j = 0; j < len - 1 - i; j++ ){
if ( arr[j] > arr[j+1] )
this.context.swap(j, j + 1);
}
}
}
};

// 选择排序,选取最小值,排在左侧
class SelectionSort extends SortPolicy {
sort(){
const arr = this.context.target;
const len = arr.length;
let minIndex;// 最小值序号
for ( let i = 0; i < len - 1; i++ ){
minIndex = i;

for ( let j = i; j < len; j++ ){
if ( arr[minIndex] > arr[j] )
minIndex = j;
}

if ( i !== minIndex )
this.context.swap(i, minIndex);
}
}
};

// 插入排序,将后一位比较项顺序插入到之前已排序的数组中
class InsertionSort extends SortPolicy {
sort(){
const arr = this.context.target;
const len = arr.length;

for ( let i = 1; i < length; i++ ){
let j = i;
let temp = arr[i];

while ( j > 0 && arr[j - 1] > temp ){
arr[j] = arr[j - 1];
j--;
};

arr[j] = temp;
};
}
};

// 归并排序,将数组项拆分后分别排序,再合并排序
class MergeSort extends SortPolicy {
sort(){
const arr = this.context.target;
this.mergeSortRec(arr);
}

// 分治
mergeSortRec(arr){
const len = arr.length;
if ( len === 1 ) return arr;

let mid = Math.floor(len / 2);
let left = arr.slice(0, mid);
let right = arr.slice(mid, len);

return this.merge(this.mergeSortRec(left), this.mergeSortRec(right));
}

// 合并两个已排序数组
merge(left, right){
const leftLen = left.length;
const rightLen = right.length;
let leftIndex = 0;
let rightIndex = 0;
let result = [];

while ( leftIndex < leftLen && rightIndex < rightLen ){
if ( left[leftIndex] < right[rightIndex] )
result.push(left[leftIndex++]);
else
result.push(right[rightIndex++]);
};

while ( leftIndex < leftLen ){
result.push(left[leftIndex++]);
};

while ( rightIndex < rightLen ){
result.push(right[rightIndex++]);
};

return result;
}
};

// 快速排序,选取中间项,将左右两边元素按和中间相的比较结果对调,递归该过程,实现数组排序
class QuickSort extends SortPolicy {
sort(){
const arr = this.context.target;
const len = arr.length;
this.quick(arr, 0, len);
}

// 递归,实现分治
quick(arr, left, right){
const len = arr.length;
let index;
if ( len > 1 ){
index = this.partition(arr, left, right);

if ( left < index -1 )
this.quick(arr, left, index - 1);

if ( index < right )
this.quick(arr, index, right);
}
}

// 按中间项对调元素,大值放在右边,小值放在左边
partition(arr, left, right){
let pivot = arr[Math.floor((right + left) / 2)];
let i = left;
let j = right;

while ( i <= j ){
while ( arr[i] < pivot ){
i++;
};

while ( arr[j] > pivot ){
j--;
};

if ( i <= j ){
this.context.swap(arr, i, j);
i++;
j--;
};
};

return i;
}
};

// 堆排序
class HeapSort extends SortPolicy {
sort(){
const arr = this.context.target;
let heapSize = arr.length;

this.buildHeap(arr);

while ( heapSize > 1 ){
heapSize--;
this.context.swap(arr, 0, heapSize);
this.heapify(arr, heapSize, 0);
}
}

buildHeap(arr){
const heapSize = arr.length;

for ( let i = Math.floor(heapSize / 2); i >= 0; i-- ){
this.heapify(arr, heapSize, i);
};
}

heapify(arr, heapSize, i){
let left = 2 * i + 1;
let right = 2 * i + 2;
let largest = i;

if ( left < heapSize && arr[left] > arr[largest] )
largest = left;

if ( right < heapSize && arr[right] > arr[largest] )
largest = right;

if ( largest !== i ){
this.context.swap(arr, i, largest);
this.heapify(arr, heapSize, largest);
};
}
}

class ArrayList {
constructor(){
this.target = [];
this.sortStragery = new BubbleSort(this);// 排序策略
}

insert(item){
this.target.push(item);
}

// 元素互换
swap(i, j){
let arr = this.target;
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

setSortStragery(Stragery){
this.sortStragery = new Stragery(this);
}

sort(){
this.sortStragery.sort();
}

toString(){
return this.target.join();
}
};

策略模式需要注意的点:

  1. 调用者需要对策略模式提供的算法足够了解。
  2. Context 类既可以通过调用时向 ConcreteStrategy 具体策略子类注入参数实现,也可以将自身作为引用存储在 ConcreteStrategy 具体策略子类中。同时 ConcreteStrategy 具体策略子类可以从 Strategy 抽象接口继承属性,其自身也可以实现为有状态值的。
  3. Context 类可设置多个,以针对不同的需求,如不同的设备。

js 中的策略模式

状态模式,js 可以使用对象字面量声明多个策略子类,通过访问对象属性的方式调用算法。

动效算法切换

本节以前端动效为例,试图说明策略模式在该领域中的应用。读者若想对前端动效有更深入的理解,可参见笔者的另一篇文章,jquery 动效分析

动效实现的基本数学思想是通过动画执行时长 duration、起始位置 beginning val、结束位置(即要变化的总量) change 计算动画已执行时间 timestamp 的所处位置 pos,即函数 pos = fn(t, b, c, d)。在动效中,位置这个概念会被起始样式和结束样式所替换。策略模式的用武之地即在于设定不同的缓动函数,以计算当前样式值。

在表达式 pos = fn(t, b, c, d) 中,参数 t 动画已执行时间, b 起始样式 由程序计算获得,参数 c 结束样式, d 动画总时长 由调用方提供。为扼要说明起见,示例代码将不提供计算样式和设置样式值的 getStyles, setStyles 方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
const Easings = {
linear(t, b, c, d){
return c * t / d + b;
},
easeIn(t, b, c, d){
return c * (t / d) * t + b;
},
easeOut(t, b, c, d){
return -c * (t / d) * (t - 2) + b;
},
easeInOut(t, b, c, d){
if ( 2t / d < 1 ) return c / 2 * t * t + b;
return - c / 2 * ((--t) * (t - 2) - 1) + b;
}
};

class Animation {
node = null;
startTime = 0;
startStyles = null;
endStyles = null;
duration = null;
easing = null;
running = false;

constructor(node, styles, duration, easing){
this.node = node;
this.startTime = +new Date;
this.startStyles = getStyles(node);
this.endStyles = styles;
this.duration = duration;
this.easing = Easings[easing];

this.run();
}

run(){
const that = this;
this.running = true;
let timer = setInterval(() => {
that.tween();
if ( !running ) clearInterval(timer);
}, 10);
}

tween(){
const { node, startTime, startStyles, endStyles, duration, easing } = this;
const currentTime = +new Date;
const t = currentTime - startTime;

if ( t >= this.duration ){
setStyles(node, endStyles);
this.running = false;
return;
};

let currentStyles = {};
Object.keys(endStyles).map(key => {
let startStyle = startStyles[key];
let endStyle = endStyles[key];

currentStyles[key] = easing(t, startStyle, endStyle, duration);
});

setStyles(this.node, currentStyles);
}
};

上述代码中,由调用方提供缓动函数算法名,animation 实例将根据将通过指定的缓动函数计算节点的当前样式,并作相应更新。关于前端动效(包含缓动函数,动画队列等)的细微说明,笔者将在后续的文章加以展开。

校验算法切换

策略模式也可以应用于数据校验中,即通过对某个字段设定校验规则,通过该规则从校验函数集合中选取函数,并对相应的数据做出校验。若需深入理解数据校验过程,可参看笔者的另一篇文章 浅析async-validator源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
const stratrgies = {
notEmpty(value, rule){
if ( value === '' ) return rule.msg;
},
minLength(value, rule){
if ( value.length < rule.length ) return rule.msg;
}
};

class Validator {
this.rules = null;

constructor(rules){
this.rules = rules;
}

validate(data){
const { rules } = this;
let errors = null;

Object.keys(data).map(key => {
const rule = rules[key];
const value = data[key];
const validateMethod = stratrgies[rule.type];

const msg = validateMethod(value, rule);
if ( msg ){
if ( !errors ) errors = {};
errors[key] = msg;
};
});

return errors;
}
};

参考

[设计模式:可复用面向对象软件的基础]
[Javascript 设计模式和开发实践 - 曾探]