PHP设计模式笔记：使用PHP实现享元模式

PHP设计模式笔记：使用PHP实现享元模式

【意图】
运用共享技术有效的支持大量细粒度的对象
享元模式变化的是对象的存储开销

【享元模式结构图】

享元模式

享元模式

【享元模式中主要角色】
抽象享元(Flyweight)角色：此角色是所有的具体享元类的超类，为这些类规定出需要实现的公共接口。那些需要外蕴状态的操作可以通过调用商业以参数形式传入
具体享元(ConcreteFlyweight)角色：实现Flyweight接口，并为内部状态（如果有的话）拉回存储空间。ConcreteFlyweight对象必须是可共享的。它所存储的状态必须是内部的
不共享的具体享元（UnsharedConcreteFlyweight）角色：并非所有的Flyweight子类都需要被共享。Flyweigth使共享成为可能，但它并不强制共享。
享元工厂(FlyweightFactory)角色：负责创建和管理享元角色。本角色必须保证享元对象可能被系统适当地共享
客户端(Client)角色：本角色需要维护一个对所有享元对象的引用。本角色需要自行存储所有享元对象的外部状态

【享元模式的优点和缺点】
享元模式的优点：Flyweight模式可以大幅度地降低内存中对象的数量。

享元模式的缺点：
1、Flyweight模式使得系统更加复杂
2、Flyweigth模式将享元对象的状态外部化，而读取外部状态使得运行时间稍微变长

【享元模式适用场景】
当以下情况都成立时使用Flyweight模式：
1、一个应用程序使用了大量的对象
2、完全由于使用大量的对象，造成很大的存储开销
3、对象的大多数状态都可变为外部状态
4、如果删除对象的外部状态，那么可以用相对较少的共享对象取代很多组对象
5、应用程序不依赖于对象标识。

【享元模式与其它模式】
单例模式(Singleton)：客户端要引用享元对象，是通过工厂对象创建或者获得的，客户端每次引用一个享元对象，都是可以通过同一个工厂对象来引用所需要的享元对象。因此，可以将享元工厂设计成单例模式，这样就可以保证客户端只引用一个工厂实例。因为所有的享元对象都是由一个工厂对象统一管理的，所以在客户端没有必要引用多个工厂对象。不管是单纯享元模式还是复合享元模式中的享元工厂角色，都可以设计成为单例模式，对于结果是不会有任何影响的。
Composite模式：复合享元模式实际上是单纯享元模式与合成模式的组合。单纯享元对象可以作为树叶对象来讲，是可以共享的，而复合享元对象可以作为树枝对象，因此在复合享元角色中可以添加聚集管理方法。

【享元模式PHP示例】

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

<?php
 
/**
 * 享元模式的PHP简单实现 2010-08-03 sz
 * @author 胖子 phppan.p#gmail.com  http://www.phppan.com
 * 哥学社成员（http://www.blog-brother.com/）
 * @package design pattern
 */
 
/**
 * 抽象享元角色
 */
abstract class Flyweight {
 
    /**
     * 示意性方法
     * @param string $state 外部状态
     */
    abstract public function operation($state);
}
 
/**
 * 具体享元角色
 */
class ConcreteFlyweight extends Flyweight {
 
    private $_intrinsicState = null;
 
    /**
     * 构造方法
     * @param string $state  内部状态
     */
    public function __construct($state) {
        $this->_intrinsicState = $state;
    }
 
    public function operation($state) {
        echo 'ConcreteFlyweight operation, Intrinsic State = ' . $this->_intrinsicState
        . ' Extrinsic State = ' . $state . '<br />';
    }
 
}
 
/**
 * 不共享的具体享元，客户端直接调用
 */
class UnsharedConcreteFlyweight extends Flyweight {
 
    private $_intrinsicState = null;
 
    /**
     * 构造方法
     * @param string $state  内部状态
     */
    public function __construct($state) {
        $this->_intrinsicState = $state;
    }
 
    public function operation($state) {
        echo 'UnsharedConcreteFlyweight operation, Intrinsic State = ' . $this->_intrinsicState
        . ' Extrinsic State = ' . $state . '<br />';
    }
 
}
 
/**
 * 享元工厂角色
 */
class FlyweightFactory {
 
    private $_flyweights;
 
    public function __construct() {
        $this->_flyweights = array();
    }
 
    public function getFlyweigth($state) {
        if (isset($this->_flyweights[$state])) {
            return $this->_flyweights[$state];
        } else {
            return $this->_flyweights[$state] = new ConcreteFlyweight($state);
        }
    }
 
}
 
/**
 * 客户端
 */
class Client {
 
    /**
     * Main program.
     */
    public static function main() {
        $flyweightFactory = new FlyweightFactory();
        $flyweight = $flyweightFactory->getFlyweigth('state A');
        $flyweight->operation('other state A');
 
        $flyweight = $flyweightFactory->getFlyweigth('state B');
        $flyweight->operation('other state B');
 
        /* 不共享的对象，单独调用 */
        $uflyweight = new UnsharedConcreteFlyweight('state A');
        $uflyweight->operation('other state A');
    }
 
}
 
