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