基本算法连载（14）－BST（Binary Search Tree）的笔记

插入实现（传指针地址的地址）：

void InsertNode(struct node **node_ptr, struct node *newNode) {
   struct node *node = *node_ptr;
   if (node == NULL)
       *node_ptr = newNode;
   else if (newNode->value <= node->value)
       InsertNode(&node->left, newNode);
   else
       InsertNode(&node->right, newNode);
}

删除节点：

void DeleteNode(struct node*& node) {
   struct node*& temp = node;
   if (node->left == NULL) {
       node = node->right;
       delete temp;
   } else if (node->right == NULL) {
       node = node->left;
       delete temp;
   } else {
       // Node has two children - get max of left subtree
       temp = node->left;
       while (temp->right != NULL) {
           temp = temp->right;
       }
       node->value = temp->value;
       DeleteNode(temp);
   }
}

基本算法连载（13）－递归程序转变成非递归

用堆栈实现递归其实并没有消除递归，只不过人工做了本来由编译器做的事情。真正的非递归是指运算时所需要的空间是常数，即所需空间与问题的输入规模无关。并非所有递归都可以转换成非递归，比如著名的Ackmann函数。
递归转非递归方法：
（1）用一般公式直接代替。象经常看到的斐波那契数列，它就存在通项公式，而无需采用递归实现。
（2）使用栈来实现
（3）通过Cooper变换、反演变换将一些递归转化为尾递归，从而迭代求出结果
至于什么是Cooper变换，反演变换，这可得好好研究数学。这里贴两个变换实例。

计算阶乘的递归实现（用Haskell实现的，谁都看得懂）：f x ＝ if x = 0 then 1 else f(x-1)*x;
第一步：转变成尾递归

int G(int x, int y)
{
 int x1, y1;

 if (x == 1) {
   return 1 * y;
 } else {   
   x1 = x - 1;
   y1 = x *y;
   return G(x1, y1);
 }
}

int f(int x)
{
 return G(x, 1);
}

第二步：转变成迭代

int G(int x, int y)
{
 int x1, y1;

loop:
 if (x == 1) {
   return 1 * y;
 } else {
   x1 = x - 1;
   y1 = x *y; 
   x = x1
   y = y1;   
   goto loop;
 }
}

求斐波那契值：
f x |x==0 =0
   |x==1 =1
   |otherwise = f (x-1)+f (x-2)

第一步：转变成尾递归
int fib(int n){
   if(n==0)
      return 0;
   return _fib(n,1,0);
}

int _fib(int n,int f1,int f2){
   if(n==1)
      return f1;
   return _fib(n-1,f1+f2,f1);
}

第二步：转变成迭代（略）

基本算法连载（12）－顺序查找的两个实现

顺序表的实现，天下人都知道，最最简单的一种，不过我还是贴出两个实现，大家看看：

int search(int a[],int key,int length){
int i;
for(i=length-1;i>=0;i--){
if(a[i]==key)
 return i;
}
return -1;
}

/*
* 实际数组元素是从1号位置起开始存储，0号位置存储key
*/
int search(int a[],int key,int length){
int i;
a[0] = key;
for(i=length;!(a[i]==key);i--);
return i;
}

由此，想到了字符串的拷贝实现：

for(i=0;0!=(dst[i]=src[i]);i++);

基本算法连载（11）－两个基本概念：in-place和tail-end recursion

平时看算法，经常碰到in-place algorithm和tail-end recursion两个概念。今天终于了解了这两个概念。
In-place算法：The input is usually overwritten by the output as the algorithm executes.函数语言是不鼓励或支持in-place算法的，它把overwriiten当作side effect。函数语言，听过不少，没有学过，有时间得学学。
代码：

int sum(int n){
int i;
int sum = 0;
for(i=1;i<=n;i++){
sum = sum+i;
}
return sum;
}

此处的sum就被overwritten，可以算作in-place算法。

Tail-end recursion(tail recursion)：函数所做的最后一件事情是一个函数调用，被称作尾部调用（tail－call）。使用尾部调用的递归程序称为尾部递归。tail-recursion是很容易转变成iteration的。在把尾部递归程序转变成非递归程序时，我们就有了理论保证。尾部调用是可以进行优化的：在尾部进行函数调用时使用一个栈结构覆盖当前的栈结构，同时保持原来的返回地址。
以下的代码展示的是一个更一般化的tail recursion，它先转变成熟悉的tail recursion，然后转变成iteration。看惯了Java代码，看这个还有点不习惯。
代码：

#include <stdlib.h>
typedef struct list{
 int value;
 struct list* next;
}list;

