thr3ads.net - R help - [R] Speeding up a loop [Jul 2012]

If this information is useful, please help other people find it:
Share via:

wwreith

2012-Jul-20 12:45 UTC

[R] Speeding up a loop

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.

Jean V Adams

2012-Jul-20 14:05 UTC

head link

[R] Speeding up a loop

I've had to do something similar, so I wrote a small function to help.
This runs in about 1/4 the time of your code on my machine.
Others may have a more efficient approach.

all.combs <- function(num, from=0, to=num) {
        # create a matrix of all possible combinations of num items
        # restrict each row to have between "from" and "to"
items
        res <- vector("list", to-from+1)
        for(i in seq(from:to)) {
                j <- (from:to)[i]
                if(j==0) res[[i]] <- rep(FALSE, num)
                comb <- combn(num, j)
                res[[i]] <- t(apply(comb, 2, function(x) 
!is.na(match(1:num, x))))
                }
        do.call(rbind, res)
        }

all.combs(20, 5, 13)

Jean


wwreith <reith_william@bah.com> wrote on 07/20/2012 07:45:30 AM:
> 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?
	[[alternative HTML version deleted]]

Petr Savicky

2012-Jul-20 14:26 UTC

head link

[R] Speeding up a loop

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, ]
  nrow(x)

  [1] 888896

Hope this helps.

Petr Savicky.

Jean V Adams

2012-Jul-20 15:26 UTC

head link

[R] Speeding up a loop

"Reith, William [USA]" <reith_william@bah.com> wrote on
07/20/2012
09:52:02 AM:
> Would this matrix eat up memory making the rest of my program 
> slower? Each x needs to be multiplied by a matrix and the results 
> checked against a set of thresholds. Doing them one at a time takes 
> at least 24 hours right now. 
> 
> Optimizing a program is not my thing. 
> 
> Sent from my Verizon Wireless 4GLTE smartphone

It's not mine either.
Better to ask the group.
I'm ccing R-help on this message.

Jean

> "Jean V Adams" <jvadams@usgs.gov> wrote on 07/20/2012 10:05
AM:
> 
> I've had to do something similar, so I wrote a small function to help. 
> This runs in about 1/4 the time of your code on my machine. 
> Others may have a more efficient approach. 
> 
> all.combs <- function(num, from=0, to=num) { 
>         # create a matrix of all possible combinations of num items 
>         # restrict each row to have between "from" and
"to" items
>         res <- vector("list", to-from+1) 
>         for(i in seq(from:to)) { 
>                 j <- (from:to)[i] 
>                 if(j==0) res[[i]] <- rep(FALSE, num) 
>                 comb <- combn(num, j) 
>                 res[[i]] <- t(apply(comb, 2, function(x) !is.na
> (match(1:num, x)))) 
>                 } 
>         do.call(rbind, res) 
>         } 
> 
> all.combs(20, 5, 13) 
> 
> Jean 
> 
> 
> wwreith <reith_william@bah.com> wrote on 07/20/2012 07:45:30 AM:
> 
> > 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?	[[alternative HTML version deleted]]

wwreith

2012-Jul-20 18:34 UTC

head link

[R] Speeding up a loop

That is faster than what I was doing and reducing 15% of my iterations it
still very helpful.

Next question.

I need to multiply each row x[i,] of the matrix x by another matrix A.
Specifically

for(i in 1:n)
{
If (x[i,]%*%A[,1]<.5 || x[i,]%*%A[,2]<42 || x[i,]%*%A[,3]>150) 
{
x<-x[-i,] 
n<-n-1
}. #In other words remove row i from x if it does not meet criteria
(>=.5,>=42, <=150). When multiplied to A}
Is there a better way than using a for loop for this or x<-x[-i,] for that
matter? I assume building a new matrix would be worse. 

Ideally I want to also exclude some x[,i] as well example if x[1,] is better
than x[2,] in all three categories i.e. bigger, bigger, and smaller than
x[2,] when multiplied to A then I want to exclude x[2,] as well. Any
suggestions on whether it is better to do this all at once or in stages?

