MathGroup Archive 2005

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

Search the Archive

Re: letrec/named let

  • To: mathgroup at smc.vnet.net
  • Subject: [mg56830] Re: letrec/named let
  • From: "Carl K. Woll" <carl at woll2woll.com>
  • Date: Sat, 7 May 2005 04:16:44 -0400 (EDT)
  • References: <069a01c55260$afdad760$6400a8c0@Main> <opsqc8fk0aiz9bcq@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: [mg56830] 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
>
> 



  • Prev by Date: Re: managing order of magnitude instead of numbers
  • Next by Date: Re: letrec/named let
  • Previous by thread: Re: letrec/named let
  • Next by thread: Re: letrec/named let