On the way day day up...

设计模式——单例模式&工厂方法

单例模式

单例模式保证类只有一个实例,并且自行实例化,并向整个系统提供这个实例

特点

  1. 这个类只能有一个实例;
  2. 必须自行创建这个实例;
  3. 必须向系统提供访这个实例的访问方法;

实现

class singleton{

	private static $instance;
	//防止外界实例化对象,构造函数为私有,不能被外面实例化
	private function __construct(){
		echo "this is __construct \n";
	}
	//防止外界克隆对象
	private function __clone(){
	}
	public static function getInstance(){
		if(empty(self::$instance)){
			self::$instance = new singleton();//实例化
			return self::$instance;
		}else{
			return self::$instance;
		}
	}
}

$test = singleton::getInstance();//直接调用类的静态方法

//$test2 = clone $test;//不能clone,因为__clone为私有
//new singleton();//不能实例化,因为构造函数__construct为私有

工厂方法

主要步骤:

  1. 定义一个抽象类(基类),定义一些抽象方法(接口规范)
  2. 继承该抽象类,实现抽象方法
  3. 定义工厂类,实例化对象

实现

//抽象类,基类
abstract class Cache_Abstract{

	abstract public function getKey($key);
	abstract public function setKey($key, $value);
}

//子类,集成抽象类
class File_Cache extends Cache_Abstract{

	public function getKey($key){
		//...
		return $key;
	}

	public function setKey($key, $value){
		//...
		return $key;
	}
}

class Apc_Cache extends Cache_Abstract{

	public function getKey($key){
		//...
		return $key;
	}

	public function setKey($key, $value){
		//...
		return $key;
	}
}

//工厂类
class Cache{

	//根据需要,实例化相应的类
	public function factory($strEngine='', $arrOptions=array()){

		switch($strEngine){

			case 'file':
				$objEngine = new File_Cache($arrOptions);
				break;
			case 'apc':
				$objEngine = new Apc_Cache($arrOptions);
				break;
			default:
				$objEngine = new Apc_Cache($arrOptions);
				break;
		}

		return $objEngine;
	}
}

redis基本概念简介

redis是一个开源的、key-value的内存数据库

redis数据库

每个redis服务器都会创建一个redisServer结构体类型的变量,存储服务器的各种信息。

数据库相关的信息保存在redisServer中的 redisDb *db 数组中,数组中的每个元素都是一个redisDb结构体变量,代表一个数据库。db数组中有多少个元素,就代表该redisServer有多少个数据库,一般默认16个。一般情况下,默认使用0号数据库。

数据库redisDb结构:

typedef struct redisDb{
	//字典类型,保存数据库的所有键值对(即数据),称作键空间
	//键空间的键就是数据库的键,每个键都是一个字符串对象
	//键空间的值就是数据库的值,每个值可以是字符串对象,列表对象,哈希表对象,集合对象,有序集合对象
	dict *dict;
	//字典类型,保存数据库键的过期时间,成为过期字典
	//过期字典的键是一个指针,指向键空间的某个键对象(数据库键)
	//过期字典的值是一个long long类型的整数,保存了键所指向的数据库键的过期时间(ms精度的unix时间戳)
	dict *expires;
	...
}

redis过期策略

redis采用惰性删除定期删除相结合的过期键删除策略。

惰性删除是指,每次从键空间获取键时,都检查该建是否过期,如果过期就删除,没过期就返回。

定期删除是指,每隔一段时间,就检查数据库,删除里面的过期键。删除多少过期键以及检查多少数据库,则由算法决定。redise的策略是,在规定时间内,分多次遍历服务器中的各个数据库,从数据库的expires字典中随机检查一部分键的过期时间,并删除其中的过期键。

redis持久化

RDB持久化

  • RDB持久化功能可以将redis某个时间点上的数据库状态保存到一个RDB文件中,该文件是一个经过压缩的二进制文件;
  • RDB持久化可以手动触发,也可以根据服务器配置定期执行。手动触发的话,SAVE命令会阻塞Redis服务器进程,BGSAVE命令会fork一个子进程来创建RDB文件,不会影响服务器进程处理命令。
  • 服务器启动时,会先检查是否开启了AOF持久化功能(AOF文件的更新频率通常比RDB高),如果开启,优先使用AOF文件还原数据库状态,如果未开启,再载入RDB文件。