Thanks for helping!



--
View this message in context:
http://r.789695.n4.nabble.com/Speeding-up-a-loop-tp4637201p4637255.html
Sent from the R help mailing list archive at Nabble.com.

Rui Barradas

2012-Jul-24 12:09 UTC

head link

[R] [External] Re: Speeding up a loop

Hello,

Are you sure? With a matirx composed of those two rows only I had a 
problem, the function to.keep() returned NULL. See the changes made to 
avoid it.

# beginning of loop
     for(i in seq_len(nrow(x))){
         #yes <- x[i, 1] > a1 | x[i, 2] > a2 | x[i, 3] < a3 | x[i,
4] > a4
         #if(all(yes)) keep(i, e)
         # Original post, do NOT remove if equal
         #no <- x[i, 1] < a1 | x[i, 2] < a2 | x[i, 3] > a3 | x[i, 4]
< a4
         # Changed to remove if equal
         no <- x[i, 1] <= a1 | x[i, 2] <= a2 | x[i, 3] >= a3 | x[i,
4] <= a4
         if(all(!no)) keep(i, e)
     }
     if(e$ires == 0 && nrow(x) > 0)
         x[1, ]
     else
         e$result[seq_len(e$ires), 1:nc]
# end of function


Em 23-07-2012 18:18, Reith, William [USA] escreveu:> It looks like both ways produce the same result.
>
> -----Original Message-----
> From: Rui Barradas [mailto:ruipbarradas at sapo.pt]
> Sent: Monday, July 23, 2012 1:05 PM
> To: Reith, William [USA]
> Subject: Re: [External] Re: [R] Speeding up a loop
>
> Hello,
>
> But that's the negation of '<', so try to negate
'<=', meaning, remove the equal signs. Sorry if I wasn't very
clear.
>
> Rui Barradas
>
> Em 23-07-2012 17:44, Reith, William [USA] escreveu:
>> This is what I have for the yes for loop
>>
>> for(i in seq_len(nrow(x))){
>>       yes <- x[i, 1] >= a1 | x[i, 2] >= a2 | x[i, 3] <= a3
| x[i, 4]>= a4
>>       if(all(yes)) keep(i, e)
>>     }
>>
>> -----Original Message-----
>> From: Rui Barradas [mailto:ruipbarradas at sapo.pt]
>> Sent: Monday, July 23, 2012 12:14 PM
>> To: Reith, William [USA]
>> Cc: r-help
>> Subject: [External] Re: [R] Speeding up a loop
>>
>> Hello,
>>
>> I think this is a boundary issue. In your op you've said
"less" not "less than or equal to".
>> Try using "<=" and ">=" to see what happens,
I bet it solves it.
>>
>> Rui Barradas
>>
>> Em 23-07-2012 14:43, wwreith escreveu:
>>> 1.15           60	0.553555415         0.574892872
>>> 1.15	   60	0.563183983         0.564029359
>>>
>>> Shouldn't the function row out the second one, since it it
higher in
>>> position 3 and lower in position 4 i.e. it should not all be yes?
>>>
>>>
>>>
>>>
>>>
>>> --
>>> View this message in context:
>>>
http://r.789695.n4.nabble.com/Speeding-up-a-loop-tp4637201p4637438.ht
>>> m l Sent from the R help mailing list archive at Nabble.com.
>>>
>>> ______________________________________________
>>> R-help at r-project.org mailing list
>>> https://stat.ethz.ch/mailman/listinfo/r-help
>>> PLEASE do read the posting guide
>>> http://www.R-project.org/posting-guide.html
>>> and provide commented, minimal, self-contained, reproducible code.

Rui Barradas

2012-Jul-24 18:35 UTC

head link

[R] [External] Re: Speeding up a loop

Hello,

Anyway, I've redid part of the function in order to accomodate 1. larger 
increments and 2. keep if equal or not. So, here's the complete version 
and forget my two previous mails.

