学步园

写这个东西源自于公司组织的一次编程道场，最后的总结就是，尽量使用既有的库，将问题转化为既有库算法能解决的问题，可读性第一，效率第二。老大们说的话总是让人觉得醍醐灌顶，不要自己实现一个功能为了去榨取那么一点点性能，最终还不一定能榨出来！不知道有没有什么特别的原因，最后几位老大展示出的代码竟然一模一样，虽然语言不同，那就像直接的翻译一般，难道编程有其道，而老大们均掌握了“道”？
       我也想出了那种“标准的做法”，只是我根本不会用什么库，也根本不了解库，虽然有了伪代码，然而在将其转化为C代码的时候，遇到了无法突破的障碍，因为我根本不知道map或者vector之类的，更别提STL了，我除了知道点C++的一点语法之外，其它的什么都不知道…有时候，我认为我根本不是一个程序员，而是一个网管。
       我没有什么技巧可炫，也没有库使用的知识可以利用，只好从零开始用标准C来实现了，虽然效率不一定很高，可读性方面也可能只有我自己能看懂，然而不管怎么说，实现了，而且所有的时间复杂度是可控的，因为整个代码没有掉进任何的库实现的算法黑洞，比如如果你不知道你所使用的sort是怎么实现的，那么它的时间复杂度就是不可控的。
       问题是这样的：按照下列规则排序字符串数组
1.F一定出现在最前面；
2.L一定出现在最后面；
3.B一定要在A前面；
4.所有相同的字符串必须放在一起。
实际上再抽象一点就是，输入字符串是无序的，但是要确保输出是有序的。正常的思路就是将字符串的规则键转化为一个数字，然后进行数字排序，然而要处理字符串和索引的关系，这个如果不使用库里面的ADT还真麻烦，于是换一种思路，在扫描字符串的过程中就将其各归其位，各归其位的含义就是根据规则的优先级顺序找到自己的位置，那么二叉树是一个理想的选择。
       现在最关键的就是写一个getprio函数以及一个compare函数，而这个是很好办的。getprio函数的逻辑决定了最终的排序结果，这个函数可以做的很复杂，也可以很简单，比如为了能实现不感兴趣的字符串按照自然顺序输出，并且相同的排在一起这样的需求，可以为getprio函数保存一个容器，保存所有已经匹配到的不感兴趣的字符串的prio值。
    以下是全部的代码：

#include <stdio.h>
#include <stdlib.h>
#define MAX    32

//一个字符串链表，保存相同的prio的字符串
struct string_list {
    char *str;
    struct string_list *next;
};
//一个字符串包装，携带了一个prio
struct string_wrap {
    char *string;
    int prio;
};
//最终决定字符串位置的二叉树
struct string_node {
    struct string_list  *string;
    struct string_list  *last;
    int prio;
    struct string_node *left;
    struct string_node *right;
};
//声明要使用的函数
struct string_node *add_node(struct string_node *, struct string_wrap *str, int (*cmp)(struct string_wrap *, struct string_node *));
void print_result(struct string_node *);
//比较函数，比较优先级
int normalcmp(struct string_wrap *n1, struct string_node *n2)
{
    return  n1->prio - n2->prio;
}
//getprio函数，根据规则返回优先级
int getprio(char *s, int thread)
{
    static int prio = 1;
    if (!strcmp(s, "F"))
        return 0;
    if (!strcmp(s, "L"))
        return 100;
    if (!strcmp(s, "B"))
        return 50;
    if (!strcmp(s, "A"))
        return 51;
    //如果希望不想关的字符串按照输入顺序输出，则放开下面的注释
    //如果只是return prio++，那么字符串将按照原始顺序输出
    //return prio++;
    //返回自然顺序，和上面注释的意义一样
    return thread;
}

int main(int argc, char **argv)
{
    struct string_node *root;
    int thread = 0;
    char string[MAX];
    char *str[40] = {"L","F","A","dsfsfsg","L","B","A", "ss", "A"};
    
    root = NULL;
    int i = 0;
    while (str[i]) {
        int prio = getprio(str[i], ++thread);
        struct string_wrap sw = {str[i], prio};
        root = add_node(root, &sw, normalcmp);
        i ++;
    }
    print_result(root);
    return 0;
}
//标准的二叉树插入
struct string_node *add_node(struct string_node *p, struct string_wrap *new, int (*cmp)(struct string_wrap *n1, struct string_node *n2))
{
    int cmp_ret;
    
