hello, first I create a list: l <- list("1"<-c(1,2,3)) then I run the following cycle, it takes over a minute(!) to complete on a very fast mashine: for(i in (1:10^5)) l[[length(l)+1]] <- c(i,i+1,i) How can I fill a list faster? (This is just a demo test, the elements of the list are calculated iteratively in an algorithm) Are there any packages and documents on how to use more advanced and fast data structures like linked-lists, hash-tables or trees for example? Thank you, Balazs Torma
It all depends on what you want to do. In your example, it is faster to first fill in a matrix and then convert the matrix to a list. The problem with filling in the list is that you are dynamically allocating space for each iteration which is probably taking at least an order of magnitude more time than the calculations you are doing. So I just translated your problem into two steps and it takes about 2 seconds on my system.> # fill in a matris > l <- matrix(ncol=3, nrow=10^5) > system.time(for(i in (1:10^5)) l[i,] <- c(i,i+1,i))user system elapsed 1.06 0.00 1.10> # convert to a list > system.time(l.list <- lapply(1:10^5, function(i) l[i,]))user system elapsed 0.45 0.00 0.46> l.list[1:10][[1]] [1] 1 2 1 [[2]] [1] 2 3 2 [[3]] [1] 3 4 3 [[4]] [1] 4 5 4 [[5]] [1] 5 6 5 On 7/13/07, Balazs Torma <torma at sztaki.hu> wrote:> hello, > > first I create a list: > > l <- list("1"<-c(1,2,3)) > > then I run the following cycle, it takes over a minute(!) to > complete on a very fast mashine: > > for(i in (1:10^5)) l[[length(l)+1]] <- c(i,i+1,i) > > How can I fill a list faster? (This is just a demo test, the elements > of the list are calculated iteratively in an algorithm) > > Are there any packages and documents on how to use more advanced and > fast data structures like linked-lists, hash-tables or trees for > example? > > Thank you, > Balazs Torma > > ______________________________________________ > R-help at stat.math.ethz.ch mailing list > stat.ethz.ch/mailman/listinfo/r-help > PLEASE do read the posting guide R-project.org/posting-guide.html > and provide commented, minimal, self-contained, reproducible code. >-- Jim Holtman Cincinnati, OH +1 513 646 9390 What is the problem you are trying to solve?
If all the data coming from your iterations are numeric (as in your toy example), why not to use a matrix with one row per iteration? Also, do preallocate the matrix and do not add row or column names before the end of the calculation. Something like: > m <- matrix(rep(NA, 3*10^5), ncol = 3) > system.time(for(i in (1:10^5)) m[i, ] <- c(i,i+1,i)) user system elapsed 1.362 0.033 1.424 That is, about 1.5sec on my Intel Duo Core 2.33Mhz MacBook Pro, compared to: > l <- list("1"<-c(1,2,3)) > system.time(for(i in (1:10^5)) l[[length(l)+1]] <- c(i,i+1,i)) user system elapsed 191.629 49.110 248.454 ... more than 4 minutes for your code. By the way, what is your "very fast machine", that is actually four times faster than mine (grrrrr!)? Best, Philippe Grosjean ..............................................<?}))><........ ) ) ) ) ) ( ( ( ( ( Prof. Philippe Grosjean ) ) ) ) ) ( ( ( ( ( Numerical Ecology of Aquatic Systems ) ) ) ) ) Mons-Hainaut University, Belgium ( ( ( ( ( .............................................................. Balazs Torma wrote:> hello, > > first I create a list: > > l <- list("1"<-c(1,2,3)) > > then I run the following cycle, it takes over a minute(!) to > complete on a very fast mashine: > > for(i in (1:10^5)) l[[length(l)+1]] <- c(i,i+1,i) > > How can I fill a list faster? (This is just a demo test, the elements > of the list are calculated iteratively in an algorithm) > > Are there any packages and documents on how to use more advanced and > fast data structures like linked-lists, hash-tables or trees for > example? > > Thank you, > Balazs Torma > > ______________________________________________ > R-help at stat.math.ethz.ch mailing list > stat.ethz.ch/mailman/listinfo/r-help > PLEASE do read the posting guide R-project.org/posting-guide.html > and provide commented, minimal, self-contained, reproducible code. >
Actually if you are really interested in the list, then just do the lapply and compute your data; it seems to be even faster than the matrix:> system.time(l.1 <- lapply(1:10^5, function(i) c(i, i+1, i)))user system elapsed 0.50 0.00 0.61> l.1[1:4][[1]] [1] 1 2 1 [[2]] [1] 2 3 2 [[3]] [1] 3 4 3 [[4]] [1] 4 5 4 On 7/13/07, Philippe Grosjean <phgrosjean at sciviews.org> wrote:> If all the data coming from your iterations are numeric (as in your toy > example), why not to use a matrix with one row per iteration? Also, do > preallocate the matrix and do not add row or column names before the end > of the calculation. Something like: > > > m <- matrix(rep(NA, 3*10^5), ncol = 3) > > system.time(for(i in (1:10^5)) m[i, ] <- c(i,i+1,i)) > user system elapsed > 1.362 0.033 1.424 > > That is, about 1.5sec on my Intel Duo Core 2.33Mhz MacBook Pro, compared to: > > > l <- list("1"<-c(1,2,3)) > > system.time(for(i in (1:10^5)) l[[length(l)+1]] <- c(i,i+1,i)) > user system elapsed > 191.629 49.110 248.454 > > ... more than 4 minutes for your code. > > By the way, what is your "very fast machine", that is actually four > times faster than mine (grrrrr!)? > > Best, > > Philippe Grosjean > > ..............................................<?}))><........ > ) ) ) ) ) > ( ( ( ( ( Prof. Philippe Grosjean > ) ) ) ) ) > ( ( ( ( ( Numerical Ecology of Aquatic Systems > ) ) ) ) ) Mons-Hainaut University, Belgium > ( ( ( ( ( > .............................................................. > > Balazs Torma wrote: > > hello, > > > > first I create a list: > > > > l <- list("1"<-c(1,2,3)) > > > > then I run the following cycle, it takes over a minute(!) to > > complete on a very fast mashine: > > > > for(i in (1:10^5)) l[[length(l)+1]] <- c(i,i+1,i) > > > > How can I fill a list faster? (This is just a demo test, the elements > > of the list are calculated iteratively in an algorithm) > > > > Are there any packages and documents on how to use more advanced and > > fast data structures like linked-lists, hash-tables or trees for > > example? > > > > Thank you, > > Balazs Torma > > > > ______________________________________________ > > R-help at stat.math.ethz.ch mailing list > > stat.ethz.ch/mailman/listinfo/r-help > > PLEASE do read the posting guide R-project.org/posting-guide.html > > and provide commented, minimal, self-contained, reproducible code. > > > > ______________________________________________ > R-help at stat.math.ethz.ch mailing list > stat.ethz.ch/mailman/listinfo/r-help > PLEASE do read the posting guide R-project.org/posting-guide.html > and provide commented, minimal, self-contained, reproducible code. >-- Jim Holtman Cincinnati, OH +1 513 646 9390 What is the problem you are trying to solve?
another solution: l <- vector(mode = "list", length = 10^5) system.time(for(i in (1:10^5)) l[[i]] <- c(i,i+1,i)) On my system this version is even slightly faster than the matrix version ... Best, Matthias ----- original message -------- Subject: Re: [R] filling a list faster Sent: Fri, 13 Jul 2007 From: Philippe Grosjean<phgrosjean at sciviews.org>> If all the data coming from your iterations are numeric (as in your toy > example), why not to use a matrix with one row per iteration? Also, do > preallocate the matrix and do not add row or column names before the end > of the calculation. Something like: > > > m <- matrix(rep(NA, 3*10^5), ncol = 3) > > system.time(for(i in (1:10^5)) m[i, ] <- c(i,i+1,i)) > user system elapsed > 1.362 0.033 1.424 > > That is, about 1.5sec on my Intel Duo Core 2.33Mhz MacBook Pro, compared to: > > > l <- list("1"<-c(1,2,3)) > > system.time(for(i in (1:10^5)) l[[length(l)+1]] <- c(i,i+1,i)) > user system elapsed > 191.629 49.110 248.454 > > ... more than 4 minutes for your code. > > By the way, what is your "very fast machine", that is actually four > times faster than mine (grrrrr!)? > > Best, > > Philippe Grosjean > > ..............................................<?}))><........ > ) ) ) ) ) > ( ( ( ( ( Prof. Philippe Grosjean > ) ) ) ) ) > ( ( ( ( ( Numerical Ecology of Aquatic Systems > ) ) ) ) ) Mons-Hainaut University, Belgium > ( ( ( ( ( > .............................................................. > > Balazs Torma wrote: > > hello, > > > > first I create a list: > > > > l <- list("1"<-c(1,2,3)) > > > > then I run the following cycle, it takes over a minute(!) to > > complete on a very fast mashine: > > > > for(i in (1:10^5)) l[[length(l)+1]] <- c(i,i+1,i) > > > > How can I fill a list faster? (This is just a demo test, the elements > > of the list are calculated iteratively in an algorithm) > > > > Are there any packages and documents on how to use more advanced and > > fast data structures like linked-lists, hash-tables or trees for > > example? > > > > Thank you, > > Balazs Torma > > > > ______________________________________________ > > R-help at stat.math.ethz.ch mailing list > > stat.ethz.ch/mailman/listinfo/r-help > > PLEASE do read the posting guide > R-project.org/posting-guide.html > > and provide commented, minimal, self-contained, reproducible code. > > > > ______________________________________________ > R-help at stat.math.ethz.ch mailing list > stat.ethz.ch/mailman/listinfo/r-help > PLEASE do read the posting guide R-project.org/posting-guide.html > and provide commented, minimal, self-contained, reproducible code. >--- original message end ----