Ah, perhaps I'm beginning to undertstand the question!
Presumably the issue is that evaluating X[X<=y] takes O(n) time,
where n = length(X), and similarly X[X>y].
So I suppose that one needs to be looking at some procedure for
a "bisecting" search for the largest r such that X[r] <= y, which
would then be O(log2(n)).
Perhaps not altogether straightforward to program, but straqightforward
in concept!
Apologies for misunderstanding.
Ted.
On 05-Jun-2016 18:13:15 Bert Gunter wrote:
> 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.
-------------------------------------------------
E-Mail: (Ted Harding) <ted.hard...@wlandres.net>
Date: 05-Jun-2016 Time: 20:49:12
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.