    if (p == NULL) {
        p = (struct string_node *)malloc(sizeof(struct string_node));
        p->string = (struct string_list*)malloc(sizeof(struct string_list));
        p->string->str = (char *)calloc(1, strlen(new->string));
        strcpy(p->string->str, new->string);
        p->last = p->string;
        p->prio = new->prio;
        p->left = p->right = NULL;
    } else if ((cmp_ret = cmp(new, p)) == 0) {
        struct string_list *next = (struct string_list*)calloc(1, sizeof(struct string_list));    
        next->str = (char *)calloc(1, strlen(new->string));
        strcpy(next->str, new->string);
        p->last->next = next;
    } else if (cmp_ret < 0) {
        p->left = add_node(p->left, new, cmp);
    } else {
        p->right = add_node(p->right, new, cmp);
    }
    
    return p;
}
//输出结果，如果不使用printf，可以用一个容器来装结果字符串
void print_result(struct string_node *p)
{
    if (p != NULL) {
        print_result(p->left);
        for (; p->string; p->string = p->string->next) {
            printf("%s\n", p->string->str);
        }
        print_result(p->right);    
    }
}

最后应该总结一下，其实写这类算法，切忌一开始第一个就考虑时间复杂度，先把它实现了再慢慢优化，不管再复杂，只要计算可以终止，那就是一个思路，你要用代码去实现自己的这个思路，然后再去想另一个思路，而不是先搞出一大堆图示，一大堆伪代码，然后加以比较，拼接，最终费了好大的劲实现一个四不像的算法。人的思路贵在第一印象，只要你能手工将凌乱的字符串排序成规则的，那么你一定有自己这么做的思路，所谓的算法就是用程序的语言将这个思路写下来，既然你能用文字来描述，为何不能用C语言或者java语言来描述呢？大O是以后的事情了，它只是一个事后的评价，在你有多个方案的时候，给出一个评价而已，如果一开始就以大O为基准，那么不会有好的结果，先把事情做了，再去考虑有没有更好的办法，而不是一开始就去考虑怎样做最好。
       还有一个问题和大O相关，如果你使用C++的STL容器来完成这个算法，首先你要知道这些容器操作的时间复杂度，然后才能计算你整个算法的时间复杂度，别以为代码简单了就高效了，你用了一个lookup完成了一个查找操作，假设STL中有lookup这个操作原语，而我用了10行C代码完成了同样的操作，你的可读性比我的好，效率也可能比我的好，然而真的100%比我的好吗？你知道loopup原语的时间复杂度吗？这好像又回到了最初的问题：
可读性第一，效率第二，不要去自己实现一个操作，为了榨取一点性能。
可是我不是很同意这个观点，作为一种精神，精益求精是每个程序员特别是有黑客精神的程序员所追求的，这种人特别希望将一切都置于自己的控制之下，即每件事都是可控的，代码的可读性仅仅是他们追求的一个方面而已，如果不是在做项目，不是为了及时交付，不是为了软件工程，那么可读性以及“最好使用库”就成了次要的。每一个精益求精的程序员追求的远远不只是软件工程中的那一套，他们应该把实现算法作为一种游戏来看待，以下举个例子。
       朋友远道而来，小区对面有一家上好的餐馆，好好吃上一顿算上酒水饮料要花300元，只需要你定好座位，付好钱，然后带着朋友去即可。另一个选择是，你去超市买上几斤肉，一些蔬菜，加上一些佐料和素材，再买上一瓶好酒，然后回家自己做，等待朋友的到来，总的花费嘛，可能已经远远超过了300元。你会怎样选择呢？如果算时间成本和方便度的话，下馆子是最好的办法，现在也一直都在提倡这么做，不是年夜饭也都这么搞了么？但是如果你想找到一种成就感和对朋友的那份心意，而不仅仅是想显示厨艺的话，我相信你会选择自己动手的，虽然很有可能由于厨艺不好会糟蹋了上好的材料(我经历了N多次)，然而意义却是不一样的。

       从工程学角度看，社会分工早就不需要自己做饭请客了，然而从生活的角度，家里还是要备一些厨具，最起码的意义是不一样的。程序员的感觉与此类似，虽然有那么多的库，那么多的框架可以使用，然而如果不是为了项目，仅仅是自己实现一个小想法的话，还是自己动手会好一些，当然那些库和框架也要会用，毕竟程序员的工作是为公司效力，而公司是完全站在软件工程的角度上考虑问题的。因此，不应该让大家总是使用库和既有的实现，在项目中这么做即可，平时自己做小玩意或者搞一点hack，还这么做，那就不太合适了。

       听科班出身的人说过，大学老师教导，初学编程，一定要先学命令行，然后再IDE，只是我不是科班出身，也没有受过那样的教导，虽如此，我还是很赞同的，如果不懂原理而只是简单的库拼接，那么只是空中楼阁，这样的人可能会是一个好的程序员，却很难成为一个好的设计者，紧急排错也最好不要找他们。我的观点并不是让大家都必须自己动手，说这句话也没有任何骄傲的成分，我只是想说：知其然，知其所以然，勿不求甚解。不求甚解，浮光掠影，下策！