基础闯关记-快速排序
2017-06-27 10:22:56    648    0    0

快速排序

快速排序基本思想

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

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

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

image

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

实现快速排序

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

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

左右子集划分思路

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

image

左右子集划分代码

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

  1. #include<stdio.h>
  2. void partition(int arr[], int left, int right);
  3. void swap(int *a, int *b);
  5. v
基础闯关记-堆排序
2017-06-20 20:32:49    824    0    0

堆排序

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

什么是二叉堆

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

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

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

image

二叉堆存储

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

  1. struct Node{
  2.     int data;
  3.     int *left;
  4.     int *right;
  5. }

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

image

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

二叉堆的建立

二叉堆建立过程过程

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

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

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

image

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

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

image

注意

从CGI到FastCGI到PHP-FPM
2017-06-13 20:41:30    1594    1    1

从CGI到FastCGI到PHP-FPM

背景

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

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

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

早些年的简单服务器

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

image

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

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

  1. vagrant@kfz:~$ gcc hello_world.c

然后采用curl工具测试

  1. vagrant@kfz:~$ curl "127.0.0.1:8887"
  2. GET / HTTP/1.1
  3. User-Agent: curl/7.49.1
  4. Host: 127.0.0.1:8887
  5. Accept: */*
  7. Hello World

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

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

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

CGI协议与CGI程序

什么是CGI协议和CGI程序

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

服务器三种并发方式
2017-05-28 13:37:15    661    0    0

服务器三种并发方式

迭代服务器

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

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

  1. #include <stdio.h>
  2. #include <netinet/in.h>
  3. #include <sys/socket.h>
  4. #define MAXLEN 1024
  5. int main()
  6. {
  7.     int server_sockfd = socket(AF_INET,SOCK_STREAM, IPPROTO_TCP);
  9.     struct sockaddr_in server_sockaddr;
  10.     server_sockaddr.sin_family = AF_INET;
  11.     server_sockaddr.sin_port = htons(1024);
  12.     server_sockaddr.sin_addr.s_addr = htonl(INADDR_ANY);
  14.     bind(server_sockfd,(struct sockaddr *)&server_sockaddr,sizeof(server_sockaddr));
  16.     listen(server_sockfd, 20);
  18.     for( ; ; ){
  19.         int clnt_sock = accept(server_sockfd, NULL, NULL);
  20.         printf("add client\n");
  22.         char buf[1024] = {'\0'};
  23.         if(read(clnt_sock, buf, 1024) != 0){
  24.             printf("read end \n");
  25.             fputs(buf, stdout);
  26.             write(clnt_sock, buf, 1024);
  27.
C语言编写服务端入门
2017-05-24 01:27:18    1101    0    0

C语言编写服务端入门

前言

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

C/S结构流程图

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

image

服务端

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

socket函数

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

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

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

协议族可以有以下取值

family 说明
AF_INET IPv4协议
AF_INET6 IPv6协议
AF_LOCAL Unix域协议
AF_ROUTE 路由套接字
AF_KEY 密钥套接字

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

type 说明
SOCK_STREAM 字节流套接字
SOCK_DGRAM 数据报套接字
SOCK_SEQPACKET 有序分组套接字
SOCK_ROW 原始套接字

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

protocol 说明
IPPROTO_TCP TCP传输协议
IPPROTO_UDP UDP传输协议
IPPROTO_SCTP SCTP传输协议

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

MySQL事务和隔离级别
2017-05-16 19:20:11    571    0    0

MySQL事务和隔离级别

前言

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

  1. 1. select money from account where name=A;
  2. 2. update account set money = money - 200 where name = A;
  3. 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连接的建立和终止
2017-04-16 11:22:44    744    0    0

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确认，三次握手完成

image

四次挥手

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

image

使用tcpdump调试

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

Socket网络编程入门
2017-04-14 00:31:09    1633    0    0

Socket网络编程入门

引子

从我们熟悉的web应用为例子，先不讨论socket，我们看一下如果两台机器之间要通讯，需要经过哪些步骤。我们看一下服务器回给我们一个简单的"Hi"时，需要经过哪些步骤。

image

服务端：

  1. 服务器的应用层会产生一个Hi字符串
  2. 数据封装后交给传输层
  3. 传输层封装后交给网络层
  4. 网络层数据封装后交给数据链路层
  5. 物理层接收后变成0和1字节流传输到Internet网络中

客户端：

  1. 客户端物理层接收来自服务端的0和1字节流
  2. 数据链路层接收物理层数据并解读数据报
  3. 网络层接收物理层数据并解读数据报
  4. 传输层解读网络层数据并解读数据报
  5. 应用层接收到Hi字符

现实中的网络数据传输远远比这复杂得多，数据必须经过5层协议栈。试想如果让一个开发者从0开始实现这样的一个数据传输，难度可想而知。但是目前从事网络开发的人千千万万，他们是怎么做到的呢，这一切都要归功于Unix操作系统和Socket。因为有了Socket，网络编程变得快速而且简单了很多。

什么是socket

Socket就是操作系统(Unix)为应用进程提供的一个方便操作网络数据收发的api接口，只要你读懂了这一套api接口，就可以把数据从一个主机传输到另一个主机，或者从其他主机接受数据，而不需要知道还有五层协议的复杂性。这就好比我们开发者读取文件的时候，file系列函数就可以轻松的帮我们获取文件的内容，我们不需要知道磁盘的磁头如何转动，如何实现定位读数据等。
下面是操作系统提供的Socket层的位置

image

这个图的上层是应用程序层，比如我们的nginx，apache系列的软件，下层是操作系统层，比如Unix。Socket层位于应用层和传输层之间，上层应用如果想实现网络编程，只需要调用操作系统提供的Socket层提供的api即可。操作系统通过Socket大大简化了网络编程的复杂性，使得从事网络编程的开发人员更加便捷。

Socket相关函数一览

既然知道了Socket是操作系统为我们提供的一层网络编程接口封装，那就可以看一下操作系统给我们留了哪些接口，我们能用这些接口干什么

函数名称 用途 说明
socket 创建套接字
Hadoop+Hive环境搭建
2017-02-22 23:27:42    867    0    0

Hadoop+Hive环境搭建

JDK安装

由于国内城墙的原因，访问官网下载速度有点慢，这里csdn上下来资源。jdk安装包下载地址:

http://download.csdn.net/download/love254443233/9179483

下载下来上传到Linux服务器上，使用rz命令即可，如果没有这个命令，安装rz参照这篇文章

http://blog.csdn.net/kobejayandy/article/details/13291655

  1. 解压jdk-7u79-linux-x64.tar.gz
  1. [root@S140530 ~]# tar zxvf jdk-7u79-linux-x64.tar.gz
  1. 在/root/.bash_profile中添加如下配置
  1. export JAVA_HOME=/root/jdk1.7.0_79
  2. export PATH=$JAVA_HOME/bin:$PATH
  1. 使环境变量生效，执行以下命令
  1. [root@S140530 ~]# source ~/.bash_profile
  1. 安装验证，执行java命令
  1. [root@S140530 ~]# java -version
  2. java version "1.7.0_79"
  3. Java(TM) SE Runtime Environment (build 1.7.0_79-b15)
  4. Java HotSpot(TM) 64-Bit Server VM (build 24.79-b02, mixed mode)

Hadoop安装

下载解压

  1. 下载Hadoop2.7.1 
  1.  wget "http://mirrors.hust.edu.cn/apache/hadoop/common/hadoop-2.7.1/hadoop-2.7.1.tar.gz"
  1. 复制hadoop-2.7.1.tar.gz 到/usr/hadoop目录下
  1. [root@S140530 hadoop]# makedir /usr/hadoop
  2. [root@S140530 hadoop]# cp hadoop-2.7.1.tar.
MySQL索引
2016-11-18 00:30:00    245    0    0

什么是索引

要理解MySQL中索引是如何工作的，最简单的办法就是看一本书的“索引”部分，就像给你一本新华字典，然后要你找出“爵”字，具体做法是根据拼音找出j开头的部分，然后再进一步定位到“爵”的页码，从而找出“爵”。MySQL索引的工作原理也一样。

B-Tree索引

当谈论索引的时候，如果没有特别申明，那多半是指B-Tree索引。B-Tree树意味着所有的值都是按顺序存储的，并且每一个叶子页到根的距离相同。在innoDB存储引擎中，抽象可以用以下图表示B-Tree树索引

B-Tree树能够加快访问数据的速度，因为存储引擎不再需要全表扫描获取需要的数据，取而代之的是从数据的根节点开始进行搜索。根节点的槽中存放了指向子节点的指针，存储引擎根据这些指针继续往下寻找，通过比较节点页的值和要查找的值就可以找到合适的指针进入下层节点，最终找到对应的值或者没找到结果。

MySQL中索引例子

假设有一张表的定义如下：

  1. create table people(
  2.     last_name varchar(50) not null,
  3.     first_name varchar(50) not null,
  4.     dob date not null,
  5.     gender enum('m', 'f') not null,
  6.     key(last_name, first_name, dob)
  7. )

二级索引组织方式

则在B-Tree索引中，因为建立了一个last_name，first_name，dob的索引，注意key申明的索引为二级索引。数据的组织方式可以用以下图表示

特别注意的是，索引对多个值进行排序是按照create table定义语句中的定义索引的顺序来的，如果第一列一样，则排第二列，以此类推。按照这个数据组织方式，B-tree索引适合全键值，键值范围，键值前缀查找
以下查询都可以使用到索引
1. 查询一个姓名为Allen Cuba并且生日为1960-01-01的人
2. 查询所有姓Allen的人
3. 查询所有以A为开头自行姓名的人; last_name like ‘A%’
4. 查询姓Allen和Balnger之间的

3/4
Proudly powered by Leanote