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@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 <n...@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@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@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@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.