Client::main();
?>

【复合享元模式】
复合享元模式对象是由一些单纯享元使用合成模式加以复合而成
复合享元角色所代表的对象是不可以共享的，但是一个复合享元对象可以分解成为多个本身是单纯享元对象的组合。

【复合享元模式PHP示例】

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

<?php
 
/**
 * 复合享元模式的PHP简单实现 2010-08-03 sz
 * 《Java与模式》中的示意性源码的PHP修改版本
 * @author 胖子 phppan.p#gmail.com  http://www.phppan.com
 * 哥学社成员（http://www.blog-brother.com/）
 * @package design pattern
 */
 
/**
 * 抽象享元角色
 */
abstract class Flyweight {
 
    /**
     * 示意性方法
     * @param string $state 外部状态
     */
    abstract public function operation($state);
}
 
/**
 * 具体享元角色
 */
class ConcreteFlyweight extends Flyweight {
 
    private $_intrinsicState = null;
 
    /**
     * 构造方法
     * @param string $state  内部状态
     */
    public function __construct($state) {
        $this->_intrinsicState = $state;
    }
 
    public function operation($state) {
        echo 'ConcreteFlyweight operation, Intrinsic State = ' . $this->_intrinsicState
        . ' Extrinsic State = ' . $state . '<br />';
    }
 
}
 
/**
 * 不共享的具体享元，客户端直接调用
 */
class UnsharedConcreteFlyweight extends Flyweight {
 
    private $_flyweights;
 
    /**
     * 构造方法
     * @param string $state  内部状态
     */
    public function __construct() {
        $this->_flyweights = array();
    }
 
    public function operation($state) {
        foreach ($this->_flyweights as $flyweight) {
            $flyweight->operation($state);
        }
    }
 
    public function add($state, Flyweight $flyweight) {
        $this->_flyweights[$state] = $flyweight;
    }
 
}
 
/**
 * 享元工厂角色
 */
class FlyweightFactory {
 
    private $_flyweights;
 
    public function __construct() {
        $this->_flyweights = array();
    }
 
    public function getFlyweigth($state) {
        if (is_array($state)) { //  复合模式
            $uFlyweight = new UnsharedConcreteFlyweight();
 
            foreach ($state as $row) {
                $uFlyweight->add($row, $this->getFlyweigth($row));
            }
            return $uFlyweight;
        } else if (is_string($state)) {
            if (isset($this->_flyweights[$state])) {
                return $this->_flyweights[$state];
            } else {
                return $this->_flyweights[$state] = new ConcreteFlyweight($state);
            }
        } else {
            return null;
        }
    }
 
}
 
/**
 * 客户端
 */
class Client {
 
    /**
     * Main program.
     */
    public static function main() {
        $flyweightFactory = new FlyweightFactory();
        $flyweight = $flyweightFactory->getFlyweigth('state A');
        $flyweight->operation('other state A');
 
        $flyweight = $flyweightFactory->getFlyweigth('state B');
        $flyweight->operation('other state B');
 
        /* 复合对象*/
        $uflyweight = $flyweightFactory->getFlyweigth(array('state A', 'state B'));
        $uflyweight->operation('other state A');
    }
 
}
 
Client::main();
?>

【PHP中享元模式的地位】
相对于其它模式，Flyweight模式在PHP的现有版本中没有太大的意义，因为PHP的生命周期是页面级的
即从一个PHP文件执行开始会载入所需的资源，当执行完毕后，这些所有的资源会被全部释放。
而一般来说我们也不会让一个页面执行太长时间。

PHP源码阅读笔记二十六：PHP快速排序源码实现的简化版本

PHP源码阅读笔记：PHP中的快速排序实现的简化版本
这段时间在复习数据结构，有看到排序及经典的快速排序
于是有了看下PHP中实现排序的方式，在Zend目录下我们可以看到zend_qsort.c文件及zend_qsort.h文件
这是PHP实现快速排序的文件所在
从代码中我们可以看到，也许是为了兼容多种数据类型，所以其在交换及比较位置比较复杂，看起来也比较纠结，于是自己将
其中的类型全部换成int类型，得到简化版本的PHP源码中的快速排序
其代码如下 ：

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

#include <stdio.h>
 
static qsort_swap(int *a, int *b)
{
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}
 
