[R] detecting if a variable has changed

peter dalgaard pdalgd at gmail.com
Mon Jun 6 09:46:06 CEST 2016


> On 06 Jun 2016, at 05:20 , 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.

Yep. To do better, you probably need a different storage format (like a binary tree) or specialized hardware - single-instruction/multiple-data architecture devices come to mind. 

-pd

> 
> 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.
>> 
> 
> ______________________________________________
> 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.

-- 
Peter Dalgaard, Professor,
Center for Statistics, Copenhagen Business School
Solbjerg Plads 3, 2000 Frederiksberg, Denmark
Phone: (+45)38153501
Office: A 4.23
Email: pd.mes at cbs.dk  Priv: PDalgd at gmail.com



More information about the R-help mailing list