AOF持久化

  • AOF(Append Only FIle)持久化是通过保存Redis服务器所执行的写命令来记录数据库状态的;
  • AOF文件中的所有命令都以Redis命令请求协议的格式保存;
  • AOF重写——读取数据库中的键值对,然后用一条命令记录键值对,代替之前记录这个键值对的多条命令,这就是重写原理。

redis复制

旧版复制功能

分为同步命令传播两个阶段:

  1. slave向master发送SYNC命令,master生成RDB文件,同时从现在开始记录命令到缓冲区;

  2. slave接收RDB文件,根据RDB文件同步数据;

  3. master将缓冲区中的命令发送给slave,slave状态同步至与master状态一致;

  4. 后续master执行命令后,同步传送给slave——命令传播

缺点

这种方式的缺点是,如果slave在命令传播阶段突然断开与master的连接,几秒后又重新建立连接,那么这时候需要重新执行上述过程,同步所有数据。其实,断开连接之前的数据是没必要再同步的。这样浪费了cpu、IO、带宽等资源。

新版复制功能

新增了部分重同步的功能,就是说,上述slave断开重连的情况,可以只同步断开后的命令。

新版复制用PSYNC命令代替SYNC命令,支持完整重同步部分重同步。其中,完整重同步与老的同步机制类似。这里主要说下部分重同步

部分重同步

部分重同步通过主从服务器的复制偏移量主服务器的复制积压缓冲区服务器运行ID这3部分实现。

  1. 主从服务器都会维护一个复制偏移量offset,主服务器每传播N个字节,offset值加N,从服务器收到这N个字节后,也把自己的offset加N;

  2. 主服务器维护一个固定长度的先进先出队列,默认1MB,近期传播的命令会保存在这里,并且队列中的每个字节都有一个编号,就是复制偏移量offset。

  3. 从服务器重新连接后,会发送之前保存的主服务器的ID,如果与当前连接的主服务器ID相同,则进行部分重同步,如果不同,则说明当前主服务器并不是之前的,所以需要从新全部同步(ps: 每个redis服务器都有自己的运行ID,是在服务器启动时自动生成的,有40个随机的十六进制字符组成)

另外,如果在命令传播过程中,master发送的命令slave没有收到怎么办?比如,master这边的offset偏移了40,而slave没收到这40字节,所以offset就不会偏移,这时主从服务器的状态就不一致了。

为了解决这个问题,redis2.8版本新增了心跳检查功能,slave以每秒一次的频率向master发送REPLCONF ACK 命令,告诉master自己当前的offset是多少,如果master发现slave和自己的offset不一致,就会把丢掉的那些命令重新发送一次。

算法基础题——链表

链表

1. 单链表倒置

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct ListNode{
	char value;
	struct ListNode * next;
}ListNode;


//单链表倒置——头插法
ListNode * listReverse(ListNode * head){
	if(NULL == head){
		return NULL;
	}
	if(NULL == head->next){
		return head;
	}

	ListNode * p = head->next;
	head->next = NULL;
	ListNode * tmp;
	while(p){
		tmp = p->next;
		p->next = head->next;
		head->next = p;
		p = tmp;
	}
	
	return head;
}
//创建单链表
ListNode * makeList(char * src, ListNode *head){
	if(NULL == src){
		return NULL;
	}
	//创建头结点
	head = (ListNode *) malloc(sizeof(ListNode));
	head->next = NULL;
	ListNode *p = head;

	while(*src != '\0'){
		ListNode * node = (ListNode *) malloc(sizeof(ListNode));
		if(NULL == node){
			return NULL;
		}
		p->next = node;
		p = p->next;
		p->value = *src;
		p->next = NULL;
		src++;
	}

	return head;
}

int main(){
	char *src = "abcde";
	ListNode * head, *tmp;
	head = makeList(src, head);
	tmp = head;
	do{
		tmp = tmp->next;
		printf("######%c\n", tmp->value);
	}while(tmp->next);
	
	head = listReverse(head);
	tmp = head;
	do{
		tmp = tmp->next;
		printf("******%c\n", tmp->value);
	}while(tmp->next);
	
	free(head);//释放malloc分配的堆空间
	head = NULL;//释放后,将指针置为NULL,防止后面的程序误用
}

