[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