Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: RE: split a list

• To: mathgroup at smc.vnet.net
• Subject: [mg40633] Re: [mg40557] RE: [mg40515] split a list
• From: Dr Bob <majort at cox-internet.com>
• Date: Fri, 11 Apr 2003 02:05:20 -0400 (EDT)
• References: <200304100737.DAA24168@smc.vnet.net>
• Reply-to: majort at cox-internet.com
• Sender: owner-wri-mathgroup at wolfram.com

That's really amazing!  It's nice that we can get the advantage of compiled 
code while still using a high level, interpreted language with symbolic 
capabilities, etc.  Mathematica rules.

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]}
        ] &;

(I had to reverse u and v to get the same answer as other solutions.)

test = trial@5000;
brambilla @@ test ==
 kuska @@ test == treat @@ test == treat3 @@ test == treat5 @@ test == 
hartmut @@ test

True

test = trial@500000;
Timing[treat @@ test;]
Timing[kuska @@ test;]
Timing[treat2 @@ test;]
Timing[treat3 @@ test;]
Timing[treat5 @@ test;]
Timing[hartmut @@ test;]

{3.75 Second,Null}
{3.938 Second,Null}
{3.703 Second,Null}
{3.765 Second,Null}
{16.672 Second,Null}
{0.516 Second,Null}

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

{15.843 Second,Null}
{15.406 Second,Null}
{15.657 Second,Null}
{2.61 Second,Null}
{16.797 Second,Null}
{16. Second,Null}

Bobby

Display all headersDate: Thu, 10 Apr 2003 03:37:08 -0400 (EDT)From: "Wolf, 
To: mathgroup at smc.vnet.net
Hartmut" <Hartmut.Wolf at t-systems.com>To: mathgroup at smc.vnet.netSubject: [mg40633] 
[mg40557] RE: [mg40515] split a list

> -----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: [mg40633] [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

• References:
  • RE: split a list
    • From: "Wolf, Hartmut" <Hartmut.Wolf@t-systems.com>