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>