Re: letrec/named let
- To: mathgroup at smc.vnet.net
- Subject: [mg56752] Re: [mg56707] letrec/named let
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Thu, 5 May 2005 06:01:33 -0400 (EDT)
- References: <200505040433.AAA06220@smc.vnet.net> <6bd33c74358661121c5a59d79fcccad0@mimuw.edu.pl> <1115215689.31793.86.camel@30-5-214.wireless.csail.mit.edu>
- Sender: owner-wri-mathgroup at wolfram.com
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/
>>
>
- Follow-Ups:
- Re: Re: letrec/named let
- From: DrBob <drbob@bigfoot.com>
- Re: Re: letrec/named let
- References:
- letrec/named let
- From: Daniel Roy <droy@mit.edu>
- letrec/named let