Re: letrec/named let
- To: mathgroup at smc.vnet.net
- Subject: [mg56830] Re: letrec/named let
- From: "Carl K. Woll" <carl at woll2woll.com>
- Date: Sat, 7 May 2005 04:16:44 -0400 (EDT)
- References: <069a01c55260$afdad760$6400a8c0@Main> <opsqc8fk0aiz9bcq@monster.ma.dl.cox.net>
- Sender: owner-wri-mathgroup at wolfram.com
----- Original Message ----- From: "DrBob" <drbob at bigfoot.com> To: mathgroup at smc.vnet.net Subject: [mg56830] Re: letrec/named let > That's a very nice "rescue" of the Ordering@Ordering solution. > > Here's a test with (probably) no repeated elements, however, that shows > treat ahead. Perhaps there's an intermediate situation where carl wins, or > it matters whether the data is integer or real? > > data=Table[Random[],{10^6}]; > Timing[one=treat@data;] > Timing[three=carl@data;] > one==three > > {10.109 Second,Null} > {15.938 Second,Null} > True > Interesting. On my machine, carl is over 5 times faster than treat for the same test. I have version 4.1 on a Windows XP operating system. What is your setup? Perhaps you could test each individual line of carl to see where the bottleneck is. Carl Woll > Bobby > > On Fri, 6 May 2005 13:26:03 -0400, Carl K. Woll <carlw at u.washington.edu> > wrote: > >> "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 >> >> >> >> >> >> >> > > > > -- > DrBob at bigfoot.com > >