Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: letrec/named let

• To: mathgroup at smc.vnet.net
• Subject: [mg56848] Re: letrec/named let
• From: Bill Rowe <readnewsciv at earthlink.net>
• Date: Sat, 7 May 2005 15:35:09 -0400 (EDT)
• Sender: owner-wri-mathgroup at wolfram.com

On 5/7/05 at 4:17 AM, drbob at bigfoot.com (DrBob) wrote:

>Indeed, for real data, your substitute for ordering is much faster
>(in 5.1.1) than the built-in. If it's 2.5 times SLOWER on your
>machine, that does seem to imply WRI has radically DECREASED
>Ordering's performance from 4.1 to 5.1.1.
>
>It's hard to believe they'd do that, but apparently they have.
>
>>The only possibility I can think of is that ord=Ordering[data]
>>returns a packed array of integers when data is integer, while
>>ord=Ordering[data] returns an unpacked array of integers when data
>>is real.
>
>Exactly right. See below. Maybe this explains the performance issue
>for Ordering itself, too.
>
>(Note: 'data' is packed in both tests.)
>
>pq = Developer`PackedArrayQ; carlTimed[s_] := Module[{ord, t, o,
>ans},
>Print@Timing[ord = Ordering@s; Ordering]; Print@Timing[t =
>FoldList[ Plus, 1, Sign[Abs[ListCorrelate[{1, -1}, s[[ord]]]]]];
>FoldList]; Print@Timing[o = Ordering@ord; Ordering];
>Print@Timing[ans = t[[o]]; Part]; Print[pq /@ {ord, t, o, ans}];
>ans]
>ordering[x_List] := Round@Sort[Transpose[{x,
>N@Range@Length@x}]][[All, 2]] carlNewOrder[s_] := Module[{ord, t,
>o, ans},
>Print@Timing[ord = ordering@s; ordering]; Print@Timing[ t =
>FoldList[Plus, 1, Sign[Abs[ListCorrelate[{1, -1}, s[[ord]]]]]];
>FoldList]; Print@Timing[o = ordering@ord; ordering];
>Print@Timing[ans = t[[o]]; Part]; Print[pq /@ {ord, t, o, ans}];
>ans]
>
>data = Table[Random[], {10^6}]; Timing[carlTimed@data; Total]
>Timing[carlNewOrder@data; Total]
>
>{8. Second,Ordering} {0.391 Second,FoldList} {7.25 Second,Ordering}
>{0.063 Second,Part} {False,True,True,True} {15.891 Second,Total}
>
>{1.063 Second,ordering} {0.343 Second,FoldList} {7.36
>Second,ordering} {0.062 Second,Part} {True,True,True,True} {8.828
>Second,Total}
>
>Notice ordering returned a packed array (ord) for real data, but
>Ordering didn't. Also notice the second use (with Integer data) has
>Ordering and ordering equally fast, but that's despite ordering
>being applied to a packed integer array, but Ordering applied to an
>unpacked array.

Interesting. These results seem very dependent on platform. Specifically, when I run the code above I get.

In[5]:=
data = Table[Random[], {10^6}]; 
Timing[carlTimed[data]; Total]
Timing[carlNewOrder[data]; Total]

{1.478287*Second, Ordering}
{1.596432*Second, FoldList}
{1.215809*Second, Ordering}
{0.262963*Second, Part}
{True, True, True, True}
{4.568661*Second, Total}

{3.336485*Second, ordering}
{1.603586*Second, FoldList}
{18.20541*Second, ordering}
{0.266754*Second, Part}
{True, True, True, True}
{23.426852*Second, Total}

In[8]:=
$Version
Out[8]=
"5.1 for Mac OS X (January 27, 2005)"

As you can see on my machine, both Ordering and ordering return packed arrays. And when I compare timings of Carl's solution to yours I get results consistent with what Carl reported, i.e., his solution runs about 5 times faster.
--
To reply via email subtract one hundred and four

• Follow-Ups:
  • Re: Re: letrec/named let
    • From: DrBob <drbob@bigfoot.com>
  • Re: Re: letrec/named let
    • From: Andrzej Kozlowski <akoz@mimuw.edu.pl>