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>
- Position of Sign change in long list