Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Re: split a list

• To: mathgroup at smc.vnet.net
• Subject: [mg40660] Re: [mg40621] Re: split a list
• From: Dr Bob <majort at cox-internet.com>
• Date: Sat, 12 Apr 2003 03:11:56 -0400 (EDT)
• References: <b70boj$883$1@smc.vnet.net> <200304110603.CAA02004@smc.vnet.net>
• Reply-to: majort at cox-internet.com
• Sender: owner-wri-mathgroup at wolfram.com

Your "split2" wins the day -- both fast and simple.

lower = Compile[{{r, _Real, 1}, {m, _Real, 0}}, Select[r, # < m &]];
upper = Compile[{{r, _Real, 1}, {m, _Real, 0}}, Select[r, # â?¥ m &]];
woll[r_, m_] := {lower[r, m], upper[r, m]}

cutList = Compile[{{
  r, _Real, 1}, {m, _Real}}, Module[{tmp, u, v, i, j = 0, k = 0}, u = v = 
Table[0., {Length[r]}];
      For[i = 1, i â?¤ Length[r], ++i, If[(tmp = r[[
      i]]) > m, u[[++j]] = tmp, v[[++k]] = tmp]];
      xj = j; xk = k;
      {u, v}]];
hartmut = Block[{u, v, xj, xk},
      {u, v} = cutList[#1, #2];
      {Take[v, xk], Take[u, xj]}
      ] &;

test = trial@500000;
Timing[treat @@ test;]
Timing[woll @@ test;]
Timing[hartmut @@ test;]
Timing[treat3 @@ test;]

{4.547 Second,Null}
{0.719 Second,Null}
{0.953 Second,Null}
{4.312 Second,Null}

test = trial@1500000;
Timing[treat @@ test;]
Timing[woll @@ test;]
Timing[hartmut @@ test;]
Timing[treat3 @@ test;]

{13.062 Second,Null}
{2.187 Second,Null}
{2.344 Second,Null}
{12.844 Second,Null}

test = trial@2000000;
Timing[treat @@ test;]
Timing[woll @@ test;]
Timing[hartmut @@ test;]
Timing[treat3 @@ test;]

{17. Second,Null}
{2.687 Second,Null}
{3.36 Second,Null}
{16.687 Second,Null}

Bobby

On Fri, 11 Apr 2003 02:03:19 -0400 (EDT), Carl K. Woll 
<carlw at u.washington.edu> wrote:

> Hi all,
>
> Just thought I would throw a couple more possibilities into the mix.
>
> First, since Select works more quickly when the test is simpler, we can 
> try
> the following:
>
> split1[r_,m_]:={Select[#,Negative],Select[#,NonNegative]}&[r-m]+m
>
> Basically, we subtract the breakpoint from the list then do Select with 
> the
> very simple tests Negative and NonNegative, then we restore the original
> list by adding back the breakpoint. In my tests this is about twice as 
> fast
> as the simpler approach:
>
> split0[r_,m_]:={Select[r, # < m &], Select[r, # >= m &]}
>
> One small problem with my approach is that the machine real numbers you 
> get
> after subtracting and adding the breakpoint can differ enough so that 
> they
> are not considered the same number by mathematica anymore. For example:
>
> In[6]:=
> data=Table[Random[],{10^6}];
> In[7]:=
> r1=split0[data,.5];//Timing
> r2=split1[data,.5];//Timing
> r1==r2
> Out[7]=
> {5.39 Second, Null}
> Out[8]=
> {2.594 Second, Null}
> Out[9]=
> False
>
> Of course, we can make an even faster function by compiling. However, 
> since
> the output is in general not a tensor, that is the two lists are in 
> general
> not equal in length, we have to be a little creative. Anyway, using 
> Compile
> we have:
>
> lower=Compile[{{r,_Real,1},{m,_Real,0}},Select[r, # < m&]];
> upper=Compile[{{r,_Real,1},{m,_Real,0}},Select[r, # >= m&]];
> split2[r_,m_]:={lower[r,m],upper[r,m]}
>
> A timing comparison yields:
>
> In[10]:=
> r1=split0[data,.5];//Timing
> r2=split2[data,.5];//Timing
> r1==r2
> Out[10]=
> {5.734 Second, Null}
> Out[11]=
> {1.594 Second, Null}
> Out[12]=
> True
>
> The compiled version is quite a bit faster.
>
> Carl Woll
> Physics Dept
> U of Washington
>
> "Roberto Brambilla" <rlbrambilla at cesi.it> wrote in message
> news:b70boj$883$1 at smc.vnet.net...
>> Hi,
>>
>> I have a list (very long, thousands, and unsorted) of numbers 
>> r={n1,n2...}
>> and for a given a number m  I want to split it in the two sublists
>> (unsorted, same order) u={elements<m], v={elements>m}.
>> Now I use this *old-style*  method:
>>
>> u = v = {};
>> For[i = 1, i <= Length[r], i++,
>> tmp = r[[i]];
>> If[tmp > m , AppendTo[u, tmp], AppendTo[v, tmp]];
>> ]
>>
>> Any suggestion for a more efficient (and elegant) method?
>> Also oneliners are well accepted.
>>
>> Many thanks, Roberto
>>
>> Roberto Brambilla
>> CESI
>> Via Rubattino 54
>> 20134 Milano
>> tel +39.02.2125.5875
>> fax +39.02.2125.5492
>> rlbrambilla at cesi.it
>>
>>
>
>
>
>



-- 
majort at cox-internet.com
Bobby R. Treat

• References:
  • Re: split a list
    • From: "Carl K. Woll" <carlw@u.washington.edu>