Chinaunix首页 | 论坛 | 博客
  • 博客访问: 353109
  • 博文数量: 53
  • 博客积分: 25
  • 博客等级: 民兵
  • 技术积分: 1548
  • 用 户 组: 普通用户
  • 注册时间: 2012-03-27 07:54
个人简介

IT民工一枚,为学弟学妹造福是我一直写博文的动力!为媳妇提供技术支持是我学习新技术的动力!为自己脱离贫困线,买到心仪的摩托车,有饭吃,有床睡,有妹把,笔耕不辍~~

文章分类

全部博文(53)

文章存档

2013年(54)

分类: C/C++

2013-10-24 11:41:29

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

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

那就开始吧。

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

点击(此处)折叠或打开

  1. int find(int array[], int length, int value)
  2. {
  3.      int index = 0;
  4.      //Add code to search
  5.      return index;
  6. }
中间那些实现代码怎么实现呢?这个问题就是算法了。当然这里比较简单。
1. 验证参数
2. 循环实现遍历

点击(此处)折叠或打开

  1. int find(int array[], int length, int value)
  2. {
  3.     if((array == NULL) || (length == 0))
  4.         return FALSE;
  5.     int index = 0;
  6.     for(; index < length; index++)
  7.     {
  8.          if(value == array[index])
  9.                return value;
  10.      }
  11.      return FALSE;
  12. }
验证一下

点击(此处)折叠或打开

  1. static void test()
  2. {
  3.     int array[10] = {1, 2};
  4.     assert(0 == find(array, 10, 1));
  5.     assert(FALSE == find(array, 10, 10));
  6. }
顺序查找就这么简单实现了。实际上,我们实现算法的过程是简单和常规的,问题在于:
1. 能否优化算法工程过程。
2. 能否优化算法处理过程。
3. 能否优化代码结构。
4. 能否测量算法功耗。
。。。(其他可能出现的问题,在今后相对复杂的问题中再提出)

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

点击(此处)折叠或打开

  1. int find(int array[], int length, int value)
  2. {
  3.     if(NULL == array || 0 == length)
  4.         return FALSE;
  5.   
  6.     int* start = array;
  7.     int* end = array + length;
  8.     while(start < end){
  9.         if(value == *start)
  10.             return ((int)start - (int)array)/(sizeof(int));
  11.         start ++;
  12.     }
  13.     start=end=NULL;
  14.     return FALSE;
  15. }
说明两点:
1. 虽然我不喜欢用数组,但是“买的房子总比租的要踏实一点”我想你懂。
2. 你可以用数组的思想去建模,但是最好用指针来实现,因为“房子不总是那么够用”。现在的问题就是如何把算法升级过来呢?
一般我是这么做的:1)找到最核心的部分代码;2)把for循环的起止条件换成指针的移动范围;3)使用指针自加代替索引变量的自加;4)最后不要忘记给指针一个合适的归宿。不然那些都是炸弹。

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


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




阅读(3301) | 评论(0) | 转发(0) |
0

上一篇:回归,就得有个回归的态度

下一篇:没有了

给主人留下些什么吧!~~