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>
- letrec/named let