This help thread suggested a question to me: Is there a function in some package that efficiently (I.e. O(log(n)) ) inserts a single new element into the correct location in an already-sorted vector? My assumption here is that doing it via sort() is inefficient, but maybe that is incorrect. Please correct me if so. I realize that it would be straightforward to write such a function, but I just wondered if it already exists. My google & rseek searches did not succeed, but maybe I used the wrong keywords. Cheers, Bert Bert Gunter "The trouble with having an open mind is that people keep coming along and sticking things into it." -- Opus (aka Berkeley Breathed in his "Bloom County" comic strip ) On Sun, Jun 5, 2016 at 9:47 AM, William Dunlap via R-help <r-help at r-project.org> wrote:> I don't know what you mean by "without having to use any special > interfaces", but "reference classes" will do what I think you want. E.g., > the following makes a class called 'SortedNumeric' that only sorts the > vector when you want to get its value, not when you append values. It > stores the sorted vector so it does not get resorted each time you ask for > it. > > SortedNumeric <- setRefClass("sortedNumeric", > fields = list( > fData = "numeric", > fIsUnsorted = "logical"), > methods = list( > initialize = function(Data = numeric(), isUnsorted = TRUE) { > fData <<- Data > stopifnot(is.logical(isUnsorted), > length(isUnsorted)==1, > !is.na(isUnsorted)) > fIsUnsorted <<- isUnsorted > }, > getData = function() { > if (isUnsorted) { > fData <<- sort(fData) > fIsUnsorted <<- FALSE > } > fData > }, > appendData = function(newEntries) { > fData <<- c(fData, newEntries) > fIsUnsorted <<- TRUE > } > )) > > Use it as: > >> x <- SortedNumeric$new() >> x$appendData(c(4,2,5)) >> x$appendData(c(1,8,9)) >> x > Reference class object of class "sortedNumeric" > Field "fData": > [1] 4 2 5 1 8 9 > Field "fIsUnsorted": > [1] TRUE >> x$getData() > [1] 1 2 4 5 8 9 >> x > Reference class object of class "sortedNumeric" > Field "fData": > [1] 1 2 4 5 8 9 > Field "fIsUnsorted": > [1] FALSE > > > Outside of base R, I think the R6 package gives another approach to this. > > > Bill Dunlap > TIBCO Software > wdunlap tibco.com > > On Sun, Jun 5, 2016 at 6:53 AM, Neal H. Walfield <neal at walfield.org> wrote: > >> Hi, >> >> I have a huge list. Normally it is sorted, but I want to be able to >> add elements to it without having to use any special interfaces and >> then sort it on demand. My idea is to use something like weak >> references combined with attributes. Consider: >> >> # Initialization. >> l = as.list(1:10) >> # Note that it is sorted. >> attr(l, 'sorted') = weakref(l) >> >> # Modify the list. >> l = append(l, 1:3) >> >> # Check if the list is still sorted. (I use identical here, but it >> # probably too heavy weight: I just need to compare the addresses.) >> if (! identical(l, attr(l, 'sorted'))) { >> l = sort(unlist(l)) >> attr(l, 'sorted') = weakref(l) >> } >> # Do operation that requires sorted list. >> ... >> >> This is obviously a toy example. I'm not actually sorting integers >> and I may use a matrix instead of a list. >> >> I've read: >> >> http://www.hep.by/gnu/r-patched/r-exts/R-exts_122.html >> http://homepage.stat.uiowa.edu/~luke/R/references/weakfinex.html >> >> As far as I can tell, weakrefs are only available via the C API. Is >> there a way to do what I want in R without resorting to C code? Is >> what I want to do better achieved using something other than weakrefs? >> >> Thanks! >> >> :) Neal >> >> ______________________________________________ >> R-help at r-project.org mailing list -- To UNSUBSCRIBE and more, see >> 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. >> > > [[alternative HTML version deleted]] > > ______________________________________________ > R-help at r-project.org mailing list -- To UNSUBSCRIBE and more, see > 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.
On Sun, 05 Jun 2016 19:34:38 +0200, Bert Gunter wrote:> This help thread suggested a question to me: > > Is there a function in some package that efficiently (I.e. O(log(n)) ) > inserts a single new element into the correct location in an > already-sorted vector? My assumption here is that doing it via sort() > is inefficient, but maybe that is incorrect. Please correct me if so.I think data.table will do this if the the column is marked appropriately.> I realize that it would be straightforward to write such a function, > but I just wondered if it already exists. My google & rseek searches > did not succeed, but maybe I used the wrong keywords. > > Cheers, > Bert > > > Bert Gunter > > "The trouble with having an open mind is that people keep coming along > and sticking things into it." > -- Opus (aka Berkeley Breathed in his "Bloom County" comic strip ) > > > On Sun, Jun 5, 2016 at 9:47 AM, William Dunlap via R-help > <r-help at r-project.org> wrote: > > I don't know what you mean by "without having to use any special > > interfaces", but "reference classes" will do what I think you want. E.g., > > the following makes a class called 'SortedNumeric' that only sorts the > > vector when you want to get its value, not when you append values. It > > stores the sorted vector so it does not get resorted each time you ask for > > it. > > > > SortedNumeric <- setRefClass("sortedNumeric", > > fields = list( > > fData = "numeric", > > fIsUnsorted = "logical"), > > methods = list( > > initialize = function(Data = numeric(), isUnsorted = TRUE) { > > fData <<- Data > > stopifnot(is.logical(isUnsorted), > > length(isUnsorted)==1, > > !is.na(isUnsorted)) > > fIsUnsorted <<- isUnsorted > > }, > > getData = function() { > > if (isUnsorted) { > > fData <<- sort(fData) > > fIsUnsorted <<- FALSE > > } > > fData > > }, > > appendData = function(newEntries) { > > fData <<- c(fData, newEntries) > > fIsUnsorted <<- TRUE > > } > > )) > > > > Use it as: > > > >> x <- SortedNumeric$new() > >> x$appendData(c(4,2,5)) > >> x$appendData(c(1,8,9)) > >> x > > Reference class object of class "sortedNumeric" > > Field "fData": > > [1] 4 2 5 1 8 9 > > Field "fIsUnsorted": > > [1] TRUE > >> x$getData() > > [1] 1 2 4 5 8 9 > >> x > > Reference class object of class "sortedNumeric" > > Field "fData": > > [1] 1 2 4 5 8 9 > > Field "fIsUnsorted": > > [1] FALSE > > > > > > Outside of base R, I think the R6 package gives another approach to this. > > > > > > Bill Dunlap > > TIBCO Software > > wdunlap tibco.com > > > > On Sun, Jun 5, 2016 at 6:53 AM, Neal H. Walfield <neal at walfield.org> wrote: > > > >> Hi, > >> > >> I have a huge list. Normally it is sorted, but I want to be able to > >> add elements to it without having to use any special interfaces and > >> then sort it on demand. My idea is to use something like weak > >> references combined with attributes. Consider: > >> > >> # Initialization. > >> l = as.list(1:10) > >> # Note that it is sorted. > >> attr(l, 'sorted') = weakref(l) > >> > >> # Modify the list. > >> l = append(l, 1:3) > >> > >> # Check if the list is still sorted. (I use identical here, but it > >> # probably too heavy weight: I just need to compare the addresses.) > >> if (! identical(l, attr(l, 'sorted'))) { > >> l = sort(unlist(l)) > >> attr(l, 'sorted') = weakref(l) > >> } > >> # Do operation that requires sorted list. > >> ... > >> > >> This is obviously a toy example. I'm not actually sorting integers > >> and I may use a matrix instead of a list. > >> > >> I've read: > >> > >> http://www.hep.by/gnu/r-patched/r-exts/R-exts_122.html > >> http://homepage.stat.uiowa.edu/~luke/R/references/weakfinex.html > >> > >> As far as I can tell, weakrefs are only available via the C API. Is > >> there a way to do what I want in R without resorting to C code? Is > >> what I want to do better achieved using something other than weakrefs? > >> > >> Thanks! > >> > >> :) Neal > >> > >> ______________________________________________ > >> R-help at r-project.org mailing list -- To UNSUBSCRIBE and more, see > >> 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. > >> > > > > [[alternative HTML version deleted]] > > > > ______________________________________________ > > R-help at r-project.org mailing list -- To UNSUBSCRIBE and more, see > > 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. >
Surely it is straightforward, since the vector (say 'X') is already sorted? Example (raw code with explicit example): set.seed(54321) X <- sort(runif(10)) # X ## The initial sorted vector # [1] 0.04941009 0.17669234 0.20913493 0.21651016 0.27439354 # [6] 0.34161241 0.37165878 0.42900782 0.49843042 0.86636110 y <- runif(1) # y ## The new value to be inserted [1] 0.1366424 Y <- c(X[X<=y],y,X[X>y]) ## Now insert y into X: Y [1] 0.04941009 0.13664239 0.17669234 0.20913493 0.21651016 0.27439354 [7] 0.34161241 0.37165878 0.42900782 0.49843042 0.86636110 ## And there it is at Y[2] Easy to make such a function! Best wishes to all, Ted. On 05-Jun-2016 17:44:29 Neal H. Walfield wrote:> On Sun, 05 Jun 2016 19:34:38 +0200, > Bert Gunter wrote: >> This help thread suggested a question to me: >> >> Is there a function in some package that efficiently (I.e. O(log(n)) ) >> inserts a single new element into the correct location in an >> already-sorted vector? My assumption here is that doing it via sort() >> is inefficient, but maybe that is incorrect. Please correct me if so. > > I think data.table will do this if the the column is marked > appropriately. > >> I realize that it would be straightforward to write such a function, >> but I just wondered if it already exists. My google & rseek searches >> did not succeed, but maybe I used the wrong keywords. >> >> Cheers, >> Bert >> >> >> Bert Gunter >> >> "The trouble with having an open mind is that people keep coming along >> and sticking things into it." >> -- Opus (aka Berkeley Breathed in his "Bloom County" comic strip ) >> >> >> On Sun, Jun 5, 2016 at 9:47 AM, William Dunlap via R-help >> <r-help at r-project.org> wrote: >> > I don't know what you mean by "without having to use any special >> > interfaces", but "reference classes" will do what I think you want. E.g., >> > the following makes a class called 'SortedNumeric' that only sorts the >> > vector when you want to get its value, not when you append values. It >> > stores the sorted vector so it does not get resorted each time you ask for >> > it. >> > >> > SortedNumeric <- setRefClass("sortedNumeric", >> > fields = list( >> > fData = "numeric", >> > fIsUnsorted = "logical"), >> > methods = list( >> > initialize = function(Data = numeric(), isUnsorted = TRUE) >> > { >> > fData <<- Data >> > stopifnot(is.logical(isUnsorted), >> > length(isUnsorted)==1, >> > !is.na(isUnsorted)) >> > fIsUnsorted <<- isUnsorted >> > }, >> > getData = function() { >> > if (isUnsorted) { >> > fData <<- sort(fData) >> > fIsUnsorted <<- FALSE >> > } >> > fData >> > }, >> > appendData = function(newEntries) { >> > fData <<- c(fData, newEntries) >> > fIsUnsorted <<- TRUE >> > } >> > )) >> > >> > Use it as: >> > >> >> x <- SortedNumeric$new() >> >> x$appendData(c(4,2,5)) >> >> x$appendData(c(1,8,9)) >> >> x >> > Reference class object of class "sortedNumeric" >> > Field "fData": >> > [1] 4 2 5 1 8 9 >> > Field "fIsUnsorted": >> > [1] TRUE >> >> x$getData() >> > [1] 1 2 4 5 8 9 >> >> x >> > Reference class object of class "sortedNumeric" >> > Field "fData": >> > [1] 1 2 4 5 8 9 >> > Field "fIsUnsorted": >> > [1] FALSE >> > >> > >> > Outside of base R, I think the R6 package gives another approach to this. >> > >> > >> > Bill Dunlap >> > TIBCO Software >> > wdunlap tibco.com >> > >> > On Sun, Jun 5, 2016 at 6:53 AM, Neal H. Walfield <neal at walfield.org> >> > wrote: >> > >> >> Hi, >> >> >> >> I have a huge list. Normally it is sorted, but I want to be able to >> >> add elements to it without having to use any special interfaces and >> >> then sort it on demand. My idea is to use something like weak >> >> references combined with attributes. Consider: >> >> >> >> # Initialization. >> >> l = as.list(1:10) >> >> # Note that it is sorted. >> >> attr(l, 'sorted') = weakref(l) >> >> >> >> # Modify the list. >> >> l = append(l, 1:3) >> >> >> >> # Check if the list is still sorted. (I use identical here, but it >> >> # probably too heavy weight: I just need to compare the addresses.) >> >> if (! identical(l, attr(l, 'sorted'))) { >> >> l = sort(unlist(l)) >> >> attr(l, 'sorted') = weakref(l) >> >> } >> >> # Do operation that requires sorted list. >> >> ... >> >> >> >> This is obviously a toy example. I'm not actually sorting integers >> >> and I may use a matrix instead of a list. >> >> >> >> I've read: >> >> >> >> http://www.hep.by/gnu/r-patched/r-exts/R-exts_122.html >> >> http://homepage.stat.uiowa.edu/~luke/R/references/weakfinex.html >> >> >> >> As far as I can tell, weakrefs are only available via the C API. Is >> >> there a way to do what I want in R without resorting to C code? Is >> >> what I want to do better achieved using something other than weakrefs? >> >> >> >> Thanks! >> >> >> >> :) Neal >> >> >> >> ______________________________________________ >> >> R-help at r-project.org mailing list -- To UNSUBSCRIBE and more, see >> >> 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. >> >> >> > >> > [[alternative HTML version deleted]] >> > >> > ______________________________________________ >> > R-help at r-project.org mailing list -- To UNSUBSCRIBE and more, see >> > 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. >> > > ______________________________________________ > R-help at r-project.org mailing list -- To UNSUBSCRIBE and more, see > 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.------------------------------------------------- E-Mail: (Ted Harding) <Ted.Harding at wlandres.net> Date: 05-Jun-2016 Time: 19:01:10 This message was sent by XFMail