Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
1999
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 1999

[Date Index] [Thread Index] [Author Index]

Search the Archive

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



  • Prev by Date: Re: Cumulative distribution of Gauss
  • Next by Date: Re: LaTex on a Mac
  • Previous by thread: Re: Position of Sign change in long list
  • Next by thread: Re: Position of Sign change in long list