Re: letrec/named let
- To: mathgroup at smc.vnet.net
- Subject: [mg56839] Re: letrec/named let
- From: "Carl K. Woll" <carl at woll2woll.com>
- Date: Sat, 7 May 2005 04:17:02 -0400 (EDT)
- References: <069a01c55260$afdad760$6400a8c0@Main> <opsqc8fk0aiz9bcq@monster.ma.dl.cox.net> <06cb01c55267$3a6b5930$6400a8c0@Main> <opsqdiiiixiz9bcq@monster.ma.dl.cox.net> <083a01c5528e$c7e11da0$6400a8c0@Main> <opsqdmxkhmiz9bcq@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
<mathgroup at smc.vnet.net>
Subject: [mg56839] Re: letrec/named let
>I was assuming nothing in your code would be slower in the newest version,
>so I was hoping to identify a component that had gotten faster from version
>to version in MY code. Perhaps Union is 12 times faster in 5.1.1, for
>instance.
>
> Either way, as I said before, we need timings on both machines to narrow
> it down.
>
> Nevertheless, here are timings for statements in "carl":
>
> carlTimed[s_]:=Module[{ord,t,ans},
> Print@Timing[ord=Ordering@s;Ordering];
>
> Print@Timing[t=FoldList[Plus,1,Sign[Abs[ListCorrelate[{1,-1},s[[ord]]]]]];
> FoldList];
> Print@Timing[ans=t[[Ordering[ord]]];Part]]
>
> data=1+RandomArray[PoissonDistribution[2],{10^6}];
> Timing[three=carlTimed@data;]
>
> {0.813 Second,Ordering}
> {0.281 Second,FoldList}
> {0.641 Second,Part}
> {1.735 Second,Null}
>
> data=Table[Random[],{10^6}];
> Timing[three=carlTimed@data;]
>
> {8.031 Second,Ordering}
> {0.391 Second,FoldList}
> {7.281 Second,Part}
> {15.906 Second,Null}
>
> Bobby
>
And so we discover that when data is a list of a million reals, Union[data]
now takes 0.626 seconds, while Ordering[data] takes 8.031 seconds. On my
machine Union[data] takes 1.2 seconds and Ordering[data] takes 1.1 seconds.
I think we've found the bottleneck. Ordering is no longer a very fast
function, at least when it's argument is a list of reals.
Carl Woll
> On Fri, 6 May 2005 18:56:03 -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" <carl at woll2woll.com>; "Carl K. Woll"
>> Sent: Friday, May 06, 2005 5:40 PM
>> Subject: [mg56839] 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: [mg56839] 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
>>>
>>>
>>
>>
>>
>>
>>
>
>
>
> --
> DrBob at bigfoot.com
>
>