图解二叉树搜索算法

二叉查找树(Binary Search Tree),也称二叉搜索树,是指一棵空树或者具有下列性质的二叉树:

  1. 任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  2. 任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  3. 任意节点的左、右子树也分别为二叉查找树;
  4. 没有键值相等的节点。
  5. 二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(log n)。二叉查找树是基础性数据结构,用于构建更为抽象的数据结构,如集合、multiset、关联数组等。(摘自维基百科)

下面 4 张 GIF 动图,是 penjee 官博制作分享。,分享给大家。

图1:查找 BST 中的某个元素

在二叉搜索树b中查找x的过程为:

  1. 若b是空树,则搜索失败,否则:
  2. 若x等于b的根节点的数据域之值,则查找成功;否则:
  3. 若x小于b的根节点的数据域之值,则搜索左子树;否则:
    查找右子树。
    这里写图片描述

图2 ↓ :从有序数组构造一个二叉查找树

这里写图片描述

图3 ↓:往 BST 中插入元素

向一个二叉搜索树b中插入一个节点s的算法,过程为:

  1. 若b是空树,则将s所指结点作为根节点插入,否则:
  2. 若s->data等于b的根节点的数据域之值,则返回,否则:
  3. 若s->data小于b的根节点的数据域之值,则把s所指节点插入到左子树中,否则:
    把s所指节点插入到右子树中。(新插入节点总是叶子节点)
    这里写图片描述

图4 ↓:BST 转成有序数组

这里写图片描述

用Redis模拟session概述

Redis 是一个强大而简单的键值型数据库,之前在公司网站改版的过程中大量使用 Redis 来处理一些特殊的需求,我希望能将自己对 Redis 的使用经验都分享出来,而这里算是第一篇吧。

背景

项目是一个有着不小访问量的网站,为了达到分流的作用,网站按照不同的业务(个人、企业、后台、营销、搜索、API等)区分成不同的子域名,而子域名下运行的是不同的实例。

对用户登录这块的逻辑,原来的做法是:将登录的明文信息(登录ID、用户名、姓名等)在登录过程中直接写入用户 cookie,当需要进行登录校验的时候,后台直接取出 cookie 中保存的ID进行处理。可以想象,这样的模式只要模拟或者盗取了客户端的 cookie 信息,对于客户来说几乎没有任何安全性的保障。

由于用户的操作可能跨越多个实例,如果采用服务器 session 的机制的话,就需要解决 session 的共享问题,从技术的实现角度来说可能碰到的坑就更多了,于是我们利用了 Redis 来模拟服务器的 session。

实际设计

图1

登录流程见图1

  1. 用户从浏览器中将登录信息传到 Web Server 中处理
  2. Web Server 首先跟进行用户信息验证,当验证通过的时候,根据用户的客户端信息(IP、浏览器信息等)进行散列,形成一个 token,这个 token 将会是 Redis 中的 Key,同时将经常需要获取的内容(用户ID、姓名等)组装成 Value,根据需要可以是 json 格式或者 HashTable,然后设定一个 expire time 保存进 Redis
  3. 将生成的 token 保存在用户的浏览器 cookie 中

图2

验证流程见图2

  1. 用户访问需要进行验证登录的内容时,客户端会将 cookie 传到 Web Server 中
  2. Web Server 从 cookie 中获取到 token 的值,判断 token 是否存在于 Redis 中
  3. 若存在则将 Redis 中保存的信息返回到 Web Server 中进行处理,判断此次获取是否合法:
    • 客户端的信息是否和生成 token 时的一致(IP、浏览器信息等)
    • Value 中保存的内容是否和当前操作匹配(用户ID是否和当前处理的ID,或者如果将IP等信息放到内容中也可以将上一条的验证在这里处理)
  4. 所有验证通过则将正常的结果返回给用户,有需要的话还可以在这个过程中重置或延长原来 Redis key 的生存时间

这样做解决了什么问题?

其实这是一个很简单的思路,将客户登录验证和客户信息获取这两部分内容合并到 Redis 中来进行处理了

  • 不利用服务器的 session,这样当多服务器部署的时候就不需要关心 session 的同步问题了
  • 客户端 cookie 中保存的 token 信息是散列后的内容,不涉及任何业务属性,cookie 一旦被抓取到了单纯从 cookie 信息中也不会丢失任何敏感数据
  • token 即使被盗用了并被有意进行模仿,如果不是完全按照客户登录时的IP、浏览器信息来进行模拟的话,基本无法获取到客户的信息
  • 常用的信息保存在 Redis 中,由于直接读取了内存,比起持久化的数据库查询,读取速度快了很多,减少了负载同时提升了访问效率
  • Redis 中的内容设定了生存时间,当有效期内执行操作重置时间这样的机制模拟了 session timeout,这样也能进一步保证用户的数据安全性

