> > 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
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, 20
> On 06 Jun 2016, at 05:20 , Duncan Murdoch 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
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 Mur
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
woul
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" comi
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.4984304
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
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
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 fol
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
11 matches
Mail list logo