2. 单链表相交

3. 链表是否有环

4. 从无头链表中删除节点

算法基础题——树

1. 重建二叉树

2. 分层遍历二叉树

3. 求二叉树深度

算法基础题——数组

数组

1. 排序算法——快速排序

#include <stdio.h>

void quickSort(int src[], int start, int end){
	
	if(start >= end){
		return;
	}
 
	int i = start;
	int j = end;
	int value = src[i];
	int tmp = i;
	while(i < j){
		while(i < j && src[j] >= value){
			j--;
		}
		src[tmp] = src[j];
		tmp = j;

		while(i < j && src[i] <= value){
			i++;
		}
		src[tmp] = src[i];
		tmp = i;
	}
	src[i] = value;

	quickSort(src, start, i-1);
	quickSort(src, i+1, end);
	return;
}

int main(){

	int src[] = {34,45,21,18,4,9,25,90};
	quickSort(src, 0, 7);
	for(int i=0; i<8; i++){
		printf("%d\n", src[i]);
	}
 }

2. 排序算法——冒泡排序

#include <stdio.h>

int * bubble(int src[], int n){

	if(n <=1){
		return src;
	}
	int i,j,tmp;
	for(i=0; i<n; i++){
		for(j=i+1; j<n; j++){
			if(src[j] < src[i]){
				tmp = src[j];
				src[j] = src[i];
				src[i] = tmp;
			}
		}
	}

	return src;
}

int main(){
	int src[8] = {3,11,8,10,7,23,5,7};
	bubble(src, 8);
	for(int i=0;i<8;i++){
		printf("%d\n", src[i] );
	}

}

3. 排序算法——插入排序

4. 折半查找/二分查找

#include <stdio.h>
#include <string.h>

int search(int src[], int len, int value){
	
	int start = 0;
	int end = len - 1;
	
	int mid;

	while(start <= end){
		mid = (start + end) >> 1 ;
		if(value == src[mid]){
			return mid;
		}else if(value > src[mid]){
			start = mid + 1;
		}else{
			end = mid - 1;
		}
	}
	
	return -1;
}

int main(){

	int src[] = {1,2,3,4,5,6,7};
	int res = search(src, 7, 7);
	printf("%d\n", res);
}

5. 求前K大的数

6. 寻找数组中的最大值和最小值

7. AB两个有序数组,元素去重合并

//mergeArray.cpp
#include <stdio.h>
int * mergeArray(int a[], int b[], int c[], int lenA, int lenB, int &lenC) {

	int i = 0;
	int j = 0;
	int m = 0;
	lenC = 0;
	while(i < lenA && j < lenB){
		if(a[i] < b[j]){
			c[m] = a[i];
			i++;
			m++;
			lenC++;
		}else if(a[i] > b[j]){
			c[m] = b[j];
			j++;
			m++;
			lenC++;
		}else{
			c[m] = a[i];
			i++;
			j++;
			m++;
			lenC++;
		}
	}

	if(i == lenA && j < lenB){
		while(j < lenB){
			c[m] = b[j];
			j++;
			m++;
			lenC++;
		}
		
	}else if(j == lenB && i < lenA){
		while(i < lenA){
			c[m] = a[i];
			i++;
			m++;
			lenC++;
		}
	}
	return c;

}

int main(){

	int a[5] = {2,3,7,8,11};
	int b[6] = {3,9,10,12,88,89};
	int c[11];
	int len = 0;
	mergeArray(a, b, c, 5, 6, len);
	for(int i=0; i<len; i++){
		printf("%d\n", c[i]);
	}
}

8. 求数组的子数组之和的最大值

9. 求数组中最长递增子序列

10. 数组循环右移

把一个含有N个元素的数组,循环右移K位,要求时间复杂度为O(N),且只允许使用两个附加变量。

11. 数组分割

有一个无序,元素个数为2n的正整数数组,要求:如何能把这个数组分割成元素个数为n的两个数组,并使两个子数组的和最接近。