Quartz 4

策略模式

8 min read

策略模式

目的

定义一个家族算法，并封装好其中每一个，使它们可以互相替换。策略模式使算法的变化独立于使用它的客户。

解释

策略模式允许在运行时选择最匹配的算法

比如：

现代排序算法实际上是混合排序，在不同输入规模下会采取不同的排序方式。

优缺点

优点

  • 可以以相同的方式调用所有算法，减少了各种算法类与使用算法类之间的耦合。策略模式的Strategy类层次为Context类定义了一系列的可供重复使用的算法或行为，继承有助于析取这些算法中的公共功能。
  • 简化了单元测试。每个算法都有自己的类，可以通过自己的接口单独测试；
  • 符合“开放封闭原则”，无需对上下文进行修改就可以引入新的策略。

缺点

  • 不适合算法极少发生改变的场景，会使得程序整体过于复杂；
  • 要求客户端必须知晓策略间的不同，因为需要从中选择；

示例

案例：收银

大鸟给小菜出了个作业，要求实现一个商场收银软件程序，营业员可以通过输入客户所有购买商品的单价和数量，程序自动计算出总金额。同时，商场有时会有打折活动（如商品打7折），或满减促销活动（如商品满300-100），程序应能考虑这些活动的情形，在尽量减少重复代码的前提下，实现正确的金额计算。

UML 图

代码实现

先定义收银抽象类

public abstract class CashSuper{
    public abstract double acceptCash(double money);
}

然后实现具体的收银算法

public class CashNormal extends CashSuper {
    @Override
    public double acceptCash(double money) {
        return money;
    }
}
 
public class CashRebate extends CashSuper {
    private double moneyRebate;
 
    public CashRebate(String moneyRebate) {
        this.moneyRebate = Double.parseDouble(moneyRebate);
    }
 
    @Override
    public double acceptCash(double money) {
        return money * moneyRebate;
    }
 
    public double getMoneyRebate() {
        return moneyRebate;
    }
  
    public void setMoneyRebate(double moneyRebate) {
        this.moneyRebate = moneyRebate;
    }
}
 
public class CashReturn extends CashSuper {
    private double moneyCondition;
    private double moneyReturn;
 
    public CashReturn(String moneyCondition, String moneyReturn) {
        this.moneyCondition = Double.parseDouble(moneyCondition);
        this.moneyReturn = Double.parseDouble(moneyReturn);
    }
 
    @Override
    public double acceptCash(double money) {
        if(money >= this.moneyCondition) {
            return money - Math.floor(money / this.moneyCondition) * moneyReturn;
        }
        return money;
    }
 
    public double getMoneyCondition() {
        return moneyCondition;
    }
 
    public void setMoneyCondition(double moneyCondition) {
        this.moneyCondition = moneyCondition;
    }
 
    public double getMoneyReturn() {
        return moneyReturn;
    }
 
    public void setMoneyReturn(double moneyReturn) {
        this.moneyReturn = moneyReturn;
    }
}

定义封装类，提供收费接口。

public class CashContext {
 
    private CashSuper cs;
 
    public CashContext(String type) {
        switch(type){
            case "正常收费":
                this.cs = new CashNormal();
                break;
            case "满返":
                this.cs = new CashReturn("300", "100");
                break;
            case "打折":
                this.cs = new CashRebate("0.8");
                break;
        }
    }
    
	// 收银时调用的方法，不需要关系具体的收银算法，只需要关心结果
    // 与 简单工厂不同，简单工厂最终是要得到一个实例去使用，在这里只需要一个计算结果
    public double getResult(double money){
        return cs.acceptCash(money);
    }
}

案例：c标准库排序

下面的代码是c标准库的快速排序源码：glibc/qsort.c at master · lattera/glibc (github.com)

此代码采用的策略模式有：

  1. 在数据量较小（0~4）时，采用最原始的冒泡排序
  2. 在数据量较大时(total_elems > MAX_THRESH)采用快速排序
  3. 自定义比较函数 __compar_d_fn_t cmp，比较函数不同，最终排序也不相同，且可以支持自定义 struct
