小小算法竞赛(1)，大家都来参加呀----MIT的matlab练习题

newface

playlord wrote:
的确不难

我晕倒...还好我有一分,能看到前面的东东,大牛写的贴子刚刚让我赞叹不已,然后就看到了老兄的豪言...嘿嘿...不用循环,用两种方法,老兄作一下,让我们这些菜鸟也长长见识如何?:D:P;)8D

qingruan

bzzz wrote:
和你的想法类似

a=rand(1,100);
find(diff(sign(diff(a)))<0)+1

a = [1 2 3 4 4 5];
find(diff(sign(diff(a)))<0)+1
ans =
         4

home96

原帖由 bzzz 于 2005-1-13 13:49 发表
和你的想法类似

a=rand(1,100);
find(diff(sign(diff(a)))>0)+1

试了一下，感觉中间的 '>' 应为 '<'
'>' 时找出来的是小于两边数的那个数

mitm1984

感觉这道题就是求一条曲线的局部最大值
我平时的方法是

find(diff(sign(diff(x)))==-2)+1

和bzzz的差不多
不过他写的是局部最小值:L

zflvanilla

多多来逛论坛真是受益匪浅啊 :victory:

slurry

似乎find(diff(sign(diff(a)))>0)+1不对吧？下面是我的结果：
>> a=[1 3 4 8 1 2 5 10 23 10 51 61 51]
>> find(diff(sign(diff(a)))>0)+1

ans =

     5    10
而第5个和第10个分别是极小值，而不是极大值。

bainhome

改成“<0”就是极大值

fsnow82

感觉挺像高数里的二阶导数小于0时为极大值，不过这里用差分代替了求导

ni_engineer

最好的方法就是左移右移然后相减求出index；用系统函数的做法不可取，浪费资源，占用内存，你试试看如果是一个1X1_000_000_000的矩阵，比较一下运算速度，嘿嘿。代码简洁不等于优化。

bainhome

你试试看如果是一个1X1_000_000_000的矩阵

道理不错，不过请教：
这好像是个一亿阶的向量，你在MATLAB中“左移右移”一下，把运算时间和你机器的配置给大家报一下来验证你的说法是否正确，谢谢。

ni_engineer

建议楼上的大哥哥去读programming pearl第一章节，谢谢！:kiss:

bainhome

请注意，关于代码的高效性和简洁性之间关系的基本原理，估计在这里很多人都知道，很多专著中也早有论述，未必需要去看您指定的哦。我虽然层次比较低，但是也看过类似论述，这里我们要的是实践结果。
否则，谁知道您是不是在吹牛皮放大炮？二半吊子读两本书什么也不会，就长个胆子敢出来纸上谈兵的主儿太多了，我的目的出发点也是比较善意的：想把您从这些人中给区分出来，让大家不要以为您也是这种光吹不练的滥人(当然您说话这么严谨肯定不属于这种垃圾喽，一亿阶的矩阵您只有在PC机上使用MATLAB解过不少，才会有上面的神奇结论)。
这样，大家才能对您的英明论断心服口服，当然您也不会在乎这点儿“我是不是 I can play”的虚名，但是大家抱着求知寻找真理的态度，还是想让您给个答案以满足同学们对真理的好奇心，谢谢。

[ 本帖最后由 bainhome 于 2007-11-29 16:07 编辑 ]

pigsoso

挺有意思的题目啊...

nanyi545

原帖由 bzzz 于 2005-1-13 13:49 发表
和你的想法类似

a=rand(1,100);
find(diff(sign(diff(a)))>0)+1

算法不对么
原向量相邻元素一定不等？

Tla

我的第一反应是用这一种方式:
[quato] find((a(2:99)>a(1:98) & a(2:99)>a(3:100))==1)+1; [quato]
没有想到过用这种:
[quato] find(diff(sign(diff(a)))<0)+1;  [/quato]
而且,凭自个儿的感觉和经验,逻辑操作的方式应该比调用函数的方式更快一些,但在实际测试了一下,结果非常惊奇:第二种比第一种执行起来要快得多(1/2多一些),在 cpu T7250,内存1G,OS: xp sp2, Matlab 7.0 的hp笔记本上面跑几十次,结果都是第一种比第二种慢 e-5 的数量级,执行速度在1 * e-4左右.刚开始还有一些想不太明白.但最后想起了前一些时候,一个朋友分析M代码编译成的CPP代码时,似乎把很多操作都变成了调用函数来实现.连加减都是这样做的(没有确定过),逻辑操作自然也应该是. sign, diff都是built-in的函数,这里面即便有加减运算,应该不会是另外写一个函数来实现,少了这么多的调用,自然速度就更快.如果真的是这样的话,这也说明:要提高Matlab代码的运行速度,尽量多用 built-in 的函数,连> <都要少用了;P .

赶明儿写一个mex函数再试一下,再把这两种方式写的Matlab代码编译成cpp的代码再看一下,应该就清楚了

poplai

学习一下啊！

风天小畜

代码简洁和效率的讨论，肯定是很多的。
一个例子，100次左右的循环，有人，用 for 循环，几行代码搞定。
但是，事实上，最优的速度，是把一百次循环的代码，不用循环。
展开后的循环，多了几百倍行数的冗余代码。
但是，效率提高了很多。

编译器优化里面就有这么些玩意。
C语言，和汇编，他们的思路，代表着执行效率。

本题目，我可以用 汇编，结合 SIMD 优化，写出最高执行效率的。

对于matlab ，

1. tic
   
2. n=10000;  %定义多大的矩阵，即题目的行向量
   
3. aai=rand(1,n);  %用随机数生成 原始的行向量aai
   
4. OKvalue=aai(aai>[aai(2:n) 0] & aai>[0 aai(1:n-1)]);
   
5. toc
   
6. 
   
7. Elapsed time is 0.004579 seconds.

复制代码

。

测试结果如上，这是一万大小的行向量。

机器，是
2 GB memory
2.4G Opteron 146 Processor（05年的处理器，单核）
老机器，速度是这种情况.


很久没用 matlab 了，如果，哪位把 矩阵赋值，aal，aar 那一段修改一下。
速度更快。、。。



一千万 大小的行向量，也仅需 一秒多的时间

1. tic
   
2. n=10000000;
   
3. aai=rand(1,n);
   
4. OKvalue=aai(aai>[aai(2:n) 0] & aai>[0 aai(1:n-1)]);
   
5. toc
   
6. 
   
7. Elapsed time is 1.279018 seconds.

复制代码

性能图片




第二次测试计算，截图为内存占用。
内存占用





五千万行向量，五秒多

yingsly

36# nanyi545

真是很不错，感觉改为
a=rand(1,100);
find(diff(sign(diff(a)))<-1)+1
更准确

不过最妙的还是 bzzz 的算法