prograMing: split a list

*To*: mathgroup at smc.vnet.net*Subject*: [mg8843] prograMing: split a list*From*: "Xah" <xah at best.com>*Date*: Mon, 29 Sep 1997 02:40:11 -0400*Organization*: smtp.best.com*Sender*: owner-wri-mathgroup at wolfram.com

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. Xah xah at best.com http://www.best.com/~xah/SpecialPlaneCurves_dir/specialPlaneCurves.html Mountain View, CA, USA