matlab效率提升独孤九剑(附fft优化的详细例子).doc

matlab效率提升独孤九剑作者:信科@滨matlab效率提升葵花宝典        5附录:自编fft函数的优化详解  6参考资料:  ,无非在两个方面:天生的和后天的。第一个方面是算法本身的复杂度。比如插入排序复杂度为O(N2),而快速排序算法是O(NlnN),当然在大数据量时快速排序就比插入排序快很多了,这就是算法天生的优越性。所以世界并不是决定公平的啊,有的人就可以成为快速排序,而其他人只能成为插入排序,呵呵。第二个方面是算法具体实现的问题。实现算法的方式不同,写程序的人不同,使用的语言不同,优化方式的不同,是否多线程,是否并行,都会使得同一算法的不同实现时间相差十倍以上,我们称之为后天的。所以当起跑线差不多时,就看谁更拼命了,所以最终有人就是冠军而有的就只能千年老二。这也是造成社会不公平的原因。有时候就算有的高手实现插入排序都比菜鸟写的快速排序快上不少,我们可以称之为“屌丝的逆袭”,屌丝不遗憾,就看有没有一颗拼搏的心了。而这篇文章详细介绍第二方面的算法具体实现的效率问题。这是我这三年来编写matlab程序的一些经验和教训的总结,外加网上各路人马的观点,由于写测试例子太费时费力,不重要的就不写了。:观点传统现代向量化编程,避免使用循环YESNO多使用MATLAB的内置函数YESYES能用逻辑索引解决的就不用数值索引YESYES变量预分配YESYES尽量不用Cell型数组YES?矩阵含有大量0元素,采用稀疏矩阵YESYESinplaceoperationN0YES列向量存储YESYES   对向量化:由于matlab2007之后的JIT和加速器技术,使得for和向量化的差别不明显了。注意向量化可能会占用大量的内存,有时候for循环更好读。逻辑索引:采用逻辑索引比数值索引(find)快30%左右。cell:我一般用结构体代替,但是有时候用cell更方便,需要看情况而定,可能cell更方便,直观,程序可读性更好。一般瓶颈也不在这儿值得商榷。预分配:比如后面的循环要用到一个1000的数组,先预分配x=zeros(1,1000);稀疏矩阵:稀疏矩阵一般有专门的稀疏算法,可能效率更高,更省内存。由于平时没怎么用过,不发表意见。刚才看到一个减少变量赋值的次数的技术:inplaceoperation:就是如果输入参数要返回的话,就让输出参数和输入参数同名,减少赋值次数。举个例子:functiony=f1(x)y=x+1;end我们可以改写成functionx=f2(x)x=x+1;end经过测试发现f2比f1快了110%,很是明显。使用mex文件:用其他语言来实现需要的功能,避开matlab的瓶颈。用乘法代替除法进行向量运算:b=a/;改成b=a*(1/);经过测试速度快了三倍!神奇啊!这也是我无意之中发现的,看来乘法跟除法还是差别大啊。尽量用列向量进行操作:因为matlab的矩阵是按列存放的,对其进行存取的速度比行的方式要快20%。:,便于找到程序的错误和疏忽的地方。,找出性能瓶颈,其实很多时候上面提到的注意事项并不是最花时间的,有时候就一两句话就花了差不多80%的时间,注意2/8原则。附录:自编fft函数的优化详解下面我以这两天我写的fft快速傅里叶变换作为上述优化方法的应用。我是参考北京大学张平文写的《数值分析》中的算法来实现的。x=FFT(t),这儿就无意之中用到了inplaceoperation技术,呵呵。大概流程:,:fft也可以采用递归的方式进行求解,但是速度跟迭代的方式没法比,而且内存占用高。第一步:重新排列x的顺序的具体实现function[order]=t,n)%得到次序order=zeros(t);order(1:2)=[t/2+1];t/2;num=1;fori=1:n-1num=num*2;i_2=i_2/2;order(num+1:num*2)=order(1:num)+i_2;endend评注:此处我用了预分配技术,向量化操作。这个没啥好说的,而且时间也不是花在这儿。不过我感觉我的这种实现方法很是精妙,哈哈。第二步:=wn(t)w=t/2,n);i_2=1;fori=2:n%2^ii_2=i_2*2;ww=exp(-(pi/i_2)*1j);w(i,2:i_2)=ww.^(1:i_2-1);%这种实现方式效率较低,没有利用特殊性endend由于第三步需要进行一个