From luke@stat.umn.edu  Fri May 29 16:45:53 1998
From: luke@stat.umn.edu (Luke Tierney)
Date: Fri, 29 May 1998 10:45:53 -0500 (CDT)
Subject: performance of apply
In-Reply-To: <6rlnrldvez.fsf@verdi.stat.wisc.edu> from "Douglas Bates" at May 29, 98 09:05:40 am
Message-ID: <9805291545.AA08154@nokomis.stat.umn.edu>

Douglas Bates wrote:
> 
> Andreas Weingessel <Andreas.Weingessel@ci.tuwien.ac.at> writes:
> > 
> > To demonstrate it, I did some benchmarking for different methods of
> > computing the row sums of an nx10 matrix with n =3D 2000, ..., 10000.
> > 
> > The first method (M1) I used is the normal apply command:
> > 	y <- apply(x,1,sum)
> > The second method (M2) uses a for-loop for the computations, where the
> > memory for the resulting vector has been allocated before. That is, for
> > n=3D2000:
> > 	z <- numeric(2000); for (i in 1:2000) z[i] <- sum(x[i,])
> > The third method (M3) also uses a for-loop, but the resulting vector
> > is built recursively, i.e.
> > 	z1 <- NULL; for (i in 1:2000) z1 <- c(z1,sum(x[i,]))
> > 
> > All computations have been made on a Pentium II 233MHz, 256MB, R
> > started as R -v 50. The following table shows the minimum, mean, and
> > maximum CPU-time in seconds as measured by system.time over 10 runs
> > for every computation for different values of n.
> > 
> > n			M1			M2		M3
> > 2000	 4.03  4.16   4.34	0.27 0.40 0.47	0.51 0.63 0.71
> > 4000	12.65 13.40  14.68	0.73 0.81 0.94	1.78 1.86 1.98
> > 6000	26.51 28.14  29.50	1.19 1.22 1.38	3.79 3.80 3.80
> > 8000	52.06 63.43  67.61	1.46 1.63 1.69	6.38 6.41 6.58
> > 10000	84.06 98.17 118.94	1.93 2.01 2.13  9.78 9.79 9.81
> > 
> > That is, the computation of the sums of the rows of a 10000x10 matrix
> > with apply takes about 100sec on average, where a simple for-loop does
> > the same job in about 2sec.

It looks like M1 and M3 are O(n^2) but M1 is O(n). I see where that
comes from in M3, but it surprises me for M1.

luke



-- 
Luke Tierney
University of Minnesota                      Phone:           612-625-7843
School of Statistics                         Fax:             612-624-8868
206 Church Street                            email:      luke@stat.umn.edu
Minneapolis, MN 55455 USA                    WWW:  http://www.stat.umn.edu
-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-
r-devel mailing list -- Read http://www.ci.tuwien.ac.at/~hornik/R/R-FAQ.html
Send "info", "help", or "[un]subscribe"
(in the "body", not the subject !)  To: r-devel-request@stat.math.ethz.ch
_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._


performance of apply
Luke Tierney