//----------------------------------
//一般化的tail-recursion
list* f(list* input){
 list* head;
 if(input == NULL){
  head = NULL;
 }else{
  head = (list*)malloc(sizeof(list));
  head->value = input->value;
  head->next = f(input->next);
 }
 return head;
}

//------------------------------------
//熟悉的tail-recursion
void fprime(list* input,list** p){
 if(input == NULL){
  *p = NULL;
 }else{
  *p = malloc(sizeof(list));
  (*p)->value = input->value;
  fprime(input->next,&(*p)->next);
 }
}

list* f1(list* input){
 list* head;
 fprime(input,&head);
 return head;
}

//------------------------------------
//iteration
list* f2(list*input){
 list* head;
 list** p;
 p = &head;
 while(input != NULL){
  *p = (list*)malloc(sizeof(list));
  (*p)->value = input->value;
  input = input->next;
  p = &(*p)->next;
 }
 *p = NULL;
 return head;
}
 
  

基本算法连载（10）－模式匹配之BM(Boyer-Moore)

周末两天被BM算法折磨的要死。《a fast string search algorithm》论文中提到的算法思想倒是理解的差不多，但网上（http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140）给出的实现可就是看不懂。通过Baidu，Google一搜，可以看到很多Boyer-Moore的实现。但绝大部分实现都是简化版本，只考虑了bad-character shift，而忽略了good-suffix shift。
它思想的源泉是从右向左匹配字符串将获得更多有用的信息。The algorithm precomputes two tables to process the information it obtains in each failed verification: one table calculates how many positions ahead to start the next search based on the identity of the character that caused the match attempt to fail;the other makes a similar calculation based on how many characters were matched successfully before the match attempt failed.其中前一个称作bad-character shift，后一个称作good-suffix shift。想详细了解Boyer-Moore的思想，我极力推荐看作者发表的论文，它比网上对这个算法介绍的文章容易理解的多。
处理主串为n，模式串为m的情况，此算法的最好表现是：n/m。在这种情况下，只有模式串中的最后一个字符需要比较。不相等，马上可以跳过m个字符。从这里可以看出此算法一个违反直觉的性质：模式串越长，搜索越快。
最优的代码实现（没看懂，明天贴个我自己改的）：

void preBmBc(char *x, int m, int bmBc[]) {
 int i;

 for (i = 0; i < ASIZE; ++i)
    bmBc[i] = m;
 for (i = 0; i < m - 1; ++i)
    bmBc[x[i]] = m - i - 1;
}


void suffixes(char *x, int m, int *suff) {
 int f, g, i;

 suff[m - 1] = m;
 g = m - 1;
 for (i = m - 2; i >= 0; --i) {
    if (i > g && suff[i + m - 1 - f] < i - g)
       suff[i] = suff[i + m - 1 - f];
    else {
       if (i < g)
          g = i;
       f = i;
       while (g >= 0 && x[g] == x[g + m - 1 - f])
          --g;
       suff[i] = f - g;
    }
 }
}

void preBmGs(char *x, int m, int bmGs[]) {
 int i, j, suff[XSIZE];

 suffixes(x, m, suff);

 for (i = 0; i < m; ++i)
    bmGs[i] = m;
 j = 0;
 for (i = m - 1; i >= -1; --i)
    if (i == -1 || suff[i] == i + 1)
       for (; j < m - 1 - i; ++j)
          if (bmGs[j] == m)
             bmGs[j] = m - 1 - i;
 for (i = 0; i <= m - 2; ++i)
    bmGs[m - 1 - suff[i]] = m - 1 - i;
}


void BM(char *x, int m, char *y, int n) {
 int i, j, bmGs[XSIZE], bmBc[ASIZE];

 /* Preprocessing */
 preBmGs(x, m, bmGs);
 preBmBc(x, m, bmBc);

 /* Searching */
 j = 0;
 while (j <= n - m) {
    for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
    if (i < 0) {
       OUTPUT(j);
       j += bmGs[0];
    }
    else
       j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
 }
}

基本算法连载（9）－模式匹配之KMP(Knuth-Pratt-Morris)

