[R] Speeding up a loop
Petr Savicky
savicky at cs.cas.cz
Fri Jul 20 16:48:14 CEST 2012
On Fri, Jul 20, 2012 at 04:26:34PM +0200, Petr Savicky wrote:
> On Fri, Jul 20, 2012 at 05:45:30AM -0700, wwreith wrote:
> > General problem: I have 20 projects that can be invested in and I need to
> > decide which combinations meet a certain set of standards. The total
> > possible combinations comes out to 2^20. However I know for a fact that the
> > number of projects must be greater than 5 and less than 13. So far the the
> > code below is the best I can come up with for iteratively creating a set to
> > check against my set of standards.
> >
> > Code
> > x<-matrix(0,nrow=1,ncol=20)
> > for(i in 1:2^20)
> > {
> > x[1]<-x[1]+1
> > for(j in 1:20)
> > {
> > if(x[j]>1)
> > {
> > x[j]=0
> > if(j<20)
> > {
> > x[j+1]=x[j+1]+1
> > }
> > }
> > }
> > if(sum(x)>5 && sum(x)<13)
> > {
> > # insert criteria here.
> > }
> > }
> >
> > my code forces me to create all 2^20 x's and then use an if statement to
> > decide if x is within my range of projects. Is there a faster way to
> > increment x. Any ideas on how to kill the for loop so that it won't attempt
> > to process an x where the sum is greater than 12 or less than 6?
>
> Hi.
>
> The restriction on the sum of the rows between 6 and 12 eliminates the
> tails of the distribution, not the main part. So, the final number of
> rows is not much smaller than 2^20. More exactly, it is
>
> sum(choose(20, 6:12))
>
> which is about 0.8477173 * 2^20. On the other hand, all combinations
> may be created using expand.grid() faster than using a for loop.
>
> Try the following
>
> g <- as.matrix(expand.grid(rep(list(0:1), times=20)))
> s <- rowSums(g)
> x <- g[s > 5 & s < 13, ]
Hi.
The above code creates a matrix, whose rows are vectors of 0,1, which
contain between 6 and 12 ones. Using this matrix, it is possible to
go through all these combinations using a for loop as follows.
for (i in seq.int(length=nrow(x))) {
here, x[i, ] is a row of the matrix
}
Another option is to use ifelse() function, which allows to evaluate
a condition on the whole columns of the matrix. If this is possible,
then it is more efficient than a for loop.
Instead of using expand.grid() to create all 2^20 combinations, it is
possible to create only rows with a specified number of ones. The
rows of length n with exactly k ones can be created as follows.
n <- 5
k <- 2
ind <- combn(n, k)
m <- ncol(ind)
x <- matrix(0, nrow=m, ncol=n)
x[cbind(rep(1:m, each=k), c(ind))] <- 1
x
[1,] 1 1 0 0 0
[2,] 1 0 1 0 0
[3,] 1 0 0 1 0
[4,] 1 0 0 0 1
[5,] 0 1 1 0 0
[6,] 0 1 0 1 0
[7,] 0 1 0 0 1
[8,] 0 0 1 1 0
[9,] 0 0 1 0 1
[10,] 0 0 0 1 1
Hope this helps.
Petr Savicky.
More information about the R-help
mailing list