MathGroup Archive 2005

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

Search the Archive

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


  • Prev by Date: Re: Re: Re: debugging
  • Next by Date: RC circuit
  • Previous by thread: Re: letrec/named let
  • Next by thread: Re: letrec/named let