Skip to content

Speeding up a loop

5 messages · wwreith, Petr Savicky, Jean V Adams

wwreith
# 
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?



--
View this message in context: http://r.789695.n4.nabble.com/Speeding-up-a-loop-tp4637201.html
Sent from the R help mailing list archive at Nabble.com.
Petr Savicky
#
On Fri, Jul 20, 2012 at 05:45:30AM -0700, wwreith wrote:
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, ]
  nrow(x)

  [1] 888896

Hope this helps.

Petr Savicky.
Petr Savicky
#
On Fri, Jul 20, 2012 at 04:26:34PM +0200, Petr Savicky wrote:
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.