最大子数组问题求解

问题描述

问题：输入一个整型数组，数据元素有正数也有负数，求元素组合成连续子数组之和最大的子数组。

描述：输入的数组为1, -2, 3, 10, -4, 7, 2, -5，最大和的连续子数组为3, 10, -4, 7, 2，其最大和为18。

暴力求解法

第一种解法最简单，最暴力，最容易理解的一种方法。这种解法的思想就是，从第一个元素开始，然后和后面的所有元素组合开有没有可能形成最大值。代码很简单

#include<stdio.h>
#define MAX_LEN 8
int main(){
    int arr[MAX_LEN] = {1, -2, 3, 10, -4, 7, 2, -5};
    int i,j;
    int sum = 0;
    for(i=0; i < MAX_LEN; i++){
        int _tmpSum = arr[i]; 
        for(j=i+1; j < MAX_LEN; j++){
            _tmpSum += arr[j];
            if(_tmpSum > sum){
                sum = _tmpSum;  
            }           
        }       
    }   
    printf("%d", sum);
}

这种算法的时间复杂度为O(n^2)。所以这种方法虽然简单，单一般不采用。

分治求解法

计算机领域经常使用的一种求解思想，分而治之。想想二分查找，一半一半得淘汰，这样效率会提高很多。我们同样也可以用这种思路求解最大子数组问题。假定我们要寻找数组A[low .. high]的最大子数组，使用分治技术我们将A划分为两个等规模子数组。首先找到数组A的中央位置，比如mid，然后分解成两个子数组A[low .. mid]和A[mid+1 .. high]。这样如果存在一个最大的子元素系列A[i .. j]那么它一定满足下面三种情况之一

