测试Hadoop Trunk代码

从SVN上checkout代码，然后部署在了两台Linux机器之上。Hadoop版本为0.12.4。过程还是挺顺利的，这得益于以前折腾过Hadoop 0.5版。

如果你在安装的过程中，发现问题，可以参考用Hadoop搭建分布式存储和分布式运算集群。 当然你可以通过Email或者Gtalk与我联系。好久没有关注Hadoop了，发现它已经越来越成熟，开始步入实际使用阶段，比如Amazon 的 EC2 和S3。

另外，令人非常兴奋的是，Yahoo推出Pig。从介绍可知，这是一个非常有意思的项目，建立在Hadoop之上。

与搜索相关的研发工作

想从事与搜索相关的研发工作，需要哪些知识。带着这个疑问，我查看了包括Google，Baidu，Yahoo，腾讯，Sohu，Sina，阿里巴巴等公司的招聘信息。自我总结如下：

• 为什么要从事研发工作？

1. 在公司处于核心地位；
2. 把研究和开发紧密而完美的结合在一起；

• 研发职责是什么？

1. 负责搜索引擎系统的架构设计以及核心模块的系统设计；
2. 进行搜索引擎系统核心模块的编码和技术研发；
3. 重点技术难题的攻关；

• 想从事研发工作，需要什么？
  

1. 强烈责任心，开放的性格，良好的沟通能力；拥有极强的发现问题、分析问题、解决问题的能力；
2. Fluency in English(Reading and Writing)；
3. 对算法设计、数据结构有深刻的理解；
4. 精通Linux/Unix平台上的C/C++语言编程，熟练使用调试工具；熟悉网络、多线程编程技术（熟悉Unix系统调用io, socket, process, signal）；如果懂Java，将更好；
5. 能够使用一种脚本语言（perl，shell或者python)；
6. 具有搜索、信息检索相关领域开发经验者优先；
7. 至少熟悉一种数据库系统，你可以选择MySql作为自己重点攻克的对象。

• 想成为架构师，还需要什么？

1. 熟悉分布式系统架构设计，具备大流量、大访问量、高负载环境下的系统开发及优化经验；
2. 知识面广，思路开阔，对业界的最新技术发展动态有比较密切的关注；
3. 对软件开发生命周期比较熟悉，具备较强的文档编写能力及项目管理能力。

想从事研发工作的朋友可以对照上面的要求，找出自己的不足。对于你来说，那些不足就是最重要的。缺什么，什么就最重要。

Update:一些更加细化的指标，比如：

• 搜索引擎各子系统(Spider、Indexer、Searcher、分词、网页仓库)的设计和实现。
• 搜索引擎的性能优化分析和功能升级。

继续写博客，记录自己的成长

开博多处，不过全都停了下来。今天，重新开始，将在这里记录自己的每一天生活。

（1）嘻嘻哈哈才是我：http://zyxt.blogdriver.com（最早的地方，也是所呆时间最长的地方）。
（2）飞翔的章鱼：http://zyxt.blog.hexun.com/（目前内容已经全部删除！）。
（3）naivebaby：http://blog.csdn.net/naivebaby（技术blog）。
（4）我是一只小小鸟：现在这个（由于当初google blog被禁，于是放弃）。
（5）**blog：（暂且保密）。

btw：这里主要记录我在技术上的一些感悟，要了解我的生活，请访问链接中的"My Childlike Life"!

基本算法连载（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;
}