Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2005
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2005

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

Search the Archive

Re: letrec/named let

  • To: mathgroup at smc.vnet.net
  • Subject: [mg56835] Re: letrec/named let
  • From: DrBob <drbob at bigfoot.com>
  • Date: Sat, 7 May 2005 04:16:56 -0400 (EDT)
  • References: <069a01c55260$afdad760$6400a8c0@Main> <opsqc8fk0aiz9bcq@monster.ma.dl.cox.net> <06cb01c55267$3a6b5930$6400a8c0@Main>
  • Reply-to: drbob at bigfoot.com
  • Sender: owner-wri-mathgroup at wolfram.com

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

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: [mg56835] 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


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