[Date Index]
[Thread Index]
[Author Index]
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**
| |