Oh, good point! I was thinking only of the comparisons to identify the insertion location.
--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 8:20 PM, Duncan Murdoch <murdoch.dun...@gmail.com> wrote: > On 05/06/2016 2:13 PM, Bert Gunter wrote: >> >> Nope, Ted. I asked for a O(log(n)) solution, not an O(n) one. > > > I don't think that's possible with a numeric vector. Inserting an entry at > a random location is an O(n) operation, since you need to move all following > values out of the way. > > Duncan Murdoch > >> >> 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. >> > ______________________________________________ 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.