void
_quicksort (void *const pbase, size_t total_elems, size_t size,
	    __compar_d_fn_t cmp, void *arg)
{
  char *base_ptr = (char *) pbase;
 
  const size_t max_thresh = MAX_THRESH * size;
 
  if (total_elems == 0)
    /* Avoid lossage with unsigned arithmetic below.  */
    return;
    
  if (total_elems > MAX_THRESH)
    {
      char *lo = base_ptr;
      char *hi = &lo[size * (total_elems - 1)];
      stack_node stack[STACK_SIZE];
      stack_node *top = stack;
 
      PUSH (NULL, NULL);
 
      while (STACK_NOT_EMPTY)
        {
          char *left_ptr;
          char *right_ptr;
 
	  /* Select median value from among LO, MID, and HI. Rearrange
	     LO and HI so the three values are sorted. This lowers the
	     probability of picking a pathological pivot value and
	     skips a comparison for both the LEFT_PTR and RIGHT_PTR in
	     the while loops. */
 
	  char *mid = lo + size * ((hi - lo) / size >> 1);
 
	  if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
	    SWAP (mid, lo, size);
	  if ((*cmp) ((void *) hi, (void *) mid, arg) < 0)
	    SWAP (mid, hi, size);
	  else
	    goto jump_over;
	  if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
	    SWAP (mid, lo, size);
	jump_over:;
 
	  left_ptr  = lo + size;
	  right_ptr = hi - size;
 
	  /* Here's the famous ``collapse the walls'' section of quicksort.
	     Gotta like those tight inner loops!  They are the main reason
	     that this algorithm runs much faster than others. */
	  do
	    {
	      while ((*cmp) ((void *) left_ptr, (void *) mid, arg) < 0)
		left_ptr += size;
 
	      while ((*cmp) ((void *) mid, (void *) right_ptr, arg) < 0)
		right_ptr -= size;
 
	      if (left_ptr < right_ptr)
		{
		  SWAP (left_ptr, right_ptr, size);
		  if (mid == left_ptr)
		    mid = right_ptr;
		  else if (mid == right_ptr)
		    mid = left_ptr;
		  left_ptr += size;
		  right_ptr -= size;
		}
	      else if (left_ptr == right_ptr)
		{
		  left_ptr += size;
		  right_ptr -= size;
		  break;
		}
	    }
	  while (left_ptr <= right_ptr);
 
          /* Set up pointers for next iteration.  First determine whether
             left and right partitions are below the threshold size.  If so,
             ignore one or both.  Otherwise, push the larger partition's
             bounds on the stack and continue sorting the smaller one. */
 
          if ((size_t) (right_ptr - lo) <= max_thresh)
            {
              if ((size_t) (hi - left_ptr) <= max_thresh)
		/* Ignore both small partitions. */
                POP (lo, hi);
              else
		/* Ignore small left partition. */
                lo = left_ptr;
            }
          else if ((size_t) (hi - left_ptr) <= max_thresh)
	    /* Ignore small right partition. */
            hi = right_ptr;
          else if ((right_ptr - lo) > (hi - left_ptr))
            {
	      /* Push larger left partition indices. */
              PUSH (lo, right_ptr);
              lo = left_ptr;
            }
          else
            {
	      /* Push larger right partition indices. */
              PUSH (left_ptr, hi);
              hi = right_ptr;
            }
        }
    }
 
  /* Once the BASE_PTR array is partially sorted by quicksort the rest
     is completely sorted using insertion sort, since this is efficient
     for partitions below MAX_THRESH size. BASE_PTR points to the beginning
     of the array to sort, and END_PTR points at the very last element in
     the array (*not* one beyond it!). */
 
#define min(x, y) ((x) < (y) ? (x) : (y))
 
  {
    char *const end_ptr = &base_ptr[size * (total_elems - 1)];
    char *tmp_ptr = base_ptr;
    char *thresh = min(end_ptr, base_ptr + max_thresh);
    char *run_ptr;
 
    /* Find smallest element in first threshold and place it at the
       array's beginning.  This is the smallest array element,
       and the operation speeds up insertion sort's inner loop. */
 
    for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
      if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
        tmp_ptr = run_ptr;
 
    if (tmp_ptr != base_ptr)
      SWAP (tmp_ptr, base_ptr, size);
 
    /* Insertion sort, running from left-hand-side up to right-hand-side.  */
 
    run_ptr = base_ptr + size;
    while ((run_ptr += size) <= end_ptr)
      {
	tmp_ptr = run_ptr - size;
	while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
	  tmp_ptr -= size;
 
	tmp_ptr += size;
        if (tmp_ptr != run_ptr)
          {
            char *trav;
 
	    trav = run_ptr + size;
	    while (--trav >= run_ptr)
              {
                char c = *trav;
                char *hi, *lo;
 
                for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo)
                  *hi = *lo;
                *hi = c;
              }
          }
      }
  }
}

Graph View