字符串按规则排序算法 |dog250

winston

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

2. #include <stdio.h>
3. #include <stdlib.h>
4. #define MAX    32
6. //一个字符串链表，保存相同的prio的字符串
7. struct string_list {
8.     char *str;
9.     struct string_list *next;
10. };
11. //一个字符串包装，携带了一个prio
12. struct string_wrap {
13.     char *string;
14.     int prio;
15. };
16. //最终决定字符串位置的二叉树
17. struct string_node {
18.     struct string_list  *string;
19.     struct string_list  *last;
20.     int prio;
21.     struct string_node *left;
22.     struct string_node *right;
23. };
24. //声明要使用的函数
25. struct string_node *add_node(struct string_node *, struct string_wrap *str, int (*cmp)(struct string_wrap *, struct string_node *));
26. void print_result(struct string_node *);
27. //比较函数，比较优先级
28. int normalcmp(struct string_wrap *n1, struct string_node *n2)
29. {
30.     return  n1->prio - n2->prio;
31. }
32. //getprio函数，根据规则返回优先级
33. int getprio(char *s, int thread)
34. {
35.     static int prio = 1;
36.     if (!strcmp(s, "F"))
37.         return 0;
38.     if (!strcmp(s, "L"))
39.         return 100;
40.     if (!strcmp(s, "B"))
41.         return 50;
42.     if (!strcmp(s, "A"))
43.         return 51;
44.     //如果希望不想关的字符串按照输入顺序输出，则放开下面的注释
45.     //如果只是return prio++，那么字符串将按照原始顺序输出
46.     //return prio++;
47.     //返回自然顺序，和上面注释的意义一样
48.     return thread;
49. }
51. int main(int argc, char **argv)
52. {
53.     struct string_node *root;
54.     int thread = 0;
55.     char string[MAX];
56.     char *str[40] = {"L","F","A","dsfsfsg","L","B","A", "ss", "A"};
57.    
58.     root = NULL;
59.     int i = 0;
60.     while (str[i]) {
61.         int prio = getprio(str[i], ++thread);
62.         struct string_wrap sw = {str[i], prio};
63.         root = add_node(root, &sw, normalcmp);
64.         i ++;
65.     }
66.     print_result(root);
67.     return 0;
68. }
69. //标准的二叉树插入
70. struct string_node *add_node(struct string_node *p, struct string_wrap *new, int (*cmp)(struct string_wrap *n1, struct string_node *n2))
71. {
72.     int cmp_ret;
73.    
74.     if (p == NULL) {
75.         p = (struct string_node *)malloc(sizeof(struct string_node));
76.         p->string = (struct string_list*)malloc(sizeof(struct string_list));
77.         p->string->str = (char *)calloc(1, strlen(new->string));
78.         strcpy(p->string->str, new->string);
79.         p->last = p->string;
80.         p->prio = new->prio;
81.         p->left = p->right = NULL;
82.     } else if ((cmp_ret = cmp(new, p)) == 0) {
83.         struct string_list *next = (struct string_list*)calloc(1, sizeof(struct string_list));   
84.         next->str = (char *)calloc(1, strlen(new->string));
85.         strcpy(next->str, new->string);
86.         p->last->next = next;
87.     } else if (cmp_ret < 0) {
88.         p->left = add_node(p->left, new, cmp);
89.     } else {
90.         p->right = add_node(p->right, new, cmp);
91.     }
92.    
93.     return p;
94. }
95. //输出结果，如果不使用printf，可以用一个容器来装结果字符串
96. void print_result(struct string_node *p)
97. {
98.     if (p != NULL) {
99.         print_result(p->left);
100.         for (; p->string; p->string = p->string->next) {
101.             printf("%s\n", p->string->str);
102.         }
103.         print_result(p->right);   
104.     }
105. }

复制代码

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