MathGroup Archive 2005

[Date Index] [Thread Index] [Author Index]

Search the Archive

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/
>>
>


  • Prev by Date: Re: Re: debugging
  • Next by Date: New Article : ShadowPlot3D
  • Previous by thread: Re: letrec/named let
  • Next by thread: Re: Re: letrec/named let