Re: Split on the Macintosh
- To: mathgroup at smc.vnet.net
- Subject: [mg18409] Re: Split on the Macintosh
- From: "Carl K.Woll" <carlw at fermi.phys.washington.edu>
- Date: Wed, 7 Jul 1999 00:11:06 -0400
- Organization: Department of Physics
- References: <19990701013503.003579@smtp.bekkoame.ne.jp>
- Sender: owner-wri-mathgroup at wolfram.com
Hi Andrzej,
Apparently I never sent you a slight improvement (20% faster on my machine) of
the split function. Simply use the optional fourth argument of Partition:
split2[li_,testQ_:SameQ]:=Module[{r1, r2},
r1 = Flatten[Position[Partition[li, 2, 1,testQ], False]];
r2 = Transpose[{Join[{1}, r1 + 1], Join[r1, {Length[li]}]}];
Take[li, #] & /@ r2]
If Split is still quadratic on the Mac, then the above improvement may be more
than academic (although, of course, you are an academic, right?).
By the way, I'm jealous. Since I'm a poor student, I will have to wait until
August to get the new version.
Carl Woll
Physics Dept
U of Washington
Andrzej Kozlowski wrote:
> Today at last I got my Mathematica 4.0 upgrade, much earlier than I ever
> expected. I am very grateful to the mathgroup whose very existence has
> undoubtedly contributed to this, from my point of view, remarkable and
> happy event.
>
> The very first thing I did after installing Mathematica 4 was to go over my own
> personal list of bugs and problems that plagued the previous version to
> check which have and which have not been fixed. I am very pleased to be
> able to say that the first group is far larger (if one excludes functions
> contained in various packages, which appear to have not been changed at
> all. Particularly, given the improved performance of the built-in Limit
> function, it seems to me that one should now generally avoid the
> Calculus`Limit` package more then ever).
>
> However, the problem that I was most curious about still persists. It was
> something discovered about a year ago by Xah Lee, Carl Woll and myself
> and concerns the Split function. At that time I wanted to emulate it in
> mathematica 2.2 and we produced various candidates and compared their
> efficiency. Then we discovered a curious thing. Our best attempt was the
> following function:
>
> split2[li_, testQ_:SameQ] :=
> Module[{r1, r2},
> r1 = Flatten[Position[Apply[testQ, Partition[li, 2, 1], {1}], False]];
> r2 = Transpose[{Join[{1}, r1 + 1], Join[r1, {Length[li]}]}];
> Take[li, #] & /@ r2]
>
> We found that on the Macintosh alone (strictly speaking we only tested
> PPC Macs) this function is more efficient than the built in Split for
> very large lists. Not only that, its lead over Split grows with the size
> of the list. This is not true on other platforms where the built-in Split
> is much faster. Moreover, careful investigation revealed that on the Mac
> the built in Split function does not scale linearly but seems to have a
> non-negligible quadratic component, while split2 is linear. On other
> platforms, however, Split scales linearly.
>
> This is strange. One reason is that the Kernel is supposed to work the
> same way on all platforms so one would imagine that basic things as
> asymptotic growth of functions would be roughly the same. Moreover, the
> algorithms used certainly scale linearly: after all if we were able to
> produce a linear function that one would certainly expect wri to be able
> to do so.
>
> Xah Lee reported this problem to wri's techincal support. So I was
> curious to see if there would be any change in this respect in version 4.
>
> I have just run my tests and found that while Split has become
> considerably faster in version 4, it still shows non-linear asymptotic
> behaviour and is still beaten by split2 for v. large lists. Those who
> would like to see these results (valid only on the Mac) can download the
> notebook:
> <ftp://cleo.tuins.ac.jp//pub/Splitvsplit.nb>
>
> The most likely explanation seems to be that this might be something to
> do with the memory management of the Mac. Yet it is strange that it seems
> to affect only just one function, and that wri have not been able to do
> anything about it. This is not necessarily a trivial matter because it is
> precisely when dealing with very large lists that Split becomes very
> useful. Another thing that it illustrates (in my opinion) is the
> difficulties in applying purely theoretical efficiency arguments in the
> case of a program like Mathematica in which built in function splay such
> a big role.
>
> Andrzej Kozlowski
>
> Toyama International University
> JAPAN
> http://sigma.tuins.ac.jp/
> http://eri2.tuins.ac.jp/