Re: Re: letrec/named let
- To: mathgroup at smc.vnet.net
- Subject: [mg56792] Re: [mg56752] Re: [mg56707] letrec/named let
- From: DrBob <drbob at bigfoot.com>
- Date: Fri, 6 May 2005 03:00:01 -0400 (EDT)
- 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>
- Reply-to: drbob at bigfoot.com
- Sender: owner-wri-mathgroup at wolfram.com
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 data = 10 + RandomArray[PoissonDistribution[2], {10^6}]; Timing[one = treat@data;] Timing[two = andrzej@data;] one == two {0.61 Second,Null} {13.671 Second,Null} True This is all it takes to fix that problem, however: andrzej2[s_List] := andrzej[s + (1 - Min@s)] data = 10 + RandomArray[PoissonDistribution[2], {10^6}]; Timing[one = treat@data;] Timing[two = andrzej@data;] Timing[three = andrzej2@data;] one == two == three {0.594 Second,Null} {13.64 Second,Null} {0.657 Second,Null} True As a side-effect, andrzej2 agrees with my solution on arbitrary lists of integers: data = -7 + RandomArray[PoissonDistribution[2], {10^6}]; Timing[one = treat@data;] Timing[two = andrzej@data;] Timing[three = andrzej2@data;] one == two one == three {0.578 Second,Null} {0.218 Second,Null} {0.61 Second,Null} False True Bobby On Thu, 5 May 2005 06:01:33 -0400 (EDT), Andrzej Kozlowski <akoz at mimuw.edu.pl> wrote: > Unfortunately I really can't afford to spend as much time on such > questions as i would like but I hope someone else will take up this > discussion. Let me just quickly point out you can eliminate the use of > With, First and Last in various ways, for example: > > CompressNumericalSequence2[s_] := First[NestWhile[ Apply[If[FreeQ[##], > {#1 /. > x_ /; x > #2 :> x - 1, #2}, {#1, #2 + 1}] &, #] &, {s, 1}, Last[#] < > Max[First[#]] &]] > > I did not bother eliminating Last and First in the test function but it > can of course done in the same way. > But the main point was quite different. First, there is an almost > countless number of ways to program this sort of thing in Mathematica > and if other participants in the MathGroup get interested in this > question you will see lots of very different solutions, some of which > will no doubt be faster and more elegant than the one I came up with > (though your formulation of your question in terms of Lisp will > probably discourage some). > Secondly, while it is possible to program recursively in Mathematic it > is not in general the best way, which I am sure you will find out for > yourself if you continue doing so... > > Andrzej > > > > > On 4 May 2005, at 23:08, Daniel Roy wrote: > >> >> Thought you'd be interested to know that if I simply replace my >> First[Position[...]] test with your FreeQ test then the performance of >> our different versions match each other. First[Position is slow and >> this makes sense as FreeQ can stop immediately upon finding a match >> while First[Position enumerates all matches and therefore takes time >> linear in the length of the sequence (while FreeQ's runtime is also >> linear but on the average case depends probabilistically on the length >> of the sequence, query number and the distribution of numbers in the >> list... my guess is that its sub-linear on average) >> >> Here is the version simply replacing First[Position with FreeQ and some >> timing results using 10,000,000 entries. >> >> CompressNumericalSequence[S_] := Module[ >> {C = Function[{C, R, i}, >> If[i < Max[R], >> If[FreeQ[R, i], >> C[C, (If[# > i, # - 1, #]) & /@ R, i], >> C[C, R, i + 1]], >> R]]}, >> C[C, S, 1]]; >> >> ...(using 10^7 test entries)... >> >> ans1=CompressNumericalSequence1[test];//Timing >> ans2=CompressNumericalSequence[test];//Timing >> ans1 == ans2 >> >> {29.4135 Second,Null} >> {29.3635 Second,Null} >> True >> >> The remaining difference is how we transform 'a' (or R in my case). It >> appears that your (a /. x ......) rule is about as fast as mine as >> replacing them results in no statistically significant difference in >> timing. >> >> There are two things that bug me. 1) Your version requires these >> First[#] and Last[#] constructs in order to grab the parameters. To >> me, >> this is not only asthetically disastisfying, but, more practically, >> hard >> to maintain/reason about with more and more parameters. Yes, you can >> use a With like you have, but this sort of construct should be built >> into the language. Can you extend the language in such a way? Second, >> my version, while it has variable names and scoping, requires that I >> pass in a copy of itself which seems unreasonable. >> >> The issue is that the variables being defined in a scope like a >> With/Module are not available to each other before the "body". So >> With/Module is more like "let" then "letrec." Here is a version that >> does away with passing itself but I had to move the function definition >> into the body in order to accomplish this (this version ran in about >> the >> same time as the above version). >> >> CompressNumericalSequence[S_] := Module[ >> {C}, >> C = Function[{R, i}, >> If[i < Max[R], >> If[FreeQ[R, i], >> C[R /. x_ /; x > i :> x - 1, i], >> C[R, i + 1]], >> R]]; >> C[S, 1]]; >> >> I suppose this is how I would write it in the future as I don't like >> the >> First/Last aspect of the NestWhile. >> >> thoughts? >> >> dan >> >> >> >> >>> Unfortunately I am out of practice with Lisp. Let, I think, >>> corresponds >>> to Mathematica's With. I don't think there is anything that >>> corresponds >>> to named let or letrec but they are not needed. The reason is that >>> the similarity between Mathematica and Lisp is very deceptive. >>> Mathematica's syntax, or more correctly one part of its syntax does >>> indeed resemble Lisp but the "internals" of the two languages are >>> quite >>> different. (The most important difference is that Mathematica's lists >>> are arrays and Lisp style linked lists have to be explicitly formed >>> and >>> are not very easy to use.) You can program (with some effort) in >>> Mathematica in Lisp style just as you can program in C style, but if >>> you do so your programs will usually be not very efficient and in some >>> cases unmanageably inefficient. I know because many years ago when I >>> started to program in Mathematica I also attempted to program in Lisp >>> style. >>> Actually your program CompressNumericalSequence performs better than I >>> would have expected but almost any program written in a more natural >>> Mathematica style will outperform it. Here is a very casual attempt: >>> >>> CompressNumericalSequence1[s_] := First[NestWhile[With[{a = First[#], >>> b >>> = >>> Last[#]}, If[FreeQ[a, b], {a /. x_ /; >>> x > b :> x - 1, b}, {a, b + 1}]] &, {s, 1}, Last[#] < >>> Max[First[#]] &]] >>> >>> test=Table[Random[Integer,20],{10^6}]; >>> >>> >>> ans1=CompressNumericalSequence1[test];//Timing >>> >>> >>> {3.84 Second,Null} >>> >>> >>> ans2=CompressNumericalSequence[test];//Timing >>> >>> >>> {11.66 Second,Null} >>> >>> In[6]:= >>> ans1==ans2 >>> >>> True >>> >>> >>> Andrzej Kozlowski >>> Chiba, Japan >>> http://www.akikoz.net/andrzej/index.html >>> http://www.mimuw.edu.pl/~akoz/ >>> >> > > > > -- DrBob at bigfoot.com
- References:
- letrec/named let
- From: Daniel Roy <droy@mit.edu>
- Re: letrec/named let
- From: Andrzej Kozlowski <akoz@mimuw.edu.pl>
- letrec/named let