PHP实现常用排序算法(含示意动图

作为phper,一般接触算法的编程不多。

但基本的排序算法还是应该掌握。

毕竟算法作为程序的核心,算法的好坏决定了程序的质量。

本文将依次介绍一些常用的排序算法,以及PHP实现。

1 快速排序

快速排序是由东尼·霍尔发展的一种排序算法。

在平均状况下,排序 n 个项目要Ο(n log n)次比较。

在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。

事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环可以在大部分的架构上,很有效率地被实现出来。

快速排序采用分治法实现排序,具体步骤:

  1. 从数列中挑出一个数作为基准元素。通常选择第一个或最后一个元素。
  2. 扫描数列,以基准元素为比较对象,把数列分成两个区。规则是:小的移动到基准元素前面,大的移到后面,相等的前后都可以。分区完成之后,基准元素就处于数列的中间位置。
  3. 然后再用同样的方法,递归地排序划分的两部分

递归的结束条件是数列的大小是01,也就是永远都已经被排序好了。

PHP代码实现:

function quickSort($arr) {
    // 先设定结束条件,判断是否需要继续进行
    if(count($arr) <= 1) {
        return $arr;
    }

    // 选择第一个元素作为基准元素
    $baseValue = $arr[0];

    // 初始化小于基准元素的左数组
    $leftArray = array();

    // 初始化大于基准元素的右数组
    $rightArray = array();

    // 遍历除基准元素外的所有元素,按照大小关系放入左右数组内
    array_shift($arr);
    foreach ($arr as $value) {
        if ($value < $baseValue) {
            $leftArray[] = $value;
        } else {
            $rightArray[] = $value;
        }
    }

    // 再分别对左右数组进行相同的排序
    $leftArray = quickSort($leftArray);
    $rightArray = quickSort($rightArray);

    // 合并基准元素和左右数组
    return array_merge($leftArray, array($baseValue), $rightArray);
}

2 冒泡排序

冒泡排序是一种简单的排序算法。

算法重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。

走访数列的工作重复地进行,直到没有再需要交换,也就是说该数列已经排序完成。

因为排序过程让较大的数往下沉,较小的往上冒,故而叫冒泡法。

算法步骤:

  1. 从第一个元素开始,比较相邻的元素,如果第一个比第二个大,就交换他们两个。
  2. 从开始第一对到结尾的最后一对,对每一对相邻元素作同样的工作。比较结束后,最后的元素应该会是最大的数。
  3. 对所有的元素重复以上的步骤,除了最后一个。
  4. 重复上面的步骤,每次比较的对数会越来越少,直到没有任何一对数字需要比较。

PHP代码实现:

function bubbleSort($arr)
{
    $len = count($arr);
    
    for($i = 1; $i < $len; $i++) {
        for($k = 0; $k < $len - $i; $k++) {
            if($arr[$k] > $arr[$k + 1]) {
                $tmp = $arr[$k + 1];
                $arr[$k + 1] = $arr[$k];
                $arr[$k] = $tmp;
            }
        }
    }

    return $arr;
}

3 插入排序

插入排序是一种简单直观的排序算法。

插入排序的工作原理是:将需要排序的数,与前面已经排好序的数据从后往前进行比较,使其插入到相应的位置。

插入排序在实现上,通常采用in-place排序,即只需用到O(1)的额外空间的排序。

因而,在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

算法步骤:

  1. 从第一个元素开始,该元素可以认为已经被排序;
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  3. 如果以排序的元素大于新元素,将该元素移到下一位置;
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  5. 将新元素插入到该位置中;
  6. 重复步骤2。

PHP代码实现:

function insertSort($arr)
{
    $len = count($arr);

    for ($i = 1; $i < $len; $i++) {
        $tmp = $arr[$i];
        for ($j = $i - 1; $j >= 0; $j--) {
            if ($tmp < $arr[$j]) {
                $arr[$j + 1] = $arr[$j];
                $arr[$j] = $tmp;
            } else {
                break;
            }
        }
    }

    return $arr;
}

4 选择排序

选择排序是一种简单直观的排序算法。

算法步骤:

  1. 首先,在序列中找到最小元素,存放到排序序列的起始位置;
  2. 接着,从剩余未排序元素中继续寻找最小元素,放到已排序序列的末尾。
  3. 重复第二步,直到所有元素均排序完毕。

PHP代码实现:

function selectSort($arr)
{
    $len = count($arr);

    for ($i = 0; $i < $len; $i++) {
        $p = $i;

        for ($j = $i + 1; $j < $len; $j++) {
            if ($arr[$p] > $arr[$j]) {
                $p = $j;
            }
        }

        $tmp = $arr[$p];
        $arr[$p] = $arr[$i];
        $arr[$i] = $tmp;
    }

    return $arr;
}

5 归并排序

归并排序是建立在归并操作上的一种有效的排序算法。

归并排序将待排序的序列分成若干组,保证每组都有序,然后再进行合并排序,最终使整个序列有序。

该算法是采用分治法的一个非常典型的应用。

算法步骤:

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
  4. 重复步骤3直到某一指针达到序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

排序效果:

PHP实现代码:

/**
 * 归并排序
 *
 * @param array $lists
 * @return array
 */
function merge_sort(array $lists)
{
    $n = count($lists);
    if ($n <= 1) {
        return $lists;
    }
    $left = merge_sort(array_slice($lists, 0, floor($n / 2)));
    $right = merge_sort(array_slice($lists, floor($n / 2)));
    $lists = merge($left, $right);
    return $lists;
}

function merge(array $left, array $right)
{
    $lists = [];
    $i = $j = 0;
    while ($i < count($left) && $j < count($right)) {
        if ($left[$i] < $right[$j]) {
            $lists[] = $left[$i];
            $i++;
        } else {
            $lists[] = $right[$j];
            $j++;
        }
    }
    $lists = array_merge($lists, array_slice($left, $i));
    $lists = array_merge($lists, array_slice($right, $j));
    return $lists;
}

6 堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法。

堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

堆排序的平均时间复杂度为Ο(nlogn)

算法步骤:

  1. 创建一个堆H[0..n-1]
  2. 把堆首(最大值)和堆尾互换;
  3. 把堆的尺寸缩小1,并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置;
  4.  重复步骤2,直到堆的尺寸为1

PHP实现代码:

/**
 * 堆排序
 *
 * @param array $lists
 * @return array
 */
function heap_sort(array $lists)
{
    $n = count($lists);
    build_heap($lists);
    while (--$n) {
        $val = $lists[0];
        $lists[0] = $lists[$n];
        $lists[$n] = $val;
        heap_adjust($lists, 0, $n);
        //echo "sort: " . $n . "\t" . implode(', ', $lists) . PHP_EOL;
    }
    return $lists;
}

function build_heap(array &$lists)
{
    $n = count($lists) - 1;
    for ($i = floor(($n - 1) / 2); $i >= 0; $i--) {
        heap_adjust($lists, $i, $n + 1);
        //echo "build: " . $i . "\t" . implode(', ', $lists) . PHP_EOL;
    }
    //echo "build ok: " . implode(', ', $lists) . PHP_EOL;
}

function heap_adjust(array &$lists, $i, $num)
{
    if ($i > $num / 2) {
        return;
    }
    $key = $i;
    $leftChild = $i * 2 + 1;
    $rightChild = $i * 2 + 2;

    if ($leftChild < $num && $lists[$leftChild] > $lists[$key]) {
        $key = $leftChild;
    }
    if ($rightChild < $num && $lists[$rightChild] > $lists[$key]) {
        $key = $rightChild;
    }
    if ($key != $i) {
        $val = $lists[$i];
        $lists[$i] = $lists[$key];
        $lists[$key] = $val;
        heap_adjust($lists, $key, $num);
    }
}

7 希尔排序

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。

但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  • 插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率
  • 但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位

算法步骤:

  1. 先将整个待排序的记录序列分割成为若干子序列,分别进行直接插入排序
  2. 待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。

PHP实现代码:

/**
 * 希尔排序 标准
 *
 * @param array $lists
 * @return array
 */
function shell_sort(array $lists)
{
    $n = count($lists);
    $step = 2;
    $gap = intval($n / $step);
    while ($gap > 0) {
        for ($gi = 0; $gi < $gap; $gi++) {
            for ($i = $gi; $i < $n; $i += $gap) {
                $key = $lists[$i];
                for ($j = $i - $gap; $j >= 0 && $lists[$j] > $key; $j -= $gap) {
                    $lists[$j + $gap] = $lists[$j];
                    $lists[$j] = $key;
                }
            }
        }
        $gap = intval($gap / $step);
    }
    return $lists;
}

8 基数排序

基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。

由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。

说基数排序之前,我们简单介绍桶排序:

桶排序是将阵列分到有限数量的桶子里。

每个桶子再个别排序,有可能再使用别的排序算法,或是以递回方式继续使用桶排序进行排序。

桶排序是鸽巢排序的一种归纳结果。

当要被排序的阵列内的数值是均匀分配的时候,桶排序使用线性时间O(n)

但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。

简单来说,就是把数据分组,放在一个个的桶中,然后对每个桶里面的在进行排序。

例如,要对大小为[1..1000]范围内的n个整数A[1..n]排序

首先,可以把桶设为大小为10的范围,具体而言,设集合B[1]存储[1..10]的整数,集合B[2]存储   (10..20]的整数,……集合B[i]存储(   (i-1)*10,   i*10]的整数,i   =   1,2,..100。总共有  100个桶。

然后,对A[1..n]从头到尾扫描一遍,把每个A[i]放入对应的桶B[j]中。  再对这100个桶中每个桶里的数字排序,这时可用冒泡,选择,乃至快排,一般来说任  何排序法都可以。

最后,依次输出每个桶里面的数字,且每个桶中的数字从小到大输出,这  样就得到所有数字排好序的一个序列了。

假设有n个数字,有m个桶,如果数字是平均分布的,则每个桶里面平均有n/m个数字。

如果对每个桶中的数字采用快速排序,那么整个算法的复杂度是

O(n   +   m   *   n/m*log(n/m))   =   O(n   +   nlogn   –   nlogm)

从上式看出,当m接近n的时候,桶排序复杂度接近O(n)

当然,以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的  ,实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中,那就退化成一般的排序了。

前面说的几大排序算法 ,大部分时间复杂度都是O(n2),也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现O(n)的时间复杂度。但桶排序的缺点是:

1)首先是空间复杂度比较高,需要的额外开销大。排序有两个数组的空间开销,一个存放待排序数组,一个就是所谓的桶,比如待排序值是从0到m-1,那就需要m个桶,这个桶数组就要至少m个空间。