to.keep <- function(x, increment = 1e4, keep.if.equal = FALSE){
     keep <- function(i, env){
         env$ires <- env$ires + 1
         if(env$ires > env$curr.rows){
             env$result <- rbind(env$result, matrix(nrow=increment, 
ncol=nc))
             env$curr.rows <- env$curr.rows + increment
         }
         env$result[env$ires, ] <- x[i, ]
     }

     x  <- as.matrix(x)
     a1 <- x[, 1]
     a2 <- x[, 2]
     a3 <- x[, 3]
     a4 <- x[, 4]
     nc <- ncol(x)

     e <- new.env()
     e$curr.rows <- increment
     e$result <- matrix(nrow=e$curr.rows, ncol=nc)
     e$ires <- 0
     if(keep.if.equal){
         for(i in seq_len(nrow(x))){
             yes <- a1[i] >= a1 | a2[i] >= a2 | a3[i] <= a3 | a4[i]
>= a4
             if(all(yes[-i])) keep(i, e)
         }
     }else{
         for(i in seq_len(nrow(x))){
             no <- a1[i] <= a1 & a2[i] <= a2 & a3[i] >= a3
& a4[i] <= a4
             if(!any(no[-i])) keep(i, e)
         }
     }
     e$result[seq_len(e$ires), 1:nc]
}


I hope this finally settles it.

Rui Barradas

Em 23-07-2012 18:18, Reith, William [USA] escreveu:> It looks like both ways produce the same result.
>
> -----Original Message-----
> From: Rui Barradas [mailto:ruipbarradas at sapo.pt]
> Sent: Monday, July 23, 2012 1:05 PM
> To: Reith, William [USA]
> Subject: Re: [External] Re: [R] Speeding up a loop
>
> Hello,
>
> But that's the negation of '<', so try to negate
'<=', meaning, remove the equal signs. Sorry if I wasn't very
clear.
>
> Rui Barradas
>
> Em 23-07-2012 17:44, Reith, William [USA] escreveu:
>> This is what I have for the yes for loop
>>
>> for(i in seq_len(nrow(x))){
>>       yes <- x[i, 1] >= a1 | x[i, 2] >= a2 | x[i, 3] <= a3
| x[i, 4]>= a4
>>       if(all(yes)) keep(i, e)
>>     }
>>
>> -----Original Message-----
>> From: Rui Barradas [mailto:ruipbarradas at sapo.pt]
>> Sent: Monday, July 23, 2012 12:14 PM
>> To: Reith, William [USA]
>> Cc: r-help
>> Subject: [External] Re: [R] Speeding up a loop
>>
>> Hello,
>>
>> I think this is a boundary issue. In your op you've said
"less" not "less than or equal to".
>> Try using "<=" and ">=" to see what happens,
I bet it solves it.
>>
>> Rui Barradas
>>
>> Em 23-07-2012 14:43, wwreith escreveu:
>>> 1.15           60	0.553555415         0.574892872
>>> 1.15	   60	0.563183983         0.564029359
>>>
>>> Shouldn't the function row out the second one, since it it
higher in
>>> position 3 and lower in position 4 i.e. it should not all be yes?
>>>
>>>
>>>
>>>
>>>
>>> --
>>> View this message in context:
>>>
http://r.789695.n4.nabble.com/Speeding-up-a-loop-tp4637201p4637438.ht
>>> m l Sent from the R help mailing list archive at Nabble.com.
>>>
>>> ______________________________________________
>>> R-help at r-project.org mailing list
>>> https://stat.ethz.ch/mailman/listinfo/r-help
>>> PLEASE do read the posting guide
>>> http://www.R-project.org/posting-guide.html
>>> and provide commented, minimal, self-contained, reproducible code.

Maybe Matching Threads

Search for more seemingly similar threads

R help - Jul 2012 - Speeding up a loop

[R] Speeding up a loop

[R] Speeding up a loop

[R] Speeding up a loop

[R] Speeding up a loop

[R] Speeding up a loop

[R] [External] Re: Speeding up a loop

[R] [External] Re: Speeding up a loop

Maybe Matching Threads