void qsort(int *base, int nmemb)
{
	int *begin_stack[10];
	int *end_stack[10];
	int *begin;
	int *end;
	int *seg1;
	int *seg2;
	int *seg2p;
	int loop;
	unsigned int offset;
 
	/* 使用栈而不是常见的递归实现 */
	begin_stack[0] = base;	//	开始元素位置栈，入栈
	end_stack[0]   = base + (nmemb - 1) ;	//	结束位置栈，入栈
 
	for (loop = 0; loop >= 0; --loop) {
		begin = begin_stack[loop];	//	开始位置出栈
		end   = end_stack[loop];	//	结束位置出栈
 
		while (begin < end) {
			offset = (end - begin) >> 1;	//	取中间位置
 
			qsort_swap(begin, begin + offset);	//	交换开始和中间的位置
 
			seg1 = begin;
			seg2 = end;
 
			while (1) {
				for (; seg1 < seg2 && *begin < *seg1 ; seg1 += 1);
 
				for (; seg2 >= seg1 && *seg2 > *begin; seg2 -= 1);
 
				if (seg1 >= seg2)
					break;
 
				qsort_swap(seg1, seg2);
			}
 
			qsort_swap(begin, seg2);
 
			seg2p = seg2;
 
			if ((seg2p - begin) <= (end - seg2p)) {
				if (seg2p < end) {	//	右侧入栈
					begin_stack[loop] = seg2p + 1;
					end_stack[loop++] = end;
				}
				end = seg2p;
			} else {
				if (seg2p > begin) {	// 左侧入栈
					begin_stack[loop] = begin;
					end_stack[loop++] = seg2p - 1;
				}	//	end if
				begin = seg2p;
			}	//	end if
		}	//	end while
	}	//	end for
 
}
int main(int argc, char *argv[])
{
	int a[10] = {14, 5, 7, 8, 2, 4, 55, 3};
	int i;
	qsort(a, 8);
	for (i = 0; i < 8;i++) 
	{
		printf("%d ", a[i]);
	}
	return 0;
}

看完后，有一个感受：强大的指针，受益非浅！

数据结构复习笔记：使用PHP实现内排序之冒泡排序和简单选择排序

数据结构复习笔记：使用PHP实现内排序之冒泡排序和简单选择排序
【基本概念】
排序：排序是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列
内排序：内排序指的是待排序记录在放在计算机随机存储器中进行的排序过程
内排序大致可分为插入排序、交换排序、选择排序、归并排序和计数排序
在排序的过程中需要进行两种基本操作：1、比较两个关键字的大小，2、将记录从一个位置移动到另一个位置
【冒泡排序过程】
首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较批二个记录和第三个记录的关键字，依次类推，直至第n-1个元素和第n个元素进行过比较为止。以上为一次冒泡排序，礤结果是使得关键字最大的记录被安置到最后一个记录的位置上。然后进行第二真趟冒泡排序，对前n-1个记录进行同样操作，其结果是使关键字次大的记录安置到第n-1人的位置上，如此类似
【冒泡排序的PHP实现】

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

<?php
/**
 * 数据结构中冒泡排序PHP实现 2010-07-26 sz
 * @author phppan.p#gmail.com  http://www.phppan.com                                                    
 * 哥学社成员（http://www.blog-brother.com/）
 * @package data struct
 */
 
/**
 * 冒泡排序 将数组从小到排序
 * @param array $array 需要排序的数据
 * @return array
 */
function bubble_sort($array) {
    if (!is_array($array)) {
        return FALSE;
    }
 
    $len = count($array);
    for ($i = 0; $i < $len - 1; $i++) {
        for ($j = 0; $j < $len - $i - 1; $j++) {
            if ($array[$j] > $array[$j + 1]) {
                $temp = $array[$j];
                $array[$j] = $array[$j + 1];
                $array[$j + 1] = $temp;
            }
        }
    }
 
    return $array;
}
 
/* 示例 */
$array = array(3, 2, 1, 4, 6, 7, 8, 0, 55);
var_dump(bubble_sort($array));
?>

【简单选择排序的过程】
选择排序的基本思想是：每一趟在n-i+1(i = 1,2,…,n-1)个记录中选择关键字最小的记录作为有序序列中第i个记录
其中最简单的是简单选择排序，其过程如下：
通过n-i次关键字间的比较，从n-i+1个记录中选择出关键字最小的记录，并各第i个记录交换之。
【简单选择排序的PHP实现】

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

<?php
/**
 * 数据结构中简单选择排序PHP实现 2010-07-26 sz
 * @author phppan.p#gmail.com  http://www.phppan.com                                                 
 * 哥学社成员（http://www.blog-brother.com/）
 * @package data struct
 */
 
/**
 * 简单选择排序，将数组从小到大排序
 * @param array $array 需要进行排序的数组
 * @return array $array
 */
function select_sort($array) {
    if (!is_array($array)) {
        return FALSE;
    }
 
    $len = count($array);
    for ($i = 0; $i < $len - 1; $i++) {
        for ($j = $i + 1; $j < $len; $j++) {
            if ($array[$i] > $array[$j]) {
                $temp = $array[$i];
                $array[$i] = $array[$j];
                $array[$j] = $temp;
            }
        }
    }
 
    return $array;
}
 
/* 示例 */
$array = array(3, 2, 1, 4, 6, 7, 8, 0, 55);
var_dump(select_sort($array));
?>

温故知新，以前对这两种排序方式一直模糊不清，总算了结了