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

Re: letrec/named let

• To: mathgroup at smc.vnet.net
• Subject: [mg56828] Re: letrec/named let
• From: "Carl K. Woll" <carlw at u.washington.edu>
• Date: Sat, 7 May 2005 04:16:42 -0400 (EDT)
• Organization: University of Washington
• References: <200505040433.AAA06220@smc.vnet.net> <6bd33c74358661121c5a59d79fcccad0@mimuw.edu.pl> <1115215689.31793.86.camel@30-5-214.wireless.csail.mit.edu> <200505051001.GAA21966@smc.vnet.net> <d5f5ka$6dn$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

"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 

• References:
  • letrec/named let
    • From: Daniel Roy <droy@mit.edu>
  • Re: letrec/named let
    • From: Andrzej Kozlowski <akoz@mimuw.edu.pl>