Re: letrec/named let
- To: mathgroup at smc.vnet.net
- Subject: [mg56838] Re: letrec/named let
- From: DrBob <drbob at bigfoot.com>
- Date: Sat, 7 May 2005 04:17:00 -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>
- Reply-to: drbob at bigfoot.com
- Sender: owner-wri-mathgroup at wolfram.com
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
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: [mg56838] 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"
>>> <mathgroup at smc.vnet.net>
>>> Sent: Friday, May 06, 2005 2:03 PM
>>> Subject: [mg56838] 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