Re: letrec/named let
- To: mathgroup at smc.vnet.net
- Subject: [mg56836] Re: letrec/named let
- From: "Carl K. Woll" <carl at woll2woll.com>
- Date: Sat, 7 May 2005 04:16:57 -0400 (EDT)
- References: <069a01c55260$afdad760$6400a8c0@Main> <opsqc8fk0aiz9bcq@monster.ma.dl.cox.net> <06cb01c55267$3a6b5930$6400a8c0@Main> <opsqdiiiixiz9bcq@monster.ma.dl.cox.net>
- Sender: owner-wri-mathgroup at wolfram.com
----- Original Message -----
From: "DrBob" <drbob at bigfoot.com>
To: mathgroup at smc.vnet.net
Subject: [mg56836] Re: letrec/named let
> I'm guessing Union, ReplaceAll, Dispatch, and/or Thread are better
> optimized in version 5.1.1. We'd have to get relative times for various
> statements on BOTH our machines, to narrow it down. Here they are for my
> machine:
>
> treat2[s_List] := Module[{u, t, d, ans},
> Print@Timing[u = Union@s; "Union"];
> Print@Timing[t = Thread[u -> Range@Length@u]; "Thread"];
> Print@Timing[d = Dispatch@t; "Dispatch"];
> Print@Timing[ans = s /. d; "ReplaceAll"];
> ans]
>
> data=1+RandomArray[PoissonDistribution[2],{10^6}];
> Timing[treat2@data;]
>
> {0.265 Second,Union}
> {0. Second,Thread}
> {0. Second,Dispatch}
> {0.297 Second,ReplaceAll}
> {0.562 Second,Null}
>
> data=Table[Random[],{10^6}];
> Timing[treat2@data;]
>
> {0.625 Second,Union}
> {2.922 Second,Thread}
> {1.625 Second,Dispatch}
> {3.89 Second,ReplaceAll}
> {10.328 Second,Null}
>
> If your machine has Dispatch (for instance) taking a larger fraction of
> the total time, we'll have a clue to what changed.
>
> I'm actually shocked by how fast this is, considering the relatively naive
> (IMO) method involved.
>
> Bobby
>
I'm not surprised by the timings you give for treat. I'm surprised by your
timing for my function, carl. On my machine, applying my function to a
million reals takes about 2 times as long as a Union. On your machine, it
apparently takes about 24 times as long as a Union. The 1st and 3rd lines of
my function are basically sorting operations, so the bottleneck on your
machine must be the 2nd line. However, on my machine, the 2nd line is the
fastest operation. The only candidates for a bottleneck seem to be FoldList
and ListCorrelate, or perhaps something funny is going on with packed
arrays. I'd be curious what timings my function would get if you "treat"ed
it like treat2 <grin>.
Carl Woll
> On Fri, 6 May 2005 14:12:55 -0400, Carl K. Woll <carl at woll2woll.com>
> wrote:
>
>> ----- Original Message -----
>> From: "DrBob" <drbob at bigfoot.com>
To: mathgroup at smc.vnet.net
>> To: "Carl K. Woll" <carlw at u.washington.edu>; "MathGroup"
>> Sent: Friday, May 06, 2005 2:03 PM
>> Subject: [mg56836] Re: letrec/named let
>>
>>
>>> That's a very nice "rescue" of the Ordering@Ordering solution.
>>>
>>> Here's a test with (probably) no repeated elements, however, that shows
>>> treat ahead. Perhaps there's an intermediate situation where carl wins,
>>> or
>>> it matters whether the data is integer or real?
>>>
>>> data=Table[Random[],{10^6}];
>>> Timing[one=treat@data;]
>>> Timing[three=carl@data;]
>>> one==three
>>>
>>> {10.109 Second,Null}
>>> {15.938 Second,Null}
>>> True
>>>
>>
>> Interesting. On my machine, carl is over 5 times faster than treat for
>> the
>> same test. I have version 4.1 on a Windows XP operating system. What is
>> your
>> setup? Perhaps you could test each individual line of carl to see where
>> the
>> bottleneck is.
>>
>> Carl Woll
>>
>>> Bobby
>>>
>>> On Fri, 6 May 2005 13:26:03 -0400, Carl K. Woll <carlw at u.washington.edu>
>>> wrote:
>>>
>>>> "DrBob" <drbob at bigfoot.com> wrote in message
>>>> news:d5f5ka$6dn$1 at smc.vnet.net...
>>>>> 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
>>>>>
>>>>
>>>> [snip]
>>>>
>>>> Another possibility modeled after DrBob's first answer is the
>>>> following:
>>>>
>>>> carl[s_] := Module[{ord,t},
>>>> ord = Ordering[s];
>>>> t = FoldList[Plus, 1, Sign[Abs[ListCorrelate[{1, -1}, s[[ord]]]]]];
>>>> t[[Ordering[ord]]]
>>>> ]
>>>>
>>>> If there are a lot of repeated elements in the data, then treat seems
>>>> to
>>>> be
>>>> faster. On the other hand, if there aren't a lot of repeated elements,
>>>> then
>>>> carl seems to be faster. It seems like it ought to be possible to
>>>> compute
>>>> Ordering[Ordering[data]] more quickly since
>>>> Ordering[Ordering[Ordering[data]]] equals Ordering[data], but I
>>>> couldn't
>>>> think of a way.
>>>>
>>>> Carl Woll
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>
>>>
>>>
>>> --
>>> DrBob at bigfoot.com
>>>
>>>
>>
>>
>>
>>
>>
>
>
>
> --
> DrBob at bigfoot.com
>
>