芭比，我要学算法法（第一篇）

前几天，看了一篇文章，文中大力抨击了当前去找工作，尤其是算法工程师工作，的无知少年对算法的理解和掌握。本人汗颜。曾多次因为算法被各种公司挡在门外。决定卧薪尝胆，前后杀出条血路，为工作找回些活口。

废话不多说。想把这个过程写成系列，过程就依照百度百科对算法两个字的说明吧。过程会参考手头上的两本书《算法导论》《算法设计与实现》，前边这本看过一次了，感觉一看就懂，但是记不住啥玩意。跟别人说算法思想一套一套的，但是人让你用形式语言描述一下，就傻眼了吧。甚至于编码实现，更不知所以了。那篇文章中，把这个状态叫做“为伊消得人憔悴”

那就开始吧。

最简单的算法，当属查找，查找里头最简单的是挨个找，专业一点叫枚举、顺序查找

int find(int array[], int length, int value)
{
     int index = 0;
     //Add code to search
     return index;
}

中间那些实现代码怎么实现呢？这个问题就是算法了。当然这里比较简单。
1. 验证参数
2. 循环实现遍历

int find(int array[], int length, int value)
{
    if((array == NULL) || (length == 0))
        return FALSE;
    int index = 0;
    for(; index < length; index++)
    {
         if(value == array[index])
               return value;
     }
     return FALSE;
}

验证一下

static void test()
{
    int array[10] = {1, 2};
    assert(0 == find(array, 10, 1));
    assert(FALSE == find(array, 10, 10));
}

顺序查找就这么简单实现了。实际上，我们实现算法的过程是简单和常规的，问题在于：
1. 能否优化算法工程过程。
2. 能否优化算法处理过程。
3. 能否优化代码结构。
4. 能否测量算法功耗。
。。。（其他可能出现的问题，在今后相对复杂的问题中再提出）

现在就当前这个顺序查找分析一下。
时间复杂度O(n),空间复杂度O(n)，理论上已经够好了。对于内存空间够用的情况下，使用数组比使用指针的风险要低，功耗少，典型的空间换时间。刚才提到用指针了吧，那还给出代码吧。

int find(int array[], int length, int value)
{
    if(NULL == array || 0 == length)
        return FALSE;

    int* start = array;
    int* end = array + length;
    while(start < end){
        if(value == *start)
            return ((int)start - (int)array)/(sizeof(int));
        start ++;
    }
    start=end=NULL;
    return FALSE;
}

说明两点：
1. 虽然我不喜欢用数组，但是“买的房子总比租的要踏实一点”我想你懂。
2. 你可以用数组的思想去建模，但是最好用指针来实现，因为“房子不总是那么够用”。现在的问题就是如何把算法升级过来呢？
一般我是这么做的：1）找到最核心的部分代码；2）把for循环的起止条件换成指针的移动范围；3）使用指针自加代替索引变量的自加；4）最后不要忘记给指针一个合适的归宿。不然那些都是炸弹。

上边的代码已经可以交卷了，至于进一步的优化，就是语言特性的范畴了，我不太喜欢做这些小动作。但是如果你有实时性要求的时候，不得不做这些。我也会先给你一些指引。
1. 减少变量赋值，尤其是不同类型之间的；
2. 减少高级的循环指令，比如while就比for好很多；
3. 减少循环内部的指令数量和指令容量；
4. 能算的尽量提前算出来，位运算优于加减，加减优于乘，剩余 不用。
5. 不用系统库调用；
当然你还可以去谷歌一下其他的优化方案。但是有点跟算法这个话题远一点了，我就不赘述了。


最后总结一番：
1. 要开始学算法了，没有算法，没人要啊。年薪60+帝都户口。。。
2. 需要有些重要的过度，比如从知识到代码，从代码到实现，从实现到测试，从测试到优化这些过程，过程很重要！
3. 需要有一些坚持，今天简单，明天简单，后天就回不简单！