2)其次待排序的元素都要在一定的范围内等等。

/**
 * 基数排序
 *
 * @param array $lists
 * @return array
 */
function radix_sort(array $lists)
{
    $radix = 10;
    $max = max($lists);
    $k = ceil(log($max, $radix));
    if ($max == pow($radix, $k)) {
        $k++;
    }
    for ($i = 1; $i <= $k; $i++) {
        $newLists = array_fill(0, $radix, []);
        for ($j = 0; $j < count($lists); $j++) {
            $key = $lists[$j] / pow($radix, $i - 1) % $radix;
            $newLists[$key][] = $lists[$j];
        }
        $lists = [];
        for ($j = 0; $j < $radix; $j++) {
            $lists = array_merge($lists, $newLists[$j]);
        }
    }
    return $lists;
}

9 总结

各种排序的稳定性,时间复杂度、空间复杂度、稳定性总结如下图:

关于时间复杂度:

(1)平方阶(O(n2))排序
各类简单排序:直接插入、直接选择和冒泡排序;

(2)线性对数阶(O(nlog2n))排序
  快速排序、堆排序和归并排序;
(3)O(n1+§))排序,§是介于0和1之间的常数。

希尔排序

(4)线性阶(O(n))排序

基数排序,此外还有桶、箱排序。

关于稳定性:

稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序

不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序

观察者模式

观察者模式,也称发布-订阅模式,定义了一个被观察者和多个观察者的、一对多的对象关系。

在被观察者状态发生变化的时候,它的所有观察者都会收到通知,并自动更新。

观察者模式通常用在实时事件处理系统、组件间解耦、数据库驱动的消息队列系统,同时也是MVC设计模式中的重要组成部分

以下我们以订单创建为例。

当订单创建后,系统会发送邮件短信,并保存日志记录

