MathGroup Archive 1997

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

Search the Archive

Re: prograMing: split a list

  • To: mathgroup at smc.vnet.net
  • Subject: [mg8965] Re: prograMing: split a list
  • From: "Xah" <xah at best.com>
  • Date: Mon, 6 Oct 1997 01:59:34 -0400
  • Organization: smtp.best.com
  • Sender: owner-wri-mathgroup at wolfram.com

Leszek Sczaniecki <lsczan at concentric.net> wrote:
>What about this solution?
>{Select[myList, fQ], Select[myList,!fQ]}

This solution applies fQ to each element of the list twice, so it's not
perfectly efficient. (suppose each evaluatation of fQ take 1 hour...)

Original problem and solutions are attached below. I havn't received any
replies, could it be that my solutions are nothing but nothing but the best?
(^_^)

 Xah, xah at best.com
 http://www.best.com/~xah/SpecialPlaneCurves_dir/specialPlaneCurves.html
 Quote of the day: Morality abets evil.

------------------
Xah wrote:
Another recreational prograMing problem.

I want to separate the elements in a given list myList into two groups,
depending on whether the function fQ applied to that element returns True or
False. The desired result list should have the form {{a1,a2,...},{b1,b2...}}
where the first part are elements in myList that fQ returns False.

For example, suppose myList is a list of positive integers, and fQ is OddQ.
Here are three solutions and their timing.


Clear[myList,fQ,split1,split2,split3];
myList=Table[Random[Integer,{1,200}],{1000}];
fQ=OddQ;
split1[myList_List,
    fQ_]:=({Delete[myList,#],Part[myList,Sequence@@#]&/@#}&)@(
        Position[#,_?fQ,{1}]&)@myList;
split2[myList_List,
    fQ_]:=(Last at Transpose@#&)/@(
        Split[#,(First at #1===First@#2)&]&)@(
          Sort[#,OrderedQ at {First@#1,First at #2}&]&)@((List[fQ at #,#]&)/@myList);
split3[myList_List,
    fQ_]:=({Cases[#,False[b_]->b,{1}],
          Cases[#,True[b_]->b,{1}]}&)@(((fQ[#])@#&)/@myList);

solutions={split1,split2,split3};

results=(Timing@(#[myList,fQ]))&/@solutions;

{First at #,Equal@@Last at #}&@Transpose at results

{{0.233333 Second,1.53333 Second,0.15 Second},True}

This is an easy problem with many possible approaches. What I'm looking for
is speed. Can anyone come up with a faster solution?

Note: There shouldn't be any assumption on the elements of myList and fQ may
be time consuming. The order in myList should be preserved. Also, please
avoid 3.0 funtions such as Extract.




  • Prev by Date: Re: Sequence is funny !
  • Next by Date: Re: trig expansion
  • Previous by thread: Re: prograMing: split a list
  • Next by thread: Re: prograMing: split a list