MathGroup Archive 1998

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

Search the Archive

Re: Re: Split in Mathematica 2.2

At 1:26 AM -0700 6/13/98, Xah Lee wrote:
>Here are some more constructs that emulate Split. Note that the argument to
>Split need not have head List.
>(*best. Fastest too. Modified from Andrzej Kozlowski's code.*)
>  Module[{h=(Head at li)},
>    h@@((Take[li,#1]&)/@(
>              Transpose[{Flatten[{1,#1+1}],Flatten[{#1,Length at li}]}]&)@(
>                Position[#,h[a_,b_]/;Not at fQ[a,b],{1}]&)@Partition[li,2,1])];
>(*same idea, but written procedurally.*)
>split2[li_,fQ_:SameQ]:=Module[{liLength,index,i},liLength=Length at li;
>      If[Not@(fQ@@Part[li,{i,i+1}]),index={index,i}]];
>(Head at li)@@((
>            Take[li,#]&)/@(
>              Transpose[{Flatten[{1,#+1}],Flatten[{#,liLength}]}]&)@index)];
>(*using the idea of recursive pattern matching. Slow and memory intensive,
>as expected. Can anyone come up with a faster version with this approach? *)
>split3[li_,fQ_:SameQ]:=Module[{h=Head at li,g,hTemp},
>g[frest___,a_,b_,rest___]/;Not at fQ[a,b]:=hTemp[g[frest,a],g[b,rest]];
>		g[a__]:=h[a];
>		Flatten[h[g@@li],Infinity,hTemp]];
>(* another potential variety is Andrzej Kozlowski's original code using
>Fold. I havn't studied it. It may be the most elegant.*)
> testing
>li=h at Table[h@Random[Integer,{1,3}],{300}];
>result=(Timing at #[li]&)/@{Split,split,split2,split3};
>First at Transpose@result
>SameQ@@(Last at Transpose@result)
>{0.0166667 Second,0.116667 Second,0.266667 Second,0.516667 Second}
> Xah, xah at
> "Tumor growth and variations: Unix C C++ Java sed awk sh csh Perl"

My own tests show that that Carl Woll's version:

split4[li_,testQ_:SameQ] := Module[{r1,r2},

is not only the fastest that has been produced in this thread but that
it also quite clearly beats the built-in Split in Mathematica 3.0, at
least on my G3 Mac. In fact, even the best result mentioned in Xah
Lee's messgae usually beats the built-in Split for large lists. This
seems to me a pretty remarkable achievement. We are always told (in
books on Mathematica programming) that we should use built-in functions
as thay are the fastest. It doesn't seem to be true in this case! Or is
this only true on a G3 Mac? Has anyone ever heard of any other such
examples (built-inn funnctions being slower than user programmed ones)?

Here are my results:

w = Table[Random[Integer], {100000}];

{5.41667 Second,Null}
{6.31667 Second,Null}
{7. Second,Null}

(Split is the built-in function.)
Andrzej Kozlowski

  • Prev by Date: RE: Dynamic Programming
  • Next by Date: RE: Position on a List
  • Previous by thread: Re: Split in Mathematica 2.2
  • Next by thread: Re: Re: Split in Mathematica 2.2