1 问题

在没有用观察者模式的时候,如下:

class Order
{
    // 订单状态
    private $state = 0;

    // 订单状态有变化时发送通知
    public function addOrder()
    {
        $this->state = 1;
        // 发送邮件
        Email::update($this->state);
        // 短信通知
        Message::update($this->state);
        // 记录日志
        Log::update();
        // 其他更多通知
    }
}

代码中,在Order类中调用各类的方法来实现通知。当在客户端创建订单:

$order = new Order();
$order->addOrder();

就会同时产生三个通知:发送邮件、发送短信和记录日志。

在系统小的时候,这是非常快捷有效的方式。

可是,当系统变大的时候,这种方法马上面临难以扩展的问题,并且容易出错:

  1. 如果订单不需要某种通知,比如不需要记录日志,则必须修改Order类,做状态的判断;
  2. 如果再加一种通知方式,如系统消息通知,则除了增加新类,同时还需要修改Order类和客户端。

这两条都不符合面向对象中的开闭原则,会让系统越来越难维护。

2 解决

接下来我们用观察者模式解决这个问题。

2.1 被观察者

被观察者是一些具体的实例,比如订单管理、用户登陆、评论回复、状态审核等等。

别的功能会依赖于它们的状态进行各种动作。

/**
 * 被观察者接口
 */
interface Observable
{
    // 添加/注册观察者
    public function attach(Observer $observer);
    // 删除观察者
    public function detach(Observer $observer);
    // 触发通知
    public function notify();
}

/**
 * 被观察者
 * 职责:添加观察者到$observers属性中,
 * 有变动时通过notify()方法运行通知
 */
class Order implements Observable
{
    // 保存观察者
    private $observers = array();
    // 订单状态
    private $state = 0;

    // 添加(注册)观察者
    public function attach(Observer $observer)
    {
        $key = array_search($observer, $this->observers);
        if ($key === false) {
            $this->observers[] = $observer;
        }
    }

    // 移除观察者
    public function detach(Observer $observer)
    {
        $key = array_search($observer, $this->observers);
        if ($key !== false) {
            unset($this->observers[$key]);
        }
    }

    // 遍历调用观察者的update()方法进行通知,不关心其具体实现方式
    public function notify()
    {
        foreach ($this->observers as $observer) {
            // 把本类对象传给观察者,以便观察者获取当前类对象的信息
            $observer->update($this);
        }
    }

    // 订单状态有变化时发送通知
    public function addOrder()
    {
        $this->state = 1;
        $this->notify();
    }

    // 获取提供给观察者的状态
    public function getState()
    {
        return $this->state;
    }
}

被观察者至少要实现attach()detach()notify()三个方法,用以添加、删除和通知观察者。

通知的方式是,在类中的其他方法(如:创建订单)调用notify()方法。

另外,观察者可能用到被观察者的一些状态信息。

所以,要在notify()中把当前对象作为参数传给观察者,方便其通过提供的public方法获得被观察者的状态信息。

本例用getState()方法供给观察者获取状态信息。

2.2 观察者

观察者可能有多个,但每个观察者都必须实现Observer接口规定的update()方法,这是接收被观察者通知的唯一渠道。

/**
 * 观察者接口
 */
interface Observer
{
    // 接收到通知的处理方法
    public function update(Observable $observable);
}

/**
 * 观察者1:发送邮件
 */
class Email implements Observer
{
    public function update(Observable $observable)
    {
        $state = $observable->getState();
        if ($state) {
            echo '发送邮件:您已经成功下单。';
        } else {
            echo '发送邮件:下单失败,请重试。';
        }
    }
}

/**
 * 观察者2:短信通知
 */
class Message implements Observer
{
    public function update(Observable $observable)
    {
        $state = $observable->getState();
        if ($state) {
            echo '短信通知:您已下单成功。';
        } else {
            echo '短信通知:下单失败,请重试。';
        }
    }
}

/**
 * 观察者3:记录日志
 */
class Log implements Observer
{
    public function update(Observable $observable)
    {
        echo '记录日志:生成了一个订单记录。';
    }
}

这里有三个观察者:发送邮件短信通知记录日志,它们都实现了update()方法。

其中,发送邮件和短信依赖于订单、也就是被观察者的状态,来决定发送消息的内容,记录日志则不需要订单的状态。

2.3 客户端

然后我们创建一个客户端,内容:

// 创建观察者对象
$email = new Email();
$message = new Message();
$log = new Log();
// 创建订单对象
$order = new Order();

// 向订单对象中注册3个观察者:发送邮件、短信通知、记录日志
$order->attach($email);
$order->attach($message);
$order->attach($log);
// 添加订单,添加时会自动发送通知给观察者
$order->addOrder();

echo '<br />';

// 删除记录日志观察者
$order->detach($log);
// 添加另一个订单,会再次发送通知给观察着
$order->addOrder();

执行应用后,会输出这样的消息:

发送邮件:您已经成功下单。添加日志:生成了一个订单记录。系统消息:您已下单成功。
发送邮件:您已经成功下单。添加日志:生成了一个订单记录。

对于不需要通知的观察者,用detach()移出观察者列表即可。

这种情况就解开了类之间的耦合。

2.4 新增观察者

如果再需要新增一个观察者,如下,只需要添加观察者类本身,实现update()方法。

/**
 * 观察者4:系统消息
 */
class Alert implements Observer
{
    public function update(Observable $observable)
    {
        echo '系统消息:您的订单有更新了~~~';
    }
}

再到客户端中注册Alert类到观察者列表中:

// 创建“系统消息”观察者
$alert = new Alert();
// 注册观察者到订单对象中
$order->attach($alert);

就能订阅被观察者的通知。

3 特点