1. 完全位于子数组A[low .. mid]中，此时low<=i<=j<=mid
2. 完全位于子数组A[mid+1

PHP7中Protobuf的安装使用

写这篇文章的缘由是最近在关注RPC框架序列化的一些原理。但是在安装Protobuf的时候，发现网上的教程都太老了，加上目前Protobuf官方已经支持PHP了，不再需要使用第三方插件了。

关于序列化和反序列化

在PRC框架中，数据的传输发生在客户端和服务端，而我们知道基于TCP协议最终传输的是二进制的0/1序列。所以，基于TCP传输协议的RPC服务自然也需要将数据结构转换成二进制，和二进制转换成数据结构的功能。所以，原则上，基于网络的数据传输只能传输二进制表示的字符串

序列化：将数据结构或对象转换成二进制串的过程
反序列化：将在序列化过程中所生成的二进制串转换成数据结构或者对象的过程

但是，传输的二进制序列是完全没有意义的，除非有一套解析二进制串的协议。没错，这个协议可以就是目前我们大家熟知的xml，json协议。当然。除了这两者，还有其他的的序列化和反序列化协议。

几种常见的序列化和反序列协议

XML

XML是一种常用的序列化和反序列化协议，具有跨机器，跨语言等优点。XML历史悠久，其1.0版本早在1998年就形成标准，并被广泛使用至今。XML的格式如下

<note>
    <to>George</to>
    <from>John</from>
    <msg>Don't forget the meeting!</msg>
</note>

可以看出这种序列化协议的优点是可读性和易调试行。但是这种协议的缺点也很明显：额外空间开销大，序列化之后的数据量剧增。

JSON

JSON是一种轻量级的数据交换格式。采用完全独立于编程语言的文本格式来存储和表示数据。如果你跟浏览器Web应用打交道的话，那么JSON一定是应用最广泛的，它的数据格式如下

{
    "to":"George",
    "from":"John",
    "msg":"Don't forget the meeting!"
}

这种序列化协议有很大的优势：
1. 这样表示非常符合工程师对对象的理解，尤其是js工程师
2. 和xml一样，可读性强
3. 和xml相比，更加节省空间，解析速度更快

DNS原理浅析

DNS是什么

DNS（Domain Name System，域名系统）是整个互联网的核心组件，负责域名到IP地址的转换工作。比如说，你要访问www.baidu.com就得先通过DNS服务将www.baidu.com翻译成IP地址115.239.211.112。有的人可能会想，这个不是很简单吗，写一个TXT文本文件保持映射关系不就可以了吗。没错，早期的DNS就是这样的。

DNS的历史

在20世纪70年代，当时的计算机网络只有几百台主机。他们确实是采用一个名为HOSTS.TXT的文件容纳所有的主机信息，这个文件包含了主机名字——地址的映射关系（你可以想象Linux的/etc/hosts）。这样维持了一段时间后，随着网络规模的爆发，暴露了以下问题

1. 流量和负载的爆发增长，一台主机根本扛不住
2. 名字冲突问题，当时注册名字是比较随意的
3. 一致性问题，当时变更是通过邮件形式通知的，然后变更配置中心

毫无疑问，HOSTS.TXT方案最终以失败告终。但是当时的人继续探索，他们希望创造出一个系统，以解决单一主机表系统本身所固有的问题。所以今天我们看到了及其复杂的DNS系统

DNS设计

被上述HOSTS.TXT文件坑惨了之后，DNS被设计成了一个分布式数据库，它允许整个数据库的各个部分进行本地控制。同时，整个网络也能通过客户-服务器的方式访问每个部分的数据。首先为了解决名字冲突，名字被设计成了树状结构，所以我们现在的域名看起来是非常规范的。

域名空间

DNS分布式数据库是以域名为索引的，每个域名实际上就是一棵很大的逆向树中的路径。这棵逆向树就称为域名空间。这棵树的结构如下：

域名空间：这整个树就构成了域名空间，当然，现实生活中可能还有子树

域名：树中的一个节点到根节点对的顺序连接表示域名。并且用“.”分割路径上出现的名字。比如map节点对应的域名为map.baidu.com
（我们忽略了路上的根的名字）

域：一个域就是这个域名空间（整棵树）中的一个子树。域的名字就是子树根节点到树根的域名。图中的灰色圆框就是baidu.com域。百度掌管着这个域

这样设计一个很大的好处就是域名分散管理，像ba

快速排序

快速排序基本思想

快速排序的基本思想就是分治法，就是将一个大的数组按照某一中间值分成两个子集，一组是每个元素都大于中间值，另一组是每个元素都小于中间值，然后递归调用该过程，最后可完成排序。步骤：

1、先从数列中取出一个数作为基准数，可以是第一个元素或最后一个元素。
2、分两个子集，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3、再对左右子集间重复第二步，直到各子集只有一个数，排序结束

整个过程可以用下图的竹竿按从低到高的顺序排序，首先我们找出第一根杆子为标准，剩下的高杆移到右边，低杆移到左边（不用管两遍的顺序，只要符合低左高右即可）。然后针对左边再次进行同样的动作，最后就可以保证左边是从低到高排列的，再针对右边也进行同样的动作（图中没有画），最终所有的竹竿都是有序的。

这个图可以看出，只要不断递归左右两个子集，最终递归结果就是整个数组有序。所以快速排序的核心是找到一个快速的左右子集划分方法，以及找到一个合适的基准元素，这两个因素影响了你写的快速排序到底快不快。

实现快速排序

前面说到，找到划分方法和基准元素，快速排序基本上就实现了。

如果要实现以某一个元素为基准，将数组划分成左右两个子集。方法其实有很多种，有的可能时间复杂度高，有的可能耗费空间多。

左右子集划分思路

《啊哈，算法》里介绍的一种方法，这种方法的效率比较高。这种方法就是假设有两个探针，分别是左探针和右探针。一开始分别指向数组的首地址和末地址。然后右探针开始向中间靠拢，直到发现一个小于基准值的元素，然后左探针也向中间靠拢，直到发现一个大于基准值的元素，这是交换两个探针的数组，直到两个探针相遇结束。整个过程可以用下图表示，仔细观察下基准元素4是如何插入到中间的

左右子集划分代码

对照上图，很容易就可以写出相应的算法，实现上面过程的函数是partition函数，需要注意的是，看上面的图，最终和基准元素交换的是i和j相遇的地方。

#include<stdio.h>
void partition(int arr[], int left, int right);
void swap(int *a, int *b);
v

堆排序

堆排序，毫无以为，是在堆的数据结构上进行排序，注意，我们这里谈论的堆是二叉堆。所以首先了解二叉堆，然后在二叉堆的基础上排序是很容易的一件事情。

什么是二叉堆

二叉堆的结构就是完全二叉树或者近似完全二叉树。在二叉树的结构上保持一定的有序性就是二叉堆，根据这种有序性的不同，分为最大堆和最小堆

最大堆：任一节点的关键字是其子树所有节点的最大值
最小堆：任一节点的关键字是其子树所有节点的最小值

举一个例子，下面这两个都是最大堆

二叉堆存储

我们知道，二叉树的存储结构最适合的还是每个节点都是一个具有左右孩子和自身数据的结构体

struct Node{
    int data;
    int *left;
    int *right;
}

但是，完全二叉树不需要这样表示，完全二叉树可以直接用数组表示，这样更节省空间。在一个完全二叉树中，只要知道一个节点的数组下标（i），就能知道它的父节点（i/2），左孩子（2*i+1）,右孩子（2*i+2），比如下图中,字母表示二叉堆中节点数值，底下一条内存条表示二叉堆的实际存储情况。

二叉堆的存储形式即如上图所示，只不过和满二叉树不同的地方在于，二叉堆的数字是保持一定的大小关系。

二叉堆的建立

二叉堆建立过程过程

因为最大堆和最小堆的原理是一样的，我们举最大堆的例子。建立二叉堆我们使用的方法是先建立一个满二叉树，在满二叉树的基础上我们不断的调整节点，保证根节点大于其他子节点即可，最后就可以形成一个二叉堆。
建立一个满二叉树很简单，申明一个数字即可

int arr[] = {19, 20, 40, 56, 3, 9, 50};

这时候形成的二叉树如图所示

注意，这个时候的二叉树还不能形成一个二叉堆，因为我们发现最大的数字56不在根节点中。

剩下很关键的步骤，就是不断的调整节点，做法是：首先调整最右边的子树，即只看40,9,50三个元素，根节点40与它的左右孩子9,50对比找出其中的较大者，发现是50，所以50跟40位置互换，这样最右子树就满足二叉堆的条件了。然后这个过程左子树也递归进行，最后就会形成二叉堆。整个递归过程可以用下面的图表示

注意

从CGI到FastCGI到PHP-FPM

背景

笔者在学习这几个名词的时候，也是被百度到的相关文章迷惑。涉及到的主要名词包括

1. CGI协议
2. CGI脚本
3. PHP-CGI
4. FastCGI协议
5. PHP-FPM

要真正理解这些名词，如果我们硬生生的解释，也很难记住。我们可以从web服务器开发的历程来看，看看他们为什么会出现，以及他们解决了什么问题。

早些年的简单服务器

早些年的服务器很简单，你访问一个网站，比如www.helloworld.com，网站只返回你一个静态HTML页面。为了简单起见，我们假设网站值返回hello标题，这样流程可以用下图表示

这时候server是采用C语言编写的，为了说明问题，最简化一个服务器脚本。基本上一个简的C脚本就可以了，把这个服务器脚本命名为hello_server.c，代码可以到github上下载

在Linux环境中使用gcc编译hello_server.c

vagrant@kfz:~$ gcc hello_world.c

然后采用curl工具测试

vagrant@kfz:~$ curl "127.0.0.1:8887"
GET / HTTP/1.1
User-Agent: curl/7.49.1
Host: 127.0.0.1:8887
Accept: */*
Hello World

这里我们的重点不在HTTP响应的格式上，所以我们直接输出了Hello World，如果是请求静态页面，我们也是一样的思路，读取静态文件的内容然后返还给客户端。

思考：当Web时代越来越火爆，我们希望Web服务器有更多的功能，比如写博客，聊天，等等。同时，越来越多的不同领域的开发者想在web时代大显身手。很多服务器开发者发现有了以下缺点

#服务器功能方面
  Web服务器功能会随着这种逻辑的增长而增长，服务器会变的不专一
#语言支持方便
  越来越多的PHP，Python开发者想开发服务端程序，编写更多的功能，发现自己的语言无从下手

CGI协议与CGI程序

什么是CGI协议和CGI程序

既然Web服务器想做的专一，但又要支持Web的飞速发展，同时还想让其他语言开发者也

服务器三种并发方式

迭代服务器

在学习TCP/IP协议中，如果不考虑并发，我们所写出来的服务器往往叫做迭代服务器。迭代服务器会依次处理客户端的连接，只要当前连接的任务没有完成，服务器的进程就会一直被占用，直到任务完成后，服务器关闭这个socket，释放连接

看一个迭代服务器的例子，服务器的功能是接收客户端的输入，服务器接受之后原样返回客户端，即回射服务器。迭代服务器C源码

#include <stdio.h>
#include <netinet/in.h>
#include <sys/socket.h>
#define MAXLEN 1024
int main()
{
    int server_sockfd = socket(AF_INET,SOCK_STREAM, IPPROTO_TCP);
    struct sockaddr_in server_sockaddr;
    server_sockaddr.sin_family = AF_INET;
    server_sockaddr.sin_port = htons(1024);
    server_sockaddr.sin_addr.s_addr = htonl(INADDR_ANY);
    bind(server_sockfd,(struct sockaddr *)&server_sockaddr,sizeof(server_sockaddr));
    listen(server_sockfd, 20);
    for( ; ; ){
        int clnt_sock = accept(server_sockfd, NULL, NULL);
        printf("add client\n");
        char buf[1024] = {'\0'};
        if(read(clnt_sock, buf, 1024) != 0){
            printf("read end \n");
            fputs(buf, stdout);
            write(clnt_sock, buf, 1024);
       

C语言编写服务端入门

前言

本文使用C语言编写一个服务器，旨在更好的理解服务端/客户端程序，迭代服务器，并发服务器。这篇文章的例子很简单，就是当客户端连接上服务端之后，服务端给出一个“Hello World”回应。

C/S结构流程图

整个客户端，服务端交互流程可以用下图表示，服务端是优先启动进程并监听某一个端口，并且进程一直阻塞，直到有客户端连接进来，才开始处理客户端连接。

服务端

通过流程图可以看出，服务端涉及的Socket函数有socket, bind, listen, accept, read, write, close。使用这7个函数就可以编写出一个简易服务器。

socket函数

为了执行网络I/O，一个进程必须做的第一件事情就是创建一个socket函数，函数原型

# family 表示协议族
# type 表示套接字类型
# protocol 表示传输协议
# 若成功返回非负描述符，若出错返回-1
int socket(int family, int type, int protocol);

这个函数需要传入协议族，套接字类型，传输层协议三个参数。

协议族可以有以下取值

套接字类型可以有以下取值

传输层协议可以有以下取值

这里我们选择IPv4协议，使用字节流套接字，传输层选择TCP协议，所以第一段代码：

MySQL事务和隔离级别

前言

想象一个转账的场景，A要向B转账200元，首先会检查A的账户够不够200元，然后执行A的账户减去200元，最后执行B的账户增加200元。这几条语句可以表示成

1. select money from account where name=A;
2. update account set money = money - 200 where name = A;
3. update account set money = money + 200 where name = B; 

可以想象一下，如果前2条语句执行成功，第3条语句执行失败，那么这200元就“不翼而飞”。这个时候我们需要引入事务的概念，这三天语句要么都执行成功，只要有一条语句执行失败，则全部回滚。这样才能保证A的钱财不会白白丢失

事务的ACID

事务必须满足ACID特性，这四个特性分别是原子性，一致性，隔离性和持久性

原子性

一个事务必须被视为不可分割的最小工作单元，整个事务中所有操作要么全部提交成功，要么全部失败回滚。对于一个事务来说，不可能只执行其中的一部分，这就是事务的原子性

一致性

事务总是从一个一致性的状态，转移到另一个一致性的状态。在前面的例子中，即使在执行第3条语句的时候系统奔溃了，A也不会白白损失200元，因为事务最终没有提交。所以事务中所做的修改也不会保存到数据库中。

隔离性

通常来说，一个事务所做的修改在最终提交以前，对其他事务是不可见的。针对上面的例子，试想一下，假如A只有500元，如果SQL执行到第2句，A账户减去了200元。但是，这个时候，另一个进程也需要A转账500元，这个时候就需要考虑这个进程看到的是300元还是500元的问题。这一点比较复杂，会引入隔离级别的概念

持久性

一旦事务提交，则其所做的修改会永久保存到数据库中。此时即使系统奔溃，修改的数据也不会丢失。这一点也比较复杂，会引入持久化的真正含义

隔离级别

在MySQL的事务特性中，隔离一直是比较复杂而且难以理解的话题。MySQL一共给我们提供了4中不同的隔离级别。每一种隔离级别都规定了一个事务中所做的修改，哪些在事务内和

TCP连接的建立和终止

本文将阐述两个主机之间通过TCP协议通信的话需要哪些步骤，以及在建立连接的过程中经历哪些状态。并使用tcpdump工具帮助我们调试TCP应用，使我们掌握TCP如何建立和终止

TCP和UDP

首先的必须说一下TCP和UDP两种传输层协议；UDP是一种不可靠的传输协议，使用UDP协议时候，一个主机直接把一个数据报扔给另一个主机，而不考虑任何丢失的因数；所以UDP协议效率高不可靠。相反，TCP协议被定义为一种可靠传输协议，必须保证数据报一定要传输到对方（如果有意外，也会给出原因），要实现这种保证，就需要三次握手连接，传输数据确认，四次挥手告别，所以TCP协议是一种复杂，可靠的传输协议。

三次握手

当使用TCP协议传输数据时，为了保证数据的可靠传输，必须先建立连接，当建立一个TCP连接时，会发生以下情形
1. 客户端首先发送一个SYN分节，告诉服务器客户端将在连接中发送数据的初始序列号。
2. 服务器接收到客户端的SYN分节，必须发送一个确认(ACK)，同时自己也得发送一个SYN分节，他告诉客户端服务器将在同一连接中发送数据的初始分节序列
3. 客户端收到服务器的SYN之后，发送一个ACK确认，三次握手完成

四次挥手

当两台主机使用TCP协议传输数据时，任何一方都不能擅自断开连接，否则后果很严重。比如数据接收方擅自断开连接之后，结果数据发送方还有数据需要发送，这样就会导致数据收发的不一致。所以，建立一个TCP协议需要三次握手，同样，断开一个TCP连接需要四次挥手
1. 某个应用进程首先调用close，则该端为主动关闭，该端的TCP发送一个FIN分节，表示数据发送完毕
2. 接收到这个FIN的对端称为被动关闭，这个传递过来的FIN由TCP确认，即发送一个ACK。它的接收也作为一个文件结束符传递给接收端应用进程。
3. 一段时间后，接收这个文件结束符的进程将调用close关闭它的套接字，这导致它的TCP也发送一个FIN
4.主动关闭的一段接收这个FIN并发送一个ACK确认

使用tcpdump调试

使用tcpdump命令可以查看指定网卡的数据分组交换情况，这里直接使用nginx实现的服务器，然后客户