Services & ResourcesWolfram ForumsMathGroup Archive

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

RE: split a list

• To: mathgroup at smc.vnet.net
• Subject: [mg40557] RE: [mg40515] split a list
• From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com>
• Date: Thu, 10 Apr 2003 03:37:08 -0400 (EDT)
• Sender: owner-wri-mathgroup at wolfram.com

>-----Original Message-----
>From: Roberto Brambilla [mailto:rlbrambilla at cesi.it]
To: mathgroup at smc.vnet.net
>Sent: Wednesday, April 09, 2003 7:31 AM
>To: mathgroup at smc.vnet.net
>Subject: [mg40557] [mg40515] split a list
>
[...]

>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
>
[...]


Roberto,

observe

In[8]:= r = Table[Random[], {10000}];
In[9]:= m = .5;

In[10]:= 
u = v = {};
For[i = 1, i <= Length[r], i++, tmp = r[[i]];
    If[tmp > m, AppendTo[u, tmp], AppendTo[v, tmp]]] // Timing

Out[11]= {8.583 Second, Null}

In[12]:= Length /@ {u, v}
Out[12]= {4981, 5019}

In[13]:=
({u, v} = Through[{Cases, DeleteCases}[r, e_ /; e > m]]); // Timing
Out[13]= {0.51 Second, Null}

In[14]:= Length /@ {u, v}
Out[14]= {4981, 5019}


What is even more problematic with your program is its time complexity which
is O[n^2].  Such I would not like to wait for:

In[19]:= r = Table[Random[], {100000}];

In[20]:=
u = v = {};
For[i = 1, i <= Length[r], i++, tmp = r[[i]];
    If[tmp > m, AppendTo[u, tmp], AppendTo[v, tmp]]] // Timing

Out[21]= $Aborted



In[22]:=
({u, v} = Through[{Cases, DeleteCases}[r, e_ /; e > m]]); // Timing
Out[22]= {5.037 Second, Null}

In[23]:= Length /@ {u, v}
Out[23]= {50129, 49871}


Select is even a bit faster for this benchmark:

In[24]:= 
({u, v} = Select[r, #] & /@ {# > m &, # <= m &}); // Timing
Out[24]= {3.796 Second, Null}

In[25]:= Length /@ {u, v}
Out[25]= {50129, 49871}


You may however fix up (make O[n]) your "old-fashioned" algorithm:

In[33]:=
(u = v = {};
For[i = 1, i <= Length[r], i++,
        If[(tmp = r[[i]]) > m, u = {u, tmp}, v = {v, tmp}]];
      {u, v} = Flatten /@ {u, v}); // Timing

Out[33]= {6.71 Second, Null}

In[34]:= Length /@ {u, v}
Out[34]= {50129, 49871}


Another idea would be to compile:

In[57]:=
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}]];

In[58]:= ({uu, vv} = cutList[r, .5]); // Timing
Out[58]= {0.57 Second, Null}

In[59]:= {xj, xk}
Out[59]= {50129, 49871}


In[62]:= {u, v} = {Take[uu, xj], Take[vv, xk]}; // Timing
Out[62]= {0.05 Second, Null}
In[63]:= Length /@ {u, v}
Out[63]= {50129, 49871}

This is by far the best timing. Regard how I transferred the result u and v
as a tensor objekt, but the effective resulting Lengths via global
variables!


--
Hartmut Wolf

• Follow-Ups:
  • Re: RE: split a list
    • From: Dr Bob <majort@cox-internet.com>
  • Re: RE: split a list
    • From: Dr Bob <majort@cox-internet.com>