MathGroup Archive 2005

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

Search the Archive

Re: letrec/named let


"DrBob" <drbob at bigfoot.com> wrote in message 
news:d5f5ka$6dn$1 at smc.vnet.net...
> Our solutions agree on lists of strictly positive integers, but timings 
> depend a great deal on the minimum value:
>
> Clear[treat, andrzej]
> treat[s_List] := Module[{u = Union@s}, s /. Dispatch@Thread[u -> Range@
>     Length@u]]
> andrzej[s_List] :=
>      First@NestWhile[Apply[If[FreeQ[##], {#1 /. x_ /;
>             x > #2 :> x - 1, #2}, {#1, #2 + 1}] &, #] &, {s, 1},
>     Last[#] < Max[First[#]] &]
>
> data=1+RandomArray[PoissonDistribution[2],{10^6}];
> Timing[one=treat@data;]
> Timing[two=andrzej@data;]
> one == two
>
> {0.593 Second,Null}
> {0.657 Second,Null}
> True
>

[snip]

Another possibility modeled after DrBob's first answer is the following:

carl[s_] := Module[{ord,t},
 ord = Ordering[s];
 t = FoldList[Plus, 1, Sign[Abs[ListCorrelate[{1, -1}, s[[ord]]]]]];
 t[[Ordering[ord]]]
]

If there are a lot of repeated elements in the data, then treat seems to be 
faster. On the other hand, if there aren't a lot of repeated elements, then 
carl seems to be faster. It seems like it ought to be possible to compute 
Ordering[Ordering[data]] more quickly since 
Ordering[Ordering[Ordering[data]]] equals Ordering[data], but I couldn't 
think of a way.

Carl Woll 



  • Prev by Date: How to quickly find number of non-zero elements in sparse matrix rows?
  • Next by Date: Re: InitializationCell -> Toggle shortcut key
  • Previous by thread: Re: Re: letrec/named let
  • Next by thread: Re: letrec/named let