在观察者模式中,被观察者完全不需要关心观察者,在自身状态有变化是,遍历执行观察者update()方法即完成通知。

在观察者模式中,被观察者通过添加attach()方法,提供给观察者注册,使自己变得可见。

当被观察者改变时,给注册的观察者发送通知。至于观察者如何处理通知,被观察者不需要关心。

这是一种良好的设计,对象之间不必相互理解,同样能够相互通信。

UML如下:

面向对象编程中,任何对象的状态都非常重要,它们是对象间交互的桥梁。

当一个对象的改变需要被其他对象关注时,观察者模式就派上用场了。

策略模式

策略模式定义了一族相同类型的算法,算法之间独立封装,并且可以互换代替

这些算法是同一类型问题的多种处理方式,他们具体行为有差别。

每一个算法、或说每一种处理方式称为一个策略

在应用中,就可以根据环境的不同,选择不同的策略来处理问题。

 

数组输出为例。

数组的输出有序列化输出JSON字符串输出数组格式输出等方式。

每种输出方式都可以独立封装起来,作为一个策略。

应用时,如要把数组保存到数据库中,可以用序列化方式输出。

要提供给APP作接口,可以用JSON字符串输出。

其他程序调用,则直接输出数组格式。

1 问题

在没有设计模式的情况,我们用一个类集中处理数组输出,如下:

/**
 * 根据给定类型,将数组转换后输出
 */
class Output
{
    public function render($array, $type = '')
    {
        if ($type === 'serialize') {
            return serialize($array);
        } elseif ($type === 'json') {
            return json_encode($array);
        } else {
            return $array;
        }
    }
}

客户端直接使用这个类来处理数组,就能达到效果:

/**
 * 客户端代码
 */
$test = ['a', 'b', 'c'];

// 实例化输出类
$output = new Output();

// 直接返回数组
$data = $output->render($test, 'array');

// 返回JSON字符串
$data = $output->render($test, 'json');

这种方法的优点是简单、快捷,在小方案中使用非常合适。

但是,如果是一个复杂方案,包括大量的处理逻辑需要封装,或者处理方式变动较大,则就显得混乱。

当需要添加一种算法,就必须修改Output类,影响原有代码,可扩展性差

如果输出方式很多,if-elseswitch-case语句也会很多,代码混乱难以维护

2 解决

那如何用策略模式解决这个问题呢?

策略模式将各种方案分离开来,让操作者根据具体的需求,动态地选择不同的策略方案。

2.1 策略类

首先,定义一系列的策略类,它们独立封装,并且遵循统一的接口。

/**
 * 策略接口
 */
interface OutputStrategy
{
    public function render($array);
}

/**
 * 策略类1:返回序列化字符串
 */
class SerializeStrategy implements OutputStrategy
{
    public function render($array)
    {
        return serialize($array);
    }
}

/**
 * 策略类2:返回JSON编码后的字符串
 */
class JsonStrategy implements OutputStrategy
{
    public function render($array)
    {
        return json_encode($array);
    }
}

/**
 * 策略类3:直接返回数组
 */
class ArrayStrategy implements OutputStrategy
{
    public function render($array)
    {
        return $array;
    }
}

以后的维护过程中,以上代码都不需修改了。

如果需要增加输出方式,重新建一个类就可以了。

(根据FIG-PSR规范,一个类就是一个独立的PHP文件。)

2.2 环境类

环境角色用来管理策略,实现不同策略的切换功能。

同样,一旦写好,环境角色类以后也不需要修改了。

/**
 * 环境角色类
 */
class Output
{
    private $outputStrategy;

    // 传入的参数必须是策略接口的子类或子类的实例
    public function __construct(OutputStrategy $outputStrategy)
    {
        $this->outputStrategy = $outputStrategy;
    }

    public function renderOutput($array)
    {
        return $this->outputStrategy->render($array);
    }
}

2.3 客户端代码

在客户端中,策略模式通过给予不同的具体策略,来获取不同的结果

/**
 * 客户端代码
 */
$test = ['a', 'b', 'c'];

// 需要返回数组
$output = new Output(new ArrayStrategy());
$data = $output->renderOutput($test);

// 需要返回JSON
$output = new Output(new JsonStrategy());
$data = $output->renderOutput($test);

对于较为复杂的业务逻辑显得更为直观,扩展也更为方便。

3 特点

策略模式主要用来分离算法,根据相同的行为抽象来做不同的具体策略实现。

策略模式结构清晰明了、使用简单直观。并且耦合度相对而言较低,扩展方便。同时操作封装也更为彻底,数据更为安全

当然策略模式也有缺点,就是随着策略的增加,子类也会变得繁多

但缺点并不会影响系统运行,所以在复杂业务中应该考虑使用。

策略模式UML图:

适配器模式

适配器模式,即根据客户端需要,将某个类的接口转换成特定样式的接口,以解决类之间的兼容问题。

如果我们的代码依赖一些外部的API,或者依赖一些可能会经常更改的类,那么应该考虑用适配器模式。

下面我们以集成支付宝支付功能为例。

1 问题

假设支付宝支付类的功能如下:

/**
 * 支付宝支付类
 */
class Alipay
{
    public function sendPayment()
    {
        echo '使用支付宝支付。';
    }
}

// 客户端代码
$alipay = new Alipay();
$alipay->sendPayment();

我们直接实例化Alipay类完成支付功能,这样的客户端代码可能很多。

一段时间后,如果支付宝的Alipay类升级,方法名由sendPayment()变成goPayment()会怎样?

所有用了sendPayment()的客户端代码都要改变。

如果Alipay类频繁升级,或者客户端在很多地方使用,这会是极大的工作量。

2 解决

现在我们用适配器模式来解决。

我们在客户端和Alipay类之间加一个中间类,也就是适配器类,转换原始的Alipay为客户端需要的形式。