KMP算法，在《数据结构》课上听过，似是非懂，读完大学后全忘光了。Brute-Force算法，简单，谁都知道。从主串S的第pos个字符起与模式串进行比较，匹配不成功时，从主串S的第pos+1个字符重新与模式串进行比较。如果主串S的长度是n，模式串长度是m，那么Brute-Force的时间复杂度是o(m*n)。最坏情况出现在模式串的子串频繁出现在主串S中。虽然它的时间复杂度为o(m*n)，但在一般情况下匹配时间为o(m+n)，因此在实际中它被大量使用。
前几日，重新拾起了KMP算法，然后向MM讲解之。KMP的主要思想是：每当一趟匹配过程中出现字符比较不等时，不需回溯主串S的指针，而是利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的一段距离后，继续进行比较。
模式串到底向右滑动多少，在KMP算法中是用一个数组来存储的。针对模式串中的每个索引j，都将有一个对应的值。此值的含义为模式串中位置从0到j-1构成的串中所出现的首尾相同的子串的最大长度加1。
下面给出具体实现：

/*
* n is the length of text,while m is the length of pattern.
* And pos which is zero-indexed is the start point of search.
*/
int kmp(char* text,int n,char *pattern,int m,int pos){
 int i,j;
 //Generate the array of next
 int* next = (int*)malloc(m*sizeof(int));
 i = 0;
 j = -1;
 next[i] = j;
 while(i<m){
   if((j==-1) || (pattern[i]==pattern[j])){
     i++;
     j++;
     if(pattern[i]!=pattern[j])
      next[i] = j;
     else
      next[i] = next[j];
   }else{
     j = next[j];
   }
 }

 int k = 0;
 for(k=0;k<m;k++)
   printf("next:%d\n",next[k]);

 //Search
 i = pos;
 j = 0;
 while(i<n&&j<m){
   if((j==-1) || (text[i]==pattern[j])){
     i++;
     j++;
   }else{
     j = next[j];
   }
 }
 if(j==m)
    return i-m;
 else
    return 0;
}

KMP算法的时间开销包括两部分，一个是求next数组元素的值，此时的时间开销是o(m)；一个是搜索，此时的时间开销是o(n)。因此，它的时间复杂度是o(m+n)

看《The Google File System》后的一些笔记

看了基于Google File System思想实现的Hadoop代码，重读了Google的这篇论文《The Google File System》。Paper挺长，网上已经有热心的人把翻译版奉献了出来。在这里，只是把其中的部分内容抽取出来，与大家一起分享。
性能，可扩展性，可靠性，可用性仍然是GFS的目标，但它还有一些与传统分布式文件系统与众不同的东西：
（1）对于大规模的集群系统，机器出现故障很正常，因此系统容错必须十分重视。文件系统必须具有高可用性，数据完整性和相应的诊断工具。通过快速恢复，chunk复制，master复制达到高可用性；通过checksum检查数据完整性；通过log记录系统中出现的各种事件，以便诊断错误。
（2）传统文件系统的block的大小只有几k，而GFS将选用64M，以满足当前出现的越来越庞大的数据集处理需求。选用大的chunk size，可以：
a、减少与master的交互次数；
b、大部分的时候，对chunk的操作都集中在一个chunk上，因此可以维护一个持久的TCP连接减小网络开销；
c、减少存储在master上的元数据把它放在内存中。
在具有优点的同时，存在缺点，就是多个客户端同时访问同一个文件（此文件比较小，由一个chunk组成），易形成hot spot。
（3）通过观察发现，绝大部分的时候，对文件的修改操作都只是附加内容，很少是翻盖写或者随机写。因此在GFS中，对文件附加操作进行重点优化。

GFS的体系结构
GFS的体系结构是由一个master和多个chunkserver组成（在Hadoop中，master称作name node，chunkserver称作data node，chunk称作block）。
采用单一的master，可以简化系统设计，在拥有全局视图的情况下制定更好的chunk处置策略。采用此种方法，存在瓶颈问题是显而易见的。因此master只存储元信息，相当于元数据服务器，具体的数据传输由client和chunkserver来完成。

元数据
包括三类元数据，它们分别是：文件和chunk的命名空间，文件到chunk的映射和每个chunk副本的位置。元数据全部放入内存，这样可以加快master的操作速度，但它受限于内存大小。

操作日志
对文件系统的操作都将被记录到持久化存储介质，通过重新执行这些操作来达到恢复文件系统的目的。当操作日志达到一定大小时，将做checkpoint，这样可以减少文件系统的恢复时间。目前，Hadoop不支持对操作日志做checkpoint。

Data Flow
在GFS中，数据流和控制流分开，这是显而易见的。数据流怎么流动，具有一定的技巧性。它采用的是pipeline方式。一个chunkserver并不是把数据同时分发给其余的chunkserver，而是把数据只传给离自己最近的chunkserver（距离的远近通过IP地址来判断）。此时这个chunkserver在接受数据的同时，把数据转发给离它最近的chunkserver，这样充分利用了全双工网络的带宽。

以上只谈到paper中涉及的一些方面，完整内容请阅读paper。