Nope, Ted. I asked for a O(log(n)) solution, not an O(n) one. I will check out the data.table package, as suggested.
-- 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 11:01 AM, Ted Harding <ted.hard...@wlandres.net> wrote: > 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@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. > > ------------------------------------------------- > E-Mail: (Ted Harding) <ted.hard...@wlandres.net> > Date: 05-Jun-2016 Time: 19:01:10 > This message was sent by XFMail > ------------------------------------------------- ______________________________________________ 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.