为让客户端能调用到统一的类方法,我们先定义一个适配器接口:

/**
 * 适配器接口,所有的支付适配器都需实现这个接口。
 * 不管第三方支付实现方式如何,对于客户端来说,都
 * 用pay()方法完成支付
 */
interface PayAdapter
{
    public function pay();
}

因为Alipay类我们无法控制,而且它有可能经常更新,所以我们不对它做任何修改。

我们新建一个AlipayAdapter适配器类,在pay()中转换Alipay的支付功能,如下:

/**
 * 支付宝适配器
 */
class AlipayAdapter implements PayAdapter
{
    public function pay()
    {
        // 实例化Alipay类,并用Alipay的方法实现支付
        $alipay = new Alipay();
        $alipay->sendPayment();
    }
}

客户端使用方式:

// 客户端代码
$alipay = new AlipayAdapter();
// 用pay()方法实现支付
$alipay->pay();

这样,当Alipay的支付方法改变,只需要修改AlipayAdapter类就可以了。

3 适配新类

有了适配器后,扩展也变得更容易了。

继续以上的例子,在支付宝的基础上,我们再增加微信支付,它与支付宝的支付方式不同,必须通过扫码才能支付。

这种情况也应该使用适配器,而不是直接使用微信的支付功能。

代码如下:

/**
 * 微信支付类
 */
class WechatPay
{
    public function scan()
    {
        echo '扫描二维码后,';
    }

    public function doPay()
    {
        echo '使用微信支付';
    }
}

/**
 * 微信支付适配器
 */
class WechatPayAdapter implements PayAdapter
{
    public function pay()
    {
        // 实例化WechatPay类,并用WechatPay的方法实现支付。
        // 注意,微信支付的方式和支付宝的支付方式不一样,但是
        // 适配之后,他们都能用pay()来实现支付功能。
        $wechatPay = new WechatPay();
        $wechatPay->scan();
        $wechatPay->doPay();
    }
}

客户端使用:

// 客户端代码
$wechat = new WechatPayAdapter();
// 也是用pay()方法实现支付
$wechat->pay();

这就是适配器的扩展特性。

我们创建了一个用于处理第三方类(支付宝、微信支付)的方法,

如果它们的API有变化,我们仅需修改客户端依赖的适配器类就可以,不用修改、暴露第三方类本身。

4 UML图

以上适配器模式的代码对应UML如下:

适配器模式UML

注意:适配器模式中,适配器类的名称和创建方式一定是不会频繁改动的。

对于客户端来说,引用适配器类的方式应该是统一而不变的,这才算是正确使用适配器。

5 总结

大的应用都会不断地加入新库和新API。

为避免它们的变更引发问题,应该用适配器模式包装起来,提供应用统一的引用方式。

它会让我们的代码更具结构化,便于管理和扩展。

单例模式

单例模式,正如其名,允许我们创建一个而且只能创建一个对象的类。

这在整个系统的协同工作中非常有用,特别明确了只需一个类对象的时候。

那么,为什么要实现这么奇怪的类,只实例化一次?

在很多场景下会用到,如:配置类Session类Database类Cache类File类等等。

这些只需要实例化一次,就可以在应用全局中使用。

本文我们以数据库类为例。

1 问题

如果没有使用单例模式,会有什么样的问题?

如下是一个简单的数据库连接类,它没有使用单例模式。

class Database
{
    public $db = null;
    public function __construct($config = array())
    {
        $dsn = sprintf('mysql:host=%s;dbname=%s', $config['db_host'], $config['db_name']);
        $this->db = new PDO($dsn, $config['db_user'], $config['db_pass']);
    }
}

然后创建3个对象:

$config = array(
    'db_name' => 'test',
    'db_host' => 'localhost',
    'db_user' => 'root',
    'db_pass' => 'root'
);

$db1 = new Database($config);
var_dump($db1);
$db2 = new Database($config);
var_dump($db2);
$db3 = new Database($config);
var_dump($db3);

这种情况下,每当我们创建一个这个类的实例,就会新增一个到数据库的连接。

开发者每在一个地方实例化一次这个类,就会在那里多一个数据库连接。

不知不觉中,开发者就犯了个错误,给数据库和服务器性能带来巨大的影响。

上面的代码输入如下:

object(Database)[1]
  public 'db' => object(PDO)[2]
object(Database)[3]
  public 'db' => object(PDO)[4]
object(Database)[5]
  public 'db' => object(PDO)[6]

每个对象都分配一个新的资源ID,都是新的引用,它们占用3个的内存空间。

如果有100个对象创建,就会占用内存中100块不同的空间,而其余99块并非是必须的。

2 解决

开发者怎样使用基础框架,如何数据库连接,这很难控制。

如果在代码评审阶段再找出问题,又会浪费大量的人力物力。

要解决这样的问题,我们可以控制住基类,在源头上限制这个类,使其无法生成多个对象,如果已经生成过,直接返回

于是,我们的目标就是,控制数据库类,使其生成一次而且只能生成一次对象。

如下就是单例模式连接数据库代码:

class Database
{
    // 声明$instance为私有静态类型,用于保存当前类实例化后的对象
    private static $instance = null;
    // 数据库连接句柄
    private $db = null;

    // 构造方法声明为私有方法,禁止外部程序使用new实例化,只能在内部new
    private function __construct($config = array())
    {
        $dsn = sprintf('mysql:host=%s;dbname=%s', $config['db_host'], $config['db_name']);
        $this->db = new PDO($dsn, $config['db_user'], $config['db_pass']);
    }

    // 这是获取当前类对象的唯一方式
    public static function getInstance($config = array())
    {
        // 检查对象是否已经存在,不存在则实例化后保存到$instance属性
        if(self::$instance == null) {
            self::$instance = new self($config);
        }
        return self::$instance;
    }

