Re: [R] detecting if a variable has changed
> > 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. If the vector is presorted, wouldn't a binary search find the correct location in O(log(n))? (roughly log2(n)?) After that any insertion depends on how fast R can move memory about so the overall speed clearly depends on factors other than finding the location. S Ellison *** This email and any attachments are confidential. Any use...{{dropped:8}} __ 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.
Re: [R] detecting if a variable has changed
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 Murdochwrote: > 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 >> 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 > 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":
Re: [R] detecting if a variable has changed
> On 06 Jun 2016, at 05:20 , Duncan Murdochwrote: > > 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 >> 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 > 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
Re: [R] detecting if a variable has changed
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 Hardingwrote: 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 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 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
Re: [R] detecting if a variable has changed
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> 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 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,
Re: [R] detecting if a variable has changed
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 Hardingwrote: > 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 >>> 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 >>> > 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
Re: [R] detecting if a variable has changed
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 >>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 >> > 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
Re: [R] detecting if a variable has changed
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 >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 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
Re: [R] detecting if a variable has changed
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 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-helpwrote: > 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 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,
Re: [R] detecting if a variable has changed
Hi, This looks more or less what I'm looking for! Thanks! :) Neal On Sun, 05 Jun 2016 18:47:11 +0200, William Dunlap wrote: > > [1 ] > [2 ] > 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> 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. > > __ 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.
Re: [R] detecting if a variable has changed
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. Walfieldwrote: > 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.