RE: Re: split a list
- To: mathgroup at smc.vnet.net
- Subject: [mg40645] RE: [mg40621] Re: split a list
- From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com>
- Date: Sat, 12 Apr 2003 03:08:21 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
>-----Original Message----- >From: Carl K. Woll [mailto:carlw at u.washington.edu] To: mathgroup at smc.vnet.net >Sent: Friday, April 11, 2003 8:03 AM >To: mathgroup at smc.vnet.net >Subject: [mg40645] [mg40621] Re: split a list > > >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 >> >> > > > Carl, very fine, as ever. You pointed to the right difficulty for compiling. I solved it in a different way: splitlist0 = Compile[{{r, _Real, 1}, {m, _Real}}, Module[{tmp, u, v, i = 0, j = 0, k = 0}, u = v = Table[0., {Length[r]}]; While[i < Length[r], If[(tmp = r[[++i]]) < m, u[[++j]] = tmp, v[[++k]] = tmp]]; xj = j; xk = k; {u, v}]]; splitlist[r_, m_] := Block[{u, v, xj, xk}, {u, v} = splitlist0[r, m]; {Take[u, xj], Take[v, xk]}] So I return a tensor, and pass the effective lengths via global variables. Such I need only a single scan of the input list r (and keep a little advantage, inspite of additional Take(s) and Table). -- Hartmut