说说算法

中山野鬼 发布于 2012/06/27 22:36
阅读 481
收藏 4

以前别人问我是不是搞IT的,我经常说不是。省得问我”哎呀,帮我装个软件,哎呀手机有问题,哎呀帮我这个那个。。“

所以我一直说我自己是做算法的,不是写软件的。当然也确实做算法。这和这里的很多朋友从事软件开发,不太一样,因此我说说算法设计的一些关注点(个人观点,欢迎喷)

1、原理最重要。例如这里一个朋友,分析的,素数求解,已知连续两个素数之间的差值目前是多少。则这个直接影响到计算方法。

2、原型验证很关键。做算法,如果有原型,例如H264,有标准对应的JM版本,那么余下的事情属于工程化处理,包括移植,优化,也是算法工作,但原型验证已经完成。而头痛的属于没有原型,搭原型。当然这里不是说一个排序的逻辑算法。

例如我们要对超过1T的数据进行排序,而不是100个数据排序,传统的冒泡算法在那,这个也不能叫原型,为什么?冒泡算法有,你申请个1T的数据空间试试(每个数据单元未至少64位就是8个BYTE,如果小于64位,用32位描述就不存在1T的排序问题了)?所有的数据甚至不在一个硬盘上。那么我们需要用分治策略结合堆排序的等方式实现,中间还有一堆文件读入,索引的等问题。错一个步骤,结果就不会正确。

当然原型并不是说一定要实际的量,而是实际的所有工作均包含到。

代码很难没错,特别是做原型,此时,算法如果用面向对象的思想分析,则是悲剧。必须模块化的将系统的动作分解为独立的功能模块,一一设计,一一验证。这是设计思想。

而对于验证,目前我采用的方法是交叉比对的方式。也即,原理出来,两个人关门写。同时执行相同测试数据,判断结果。代码出错很常见,两套不同的代码错的一模一样,挺难。

3、全面了解硬件状态。包括当前的,和未来的(为扩充做准备)。其实和人剑合一的思想很像。只有做到贱人的地步,才能做出够贱的事情。不是我偏袒C,我会用的高级语言中,C算最贴近硬件,最容易按照硬件模型去规划程序逻辑的。别提C++,如果C++的代码也可以,放心那段代码一定是C风格(即COPY一下,改吧,改吧,就是C语言),我不反对C++具有自身优势,但我反对把C++的C风格的代码作为C++的优势,这简直是自相矛盾的事情。C++是一个长的像C的面向对象语言,但不是个兼容C的语言。

4、关注微结构,关注微操作。多用#define 。有人说#define 是老土,哈,多看看linux的源码,就知道微操的威力了。微操,可以在保证效率下,极大的提高代码质量,(阅读性,编辑正确性等等)

5、充分了解编译器特性。在后期优化中,对于编译器不太了解的地方,甚至需要使用反汇编理解编译器对C代码的编译特点,而重新规划C代码的操作(微操作)。

6、只做该做的事情。比如,编译器能做的,别做。硬件能做的,别做,例如,DMA的驱动我就不写了,XDMA(一种多维DMA驱动)折腾过好几次,为什么?快啊,比你整逻辑快多了。整个算法设计和优化过程,可以理解为,陪着原理玩,陪着硬件玩,陪着编译器玩的过程,把他们三样都伺候到位了,基本效果就出来了。

7、别太在意理论。当然前提是你对理论已经理解深刻。理论是抽象的东西,很多边界条件方的很宽。包括什么数据结构的标准代码,排序,内插,HASH等算法的标准代码。我仍然重复一个例子,快速算法比冒泡快吧,如果你对8个以内的数据排序,我只能说,谁用快速谁SB。如果结合DSP指令或类似MMX,SEE2等并发指令,你用改良的冒泡更快。

并非越简单的算法一定越好,但越简单的算法,越能拟合硬件特性,用指令进行描述。例如曾经在DSP上做的IDCT算法优化。后来发现,非0系数超过5个后(总共16个系数),全部计算的速度是最快的。

最后说个找喷的,或者看似无厘头的话:若问我算法有什么设计模式,设计规则?我觉得就一条:没有任何规则,就是规则。准确说,不被任何外在模式,方法约束(所谓理论或经典的)而实事求是的三面向的搞(面向原理,面向硬件,面向编译器)。

加载中
0
宏哥
宏哥

算法这个东西不能狭隘化.

视频解码是算法, 通过激光束测定纺线速度是算法,SHA1, RSA都是算法.... 但是不仅于此

通过 Application dictionary 来管理 数据关系,也是算法, UI逻辑也是算法, 甚至渠道管理也是算法....

程序嘛, 不就是数据 + 算法吗?

这个东西,本质就是业务. 

0
中山野鬼
中山野鬼

引用来自“宏哥”的答案

算法这个东西不能狭隘化.

视频解码是算法, 通过激光束测定纺线速度是算法,SHA1, RSA都是算法.... 但是不仅于此

通过 Application dictionary 来管理 数据关系,也是算法, UI逻辑也是算法, 甚至渠道管理也是算法....

程序嘛, 不就是数据 + 算法吗?

这个东西,本质就是业务. 

极为赞同。所以小功能库,和大系统,都是必须面向模块折腾的。卡中中间的APP,确实面向对象设计思想应用的场合更多。
叶玉祥
继续测试
0
十一文
十一文
追贴而来。严重同意第7点。我认为应该放在第一
0
vema
vema
面向业务和你的用户
0
杨同学
杨同学
膜拜一下。PS:楼主做嵌入式的?
0
中山野鬼
中山野鬼

引用来自“杨同学”的答案

膜拜一下。PS:楼主做嵌入式的?
哈,跟着需求来。不过现在不做了。。。
叶玉祥
再测试下的
叶玉祥
测试下的
返回顶部
顶部