    // 获取数据库句柄方法
    public function db()
    {
        return $this->db;
    }

    // 声明成私有方法,禁止克隆对象
    private function __clone(){}
    // 声明成私有方法,禁止重建对象
    private function __wakeup(){}
}

再通过getInstance()方法使用类对象,

$config = array(
    'db_name' => 'test',
    'db_host' => 'localhost',
    'db_user' => 'root',
    'db_pass' => 'root'
);

$db1 = Database::getInstance($config);
var_dump($db1);
$db2 = Database::getInstance($config);
var_dump($db2);
$db3 = Database::getInstance($config);
var_dump($db3);

输出信息如下:

object(Database)[1]
  private 'db' => object(PDO)[2]
object(Database)[1]
  private 'db' => object(PDO)[2]
object(Database)[1]
  private 'db' => object(PDO)[2]

对比两个输出可以看出,单例模式中,不同对象获得的资源ID是一样的。

也就是说,虽然我们用getInstance()获取Database类对象3次,其实引用的是一个内存空间,PDO也只连接了数据库一次。

以上的例子是数据库连接类,要使用数据库,在应用这样获得连接句柄:

$db = database::getInstance($config)->db();

如果是其他类,则按需要修改数据库相关的代码,单例实现部分保留。

3 特点

单例模式的特点是4私1公一个私有静态属性,构造方法私有,克隆方法私有,重建方法私有,一个公共静态方法。

其他方法根据需要增加。

最基础的单例模式代码如下:

class Singleton
{
    private static $instance = null;

    public static function getInstance()
    {
        if(self::$instance == null) {
            self::$instance = new self();
        }
        return self::$instance;
    }

    private function __construct(){}
    private function __clone(){}
    private function __wakeup(){}
}

$instance用以保存类的实例化,getInstance()方法提供给外部本类的实例化对象:

对应的UML图如下,

PHP单例模式

单例模式在应用请求的整个生命周期中都有效,这点类似全局变量,会降低程序的可测试性。

大部分情况下,也可以用依赖注入来代替单例模式,避免在应用中引入不必要的耦合。

所以,对于仅需生成一个对象的类,首先考虑用依赖注入方式,其次考虑用单例模式来实现。

简单工厂模式

工厂模式,就是负责生成其他对象的类或方法。

1 类实现

比如,我们有一些类,它们都继承自交通工具类:

interface Vehicle
{
    public function drive();
}

class Car implements Vehicle
{
    public function drive()
    {
        echo '汽车靠四个轮子滚动行走。';
    }
}

class Ship implements Vehicle
{
    public function drive()
    {
        echo '轮船靠螺旋桨划水前进。';
    }
}

class Aircraft implements Vehicle
{
    public function drive()
    {
        echo '飞机靠螺旋桨和机翼的升力飞行。';
    }
}

再创建一个工厂类,专门用作类的创建,:

class VehicleFactory
{
    public static function build($className = null)
    {
        $className = ucfirst($className);
        if ($className && class_exists($className)) {
            return new $className();
        }
        return null;
    }
}

工厂类用了一个静态方法来创建其他类,在客户端中就可以这样使用:

VehicleFactory::build('Car')->drive();
VehicleFactory::build('Ship')->drive();
VehicleFactory::build('Aircraft')->drive();

省去了每次都要new类的工作。

UML类图详解

UML类图是一种结构图,用于描述一个系统的静态结构。类图以反映类结构和类之间关系为目的,用以描述软件系统的结构,是一种静态建模方法。类图中的类,与面向对象语言中的类的概念是对应的。

1 类结构

在类的UML图中,使用长方形描述一个类的主要构成,长方形垂直地分为三层,以此放置类的名称属性方法

其中,

一般类的类名用正常字体粗体表示,如上图;抽象类名用斜体字粗体,如User;接口则需在上方加上<<interface>>

属性和方法都需要标注可见性符号,+代表public#代表protected-代表private

另外,还可以用冒号:表明属性的类型和方法的返回类型,如+$name:string+getName():string。当然,类型说明并非必须。

2 类关系

类与类之间的关系主要有六种:继承实现组合聚合关联依赖,这六种关系的箭头表示如下,

接着我们来了解类关系的具体内容。

3 六种类关系

六种类关系中,组合聚合关联这三种类关系的代码结构一样,都是用属性来保存另一个类的引用,所以要通过内容间的关系来区别。

3.1 继承

继承关系也称泛化关系(Generalization),用于描述父类与子类之间的关系。父类又称作基类,子类又称作派生类。

继承关系中,子类继承父类的所有功能,父类所具有的属性、方法,子类应该都有。子类中除了与父类一致的信息以外,还包括额外的信息。

例如:公交车、出租车和小轿车都是汽车,他们都有名称,并且都能在路上行驶。

PHP代码实现如下:

<?php

class Car
{
    public $name;
    public function run()
    {
        return '在行驶中';
    }
}

class Bus extends Car
{
    public function __construct()
    {
        $this->name = '公交车';
    }
}

class Taxi extends Car
{
    public function __construct()
    {
        $this->name = '出租车';
    }
}

// 客户端代码
$line2 = new Bus;
echo $line2->name . $line2->run();

3.2 实现

实现关系(Implementation),主要用来规定接口和实现类的关系

接口(包括抽象类)是方法的集合,在实现关系中,类实现了接口,类中的方法实现了接口声明的所有方法。

例如:汽车和轮船都是交通工具,而交通工具只是一个可移动工具的抽象概念,船和车实现了具体移动的功能。
实现关系

<?php

interface Vehicle
{
    public function run();
}

class Car implements Vehicle
{
    public $name = '汽车';
    public function run()
    {
        return $this->name . '在路上行驶';
    }
}

