[R] detecting if a variable has changed
Duncan Murdoch
murdoch.duncan at gmail.com
Mon Jun 6 05:20:07 CEST 2016
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