MathGroup Archive 2005

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

Search the Archive

Re: Re: Re: Timing runs for the last part of my previouspost

  • To: mathgroup at smc.vnet.net
  • Subject: [mg62214] Re: [mg62196] Re: Re: Timing runs for the last part of my previouspost
  • From: Maxim <m.r at inbox.ru>
  • Date: Tue, 15 Nov 2005 04:16:13 -0500 (EST)
  • Reply-to: Maxim <m.r at inbox.ru>
  • Sender: owner-wri-mathgroup at wolfram.com

-----Original Message-----
From: "Carl K. Woll" <carl at woll2woll.com>
To: mathgroup at smc.vnet.net
Subject: [mg62214] Re: [mg62196] Re:   Re: Timing runs for the last part of my previouspost

> 
> Maxim wrote:
> > On Fri, 11 Nov 2005 08:09:15 +0000 (UTC), Oyvind Tafjord  
> > <tafjord at wolfram.com> wrote:
> > 
> > 
> >>Here's yet another way which is about 30% faster then testFunc4:
> >>
> >>Pick[values, Plus @@ Sign[#] & /@ values, -2]
> >>
> >>At some point you'll need to process all pairs in the list, so it's  
> >>faster
> >>to do this up front, in an effective way, and then use Pick to get the
> >>elements you want.
> >>
> >>Oyvind Tafjord
> >>Wolfram Research
> >>
> >>
> > 
> > 
> > An even more efficient (and contrived) way is to make all the loops over  
> > the list elements implicit:
> > 
> > In[1]:=
> > L = Array[Random[Integer, {-10, 10}]&, {10^6, 2}];
> > Cases[L, {_?Negative, _?Negative}]; // Timing
> > Pick[L, Plus@@ Sign@ #& /@ L, -2]; // Timing
> > Pick[L, Total@ Transpose@ Sign@ L, -2]; // Timing
> > 
> > Out[2]= {1.563*Second, Null}
> > 
> > Out[3]= {1.062*Second, Null}
> > 
> > Out[4]= {0.468*Second, Null}
> > 
> > The second version uses Map, which is fairly efficient but still not as  
> > good as applying listable functions to vectors.
> > 
> > Maxim Rytin
> > m.r at inbox.ru
> 
> It is possible to use SparseArrays to speed this up even further. First 
> convert the original list into a vector of 1s and 0s, where the 1s 
> indicate where a pair of negatives were. Then convert to SparseArrays 
> and extract the position of the nonzero elements:
> 
> In[15]:=
> r1=L[[SparseArray[
>         1-Sign[Total[Transpose[1+Sign[L]]]]
>        ]/.SparseArray[_,_,_,{_,{_,x_},_}]:>Flatten[x]]];//Timing
> r2=Pick[L,Total@Transpose@Sign@L,-2];//Timing
> r1===r2
> 
> Out[15]=
> {0.188 Second,Null}
> 
> Out[16]=
> {1.516 Second,Null}
> 
> Out[17]=
> True
> 
> Carl Woll
> Wolfram Research
> 

It is slightly faster to use Clip:

In[1]:=
L = Array[Random[Integer, {-10, 10}]&, {10^7, 2}];
L[[SparseArray[1 - Sign[Total[Transpose[1 + Sign[L]]]]] /.
  SparseArray[_, _, _, {_, {_, x_}, _}] :> Flatten[x]]]; // Timing
SparseArray@ Clip[Total@ Transpose@ Sign@ L, {-2, -2}, {0, 0}] //
  Block[{SparseArray = List}, L[[Flatten@ #[[4, 2, 2]]]]]&; // Timing

Out[2]= {1.172*Second, Null}

Out[3]= {0.703*Second, Null}

Another consideration is the amount of memory required. Straightforward compiled code may be preferable, as it will need only 2*ByteCount[L] bytes, and SparseArray together with Sign or Clip use 3*ByteCount[L] bytes.

Maxim Rytin
m.r at inbox.ru


  • Prev by Date: Solved:Re: Defining variables in $UserBaseDirectory/init.m
  • Next by Date: Re: Re: Types in Mathematica
  • Previous by thread: Solved:Re: Defining variables in $UserBaseDirectory/init.m
  • Next by thread: FixedPoint