class Ship implements Vehicle
{
    public $name = '轮船';
    public function run()
    {
        return $this->name . '在海上航行';
    }
}

// 客户端代码
$car = new Car;
echo $car->run();

3.3 组合关系

组合关系(Composition):整体与部分的关系,但是整体与部分不可以分开

组合关系表示类之间整体与部分的关系,整体和部分有一致的生存期。一旦整体对象不存在,部分对象也将不存在,是同生共死的关系。

例如:人由头部和身体组成,两者不可分割,共同存在。
组合关系
<?php

class Head
{
    public $name = '头部';
}

class Body
{
    public $name = '身体';
}

class Human
{
    public $head;
    public $body;

    public function setHead(Head $head)
    {
        $this->head = $head;
    }

    public function setBody(Body $body)
    {
        $this->body = $body;
    }

    public function display()
    {
        return sprintf('人由%s和%s组成', $this->head->name, $this->body->name);
    }
}

// 客户端代码
$man = new Human();
$man->setHead(new Head());
$man->setBody(new Body());
echo $man->display();

3.4 聚合关系

聚合关系(Aggregation):整体和部分的关系,整体与部分可以分开。

聚合关系也表示类之间整体与部分的关系,成员对象是整体对象的一部分,但是成员对象可以脱离整体对象独立存在。

例如:公交车司机和工衣、工帽是整体与部分的关系,但是可以分开,工衣、工帽可以穿在别的司机身上,公交司机也可以穿别的工衣、工帽。

<?php

class Clothes
{
    public $name = '工衣';
}

class Hat
{
    public $name = '工帽';
}

class Driver
{
    public $clothes;
    public $hat;

    public function wearClothes(Clothes $clothes)
    {
        $this->clothes = $clothes;
    }

    public function wearHat(Hat $hat)
    {
        $this->hat = $hat;
    }

    public function show()
    {
        return sprintf('公交车司机穿着%s和%s', $this->clothes->name, $this->hat->name);
    }
}

// 客户端代码
$driver = new Driver();
$driver->wearClothes(new Clothes());
$driver->wearHat(new Hat());
echo $driver->show();

3.5 关联关系

关联关系(Association):表示一个类的属性保存了对另一个类的一个实例(或多个实例)的引用

关联关系是类与类之间最常用的一种关系,表示一类对象与另一类对象之间有联系。组合、聚合也属于关联关系,只是关联关系的类间关系比其他两种要弱。

关联关系有四种:双向关联单向关联自关联多重数关联

例如:汽车和司机,一辆汽车对应特定的司机,一个司机也可以开多辆车。

在UML图中,双向的关联可以有两个箭头或者没有箭头,单向的关联或自关联有一个箭头。上图对应的PHP代码如下:

<?php

class Driver
{
    public $cars = array();
    public function addCar(Car $car)
    {
        $this->cars[] = $car;
    }
}

class Car
{
    public $drivers = array();
    public function addDriver(Driver $driver)
    {
        $this->drivers[] = $driver;
    }
}

// 客户端代码
$jack = new Driver();
$line1 = new Car();
$jack->addCar($line1);
$line1->addDriver($jack);
print_r($jack);

在多重性关系中,可以直接在关联直线上增加一个数字,表示与之对应的另一个类的对象的个数。

  • 1..1:仅一个
  • 0..*:零个或多个
  • 1..*:一个或多个
  • 0..1:没有或只有一个
  • m..n:最少m、最多n个 (m<=n)

3.6 依赖关系

依赖关系(Dependence):假设A类的变化引起了B类的变化,则说名B类依赖于A类。

大多数情况下,依赖关系体现在某个类的方法使用另一个类的对象作为参数

依赖关系是一种“使用”关系,特定事物的改变有可能会影响到使用该事物的其他事物,在需要表示一个事物使用另一个事物时使用依赖关系。

例如:汽车依赖汽油,如果没有汽油,汽车将无法行驶。
依赖关系
<?php
class Oil
{
    public $type = '汽油';
    public function add()
    {
        return $this->type;
    }
}

class Car
{
    public function beforeRun(Oil $oil)
    {
        return '添加' . $oil->add();
    }
}

// 客户端代码
$car = new Car;
echo $car->beforeRun(new Oil());

4 总结

这六种类关系中,组合、聚合和关联的代码结构一样,可以从关系的强弱来理解,各类关系从强到弱依次是:继承→实现→组合→聚合→关联→依赖。如下是完整的一张UML关系图。

(点击图片查看大图)

UML类图是面向对象设计的辅助工具,但并非是必须工具,如果暂时不理解本文的内容,可以继续看设计模式部分,并不会影响。

说明:本文所有UML类图均使用免费的UMLet工具,在比较了Viso和StartUML后,感觉UMLet要好用很多,强烈推荐使用。另外,本文所有的UML类图源文件请点里下载

PHP生成特定长度的纯字母字符串

PHP中,md5()uniqid()函数可以返回32位和13位不重复的字符串,但是这些字符串都可能包含有数字。如果需要纯字母的字符串,而且长度不定,比如8位,那么直接用这两个函数无法达到效果。

这时可以考虑从ASCII码加mt_rand()函数的角度考虑,因为A~Z的ASCII码是65~90a~z的ASCII码是97~122,所以程序可以这么写:

// 生成纯字母字符串函数
function rand_string($length = 8) {
    $randstr = "";
    for ($i = 0; $i < (int) $length; $i ++) {
        $randnum = mt_rand(0, 51);
        if ($randnum < 26) {
            $randstr .= chr($randnum + 65); // A-Z之间字符
        } else {
            $randstr .= chr($randnum + 71); // a-z之间字符
        }
    }
 
    return $randstr;
}

// 输出8位长度的纯字母字符串
echo rand_string(8);

默认长度是8位,可以根据需要传入长度。