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>