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.hard...@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@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 <n...@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@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, reproducible code.
-------------------------------------------------
E-Mail: (Ted Harding) <ted.hard...@wlandres.net>
Date: 05-Jun-2016 Time: 19:01:10
This message was sent by XFMail
-------------------------------------------------
______________________________________________
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.
