Re: Position of Sign change in long list

*To*: mathgroup at smc.vnet.net*Subject*: [mg18709] Re: [mg18691] Position of Sign change in long list*From*: "Wolf, Hartmut" <hwolf at debis.com>*Date*: Sat, 17 Jul 1999 02:36:33 -0400*Organization*: debis Systemhaus*References*: <199907150546.BAA15968@smc.vnet.net.>*Sender*: owner-wri-mathgroup at wolfram.com

Hello Martin, Martin Rommel schrieb: > > I have a long list of data points and need to find the position where the > sign changes for the first time. > My first attempt was > > test=Table[Sin[Pi i/5000. +1],{i,10000}]; > > With[{a=Abs[test]},Position[a,Min[a]]] > > which works, but is slow. It turns out that Min is relatively slow and > avoiding it can save time. The following is almost a factor 4 faster: > > With[{st=Sign[test]},Length[Split[st][[1]]]] > > If you can think of a still faster or more elegant solution please let me > know! > The timings I found on your data "test" were: In[2]:= With[{a=Abs[test]},Position[a,Min[a]]] //Timing Out[2]= {0.651 Second,{{3408}}} -- is that too slow?? In[3]:= With[{st=Sign[test]},Length[Split[st][[1]]]] //Timing Out[3]= {0.17 Second,3408} whereas e.g. In[4]:= scata[l_]:= Module[{s=Sign[l[[1]]],n=0},Catch[If[Sign[#]=!=s,Throw[n],n++]& /@ l]] In[5]:= scata[test]//Timing Out[5]= {0.5 Second,3408} In[6]:= ff[s0_,x_]:=If[Sign[x]=!=s0,Throw[n],n++;s0] In[7]:= Block[{l=test,n=0}, Catch[Fold[ff,Sign[[[1]]],l]] ]//Timing Out[7]= {0.631 Second,3408} So your second algorithm looks superior. However I have found another one, which gives: In[32]:= scBS[test]//Timing Out[32]= {0. Second,3408} Before talking about elegance, let's talk about correctness. I have set up another sample of test data: In[13]:= Length[test2] Out[13]= 10000 With that let's repeat: In[9]:= With[{st=Sign[test2]},Length[Split[st][[1]]]] //Timing Out[9]= {0.211 Second,4} -- not quite as good as before In[10]:= scata[test2]//Timing Out[10]= {0.07 Second,4} -- *much* better than before In[11]:= Block[{l=test2,n=0}, Catch[Fold[ff,Sign[[[1]]],l]] ]//Timing Out[11]= {0.07 Second,4} -- also much better but!!!!!! In[12]:= With[{a=Abs[test2]},Position[a,Min[a]]] //Timing Out[12]= {0.881 Second,{{4259}}} -- ***wrong*** answer and "mine" too In[17]:= scBS[test2]//Timing Out[17]= {0. Second,8318} -- again lightning fast, -- but also ***wrong*** Now, why did you consider your "Min"-algorithm at all in first place? I believe, thats why your problem is *not* "need to find the position where the sign changes for the first time" but more something like: "If there is only one zero-crossing in the sample, then find it." For *that* problem, your "Min"-algorithm is still not quite correct (there is doubt if the point is the last before or the first after the crossing -- but you can easily fix that), but *then* you can also use "mine": In[15]:= scBS[lis_]:= Module[{s1=Sign[lis[[1]]],l=1,r=Length[lis],m}, While[l=!=r, If[Sign[lis[[m=Floor[(l+r)/2]]]]=!=s1,r=m,l=m+1] ]; If[Sign[lis[[l]]]=!=s1,l-1,"no sign change"] ] which is O[log n], whereas your first problem can't be solved better than O[n]. What was my sample test2? In[8]:= test2=Table[Random[]-0.5,{10000}]; Perhaps your problem isn't quite "If there is only one zero-crossing..." but obviously the data come from some physical or computational process which is not completely random. So perhaps you can make assumptions of your data, e.g. there is a maximum possible frequency in them. In that case you may scan your data with binary searches on parts not longer than the "wavelength", beginning at the left, and stopping after having found the first zero crossing. The general rule is: put all your knowledge of the data into the algorithm, and you will get *your* fastest ever possible. What about elegance? Elegant solutions come from very simple assumptions. So your "Split"-algoritm is very elegant, not always best, but possibly best for that pre-knowledge of the data you have. Kind regards, hw

**References**:**Position of Sign change in long list***From:*"Martin Rommel" <rommel@semitest.com>