[R] detecting if a variable has changed
Bert Gunter
bgunter.4567 at gmail.com
Mon Jun 6 16:52:20 CEST 2016
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.duncan at 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.Harding at 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 at 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 <neal at 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 at 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 at 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 at 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.Harding at wlandres.net>
>>> Date: 05-Jun-2016 Time: 19:01:10
>>> This message was sent by XFMail
>>> -------------------------------------------------
>>
>>
>> ______________________________________________
>> R-help at 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.
>>
>
More information about the R-help
mailing list