数学工具版"每日一练"----7.6日

itmwk

<>7.6日</P>
<>今天的题目是一个关于matlab代码向量化的问题.</P>
<>大家知道,虽然matlab以其强大的功能和方便易用备受青睐,但是matlab有一个致命的弱点----它是解释执行的,程序中的变量都是用mxArray来实现的,为了保证代码的通用性就不得不以牺牲速度为代价.因此在一些大型运算(比如说比赛时需要处理大量数据时)中,尤其在一些运用了大量for循环的运算当中,它的速度有时是不可忍受的.这样如何提高matlab的速度就成为一个众人关注的焦点.通过mex等命令在matlab中直接调用C/Fortran是一种比较有效的方法,向量化是提高matlab速度的又一有效方法.</P>
<P>向量化的意思就是:编写或重新编写代码,以使对数组元素的标量操作,可以用数组操作来取代.</P>
<P>题目是这样的:</P>
<P>令N为任意正整数,若N为偶数则除以2,若是奇数则乘以3再加1,重复以上操作,直到N变为1.这个算法很有意思,对于任意的N,最终的结果都是1.    要求通过编制程序将数组(注意是数组)N化为每一个元素1,并要给出对每一个元素重复一轮操作的次数.   如果对于是标量的N,这个问题很容易解决,用个while循环就可以了,也没什么说的,但对于数组N来说难道要用一个for循环里面再嵌套while循环来实现么?这么做当然可以,但是不是最佳的方案,即,效率太低了,最后你可以试试,看看用for嵌套while循环的做法和我最后给出的做法运行时间哪个牛.</P>
<P>哪位有兴趣?来挑战一下?最后咱们来比一比cputime?</P>

[此贴子已经被作者于2004-7-7 10:57:51编辑过]

sword7_22

                             小循环包大循环可以用哦
         比如 考虑生成一个 5x10000 的 Hilbert 长方矩阵，该矩阵的定义是其第 i 行第 j 列元素为 h_{i,j}=1/(i+j-1)。我们可以由下面语句比较先进行 i=1:5 的循环和后进行该循环的耗时区别，其效果和前面分析的是一致的。
&gt;&gt; tic
for i=1:5
for j=1:10000
H(i,j)=1/(i+j-1);
end
end
toc
elapsed_time =
8.6800
&gt;&gt; tic,
for j=1:10000
for i=1:5
J(i,j)=1/(i+j-1);
end
end
toc
elapsed_time =
25.7000 <LI>大型矩阵的预先定维
给大型矩阵动态地定维是个很费时间的事。建议在定义大矩阵时，首先用 MATLAB 的内在函数，如zeros() 或 ones() 对之先进行定维，然后再进行赋值处理，这样会显著减少所需的时间的。</LI>[em07][em08]

wttw1987

<>matlab 7。0有多大啊？我下载了5分钟，正常吗？用网亟快车！</P>
<>你肯定是高手了，我不会用！</P>
<>谢谢指点！</P>
<P>QQ：273018034</P>

itmwk

<>没人来挑战一下么?那我先来抛砖引玉吧,并介绍提高matlab速度的第一个要点.</P><>提高matlab速度的第一个要点(楼上的也已经指出来了,大矩阵的预先定维),从例子看起吧:</P><>例:若我们先执行赋值语句(1):</P><P>Array=[1,3,5];</P><P>查看Array,其中元素为:1   3   5, 是一个1*3的矩阵</P><P>再执行赋值语句(2);</P><P>Array(2,=[2,4,6];</P><P>此时,我们再查看Array,其中元素变为:</P><P>[1   3   5;</P><P> 2   4   6];   是一个2*3的矩阵.</P><P>在上面对Array赋值的过程中,我们犯了一个错误.为了理解它,我们需要先了解一下matlab的内存使用方式,</P><P>当我们首先执行语句(1)时,matlab请求了一个1*3的连续内存来存放数组Array;当继续执行语句(2)时,因为需要更大的存储空间来存放Array这个数组,所以原来的内存空间要先被释放,然后再去向编译器和系统申请一个更大的连续的内存空间,也就是说增加了系统开销.当所涉及到的数组很大,或被重新赋值很多次(比如说在for循环中多次使用),那么内存分配的系统开销就会显著地降低算法的速度.</P><P>为了解决这个问题,(提高matlalb运行速度的第一个要点)在编程时应当尽量首先分配所需的所有内存,然后再根据需要一步步赋值.以上面的情况为例,也就是应该改成:</P><P>Array=ones(2,3);</P><P>Array(1,=[1,3,5];</P><P>Array(2,=[2,4,6];</P><P>将刚刚说过的这个要点用于本题,我们首先可以经过第一次提升速度的matlab程序:</P><P>Nums = 25:50;             % numbers to test
Counts=zeros(size(Nums)); % preallocate array
for i=1:length(Nums)
   N=Nums(i);  % number to test
   count = 0;  % iteration count
while N&gt;1
       if rem(N,2)==0 % even
          N=N/2;
          count=count+1;
       else           % odd
          N=(3*N+1)/2;
          count=count+2;
       end
end
Counts(i)=count;
end
results=[Nums' Counts']</P><P>上面的这个只是初步经过优化的程序,其中的for循环还有些是可以通过向量化的方法去掉的.谁有兴趣继续试试?</P>

turnip

<>顶！！！！</P>

Genial

<>我用find等函数矢量化了一下，但是测试结果发现效率更低了</P><>主要问题就出在find这个函数上了</P><>感觉这个函数可能matlab中没有写好</P><P>function results = myfun(Nums)
NumsBck = Nums;
Counts=zeros(size(Nums)); % preallocate array
index = find(Nums&gt;1);
while (~isempty(index))
    indexodd = find(rem(Nums,2)&amp;(Nums&gt;1));
    Nums(indexodd) = (3*Nums(indexodd)+1)/2;
    Counts(indexodd) = Counts(indexodd)+1;
    indexeven = find(~rem(Nums,2));
    Nums(indexeven) = Nums(indexeven)/2;
    Counts(indexeven) = Counts(indexeven)+1;
    index = find(Nums&gt;1);
end
results=[NumsBck' Counts'];</P><P><b> 6</b>     indexodd = find(rem(Nums,2)&amp;(Nums&gt;1));  占了将近整个程序运行的40%的时间
</P><P><b>10</b>     Nums(indexeven) = Nums(indexeven)/2;不明白为什么这句也占了整个程序运行时间的20％ </P><P>

</P>

conscious

<>meshgrid() 函数构造这样可以减少循环的时间例如</P><>tic, [i,j]=meshgrid(1:5,1:10000); H=1./(i+j-1); toc
</P>

mn123

14323

IrontFEI翔

[em04]

sangbo8888

——悖论是数学界的幽灵，幽灵！！