字符串按规则排序算法

晨曦之光 发布于 2012/04/10 14:56
阅读 453
收藏 0
写这个东西源自于公司组织的一次编程道场,最后的总结就是,尽量使用既有的库,将问题转化为既有库算法能解决的问题,可读性第一,效率第二。老大们说的话总是让人觉得醍醐灌顶,不要自己实现一个功能为了去榨取那么一点点性能,最终还不一定能榨出来!不知道有没有什么特别的原因,最后几位老大展示出的代码竟然一模一样,虽然语言不同,那就像直接的翻译一般,难道编程有其道,而老大们均掌握了“道”?
       我也想出了那种“标准的做法”,只是我根本不会用什么库,也根本不了解库,虽然有了伪代码,然而在将其转化为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,只是我不是科班出身,也没有受过那样的教导,虽如此,我还是很赞同的,如果不懂原理而只是简单的库拼接,那么只是空中楼阁,这样的人可能会是一个好的程序员,却很难成为一个好的设计者,紧急排错也最好不要找他们。我的观点并不是让大家都必须自己动手,说这句话也没有任何骄傲的成分,我只是想说:知其然,知其所以然,勿不求甚解。不求甚解,浮光掠影,下策!



原文链接:http://blog.csdn.net/dog250/article/details/7051468
加载中
返回顶部
顶部