Selection algorithm
Giuliano Bertoletti
Hello,
is there a better way to find the first k ranked elements of a vector of
size n (with k < n) without sorting it first.
Roughly I have n in the range [200..2000] and k = 3 or 4.
Sorting would cost at least n*log(n) which in my opinion is a waste of time.
Maybe I could hardwire a loop with a few comparisons for a given k (say
k=3). I mean specialize a function for a certain k.
Any ideas ?
Cheers,
Giulio.
Victor Bazarov
GIYF
Also, see FAQ 5.2, just in case.
V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Stuart Golodetz
>
> Hello,
>
> is there a better way to find the first k ranked elements of a vector of
> size n (with k < n) without sorting it first.
Yes. I recommend you read Effective STL (by Scott Meyers).
Cheers,
Stu
SG
> Hello,
>
> is there a better way to find the first k ranked elements of a vector of
> size n (with k < n) without sorting it first.
>
> Roughly I have n in the range [200..2000] and k = 3 or 4.
>
> Sorting would cost at least n*log(n) which in my opinion is a waste of time.
There's std::partial_sort which does what you want. But it obviously
modifies the vector. If you don't want to alter that vector you can
process the sequence in one pass and remember the k smallest elements.
I think you can do that with a little heap. Checkout std::push_heap,
std::pop_heap. The complexity should be something like O(log(k)*n).
Cheers!
SG
Giuliano Bertoletti
>
> GIYF
>
> Also, see FAQ 5.2, just in case.
>
> V
A better answer might have been: "use std::nth_element function of the
STL library".
By the way, that's not a homework assignement.
Just trying to speed up a complex search algorithm where pruning is
mandatory and a lazy sort of the tree branches would be too expensive.
Cheers,
Giulio.
Giuliano Bertoletti
Hello,
I guess that perfectly suits may needs. Thank you.
Not only I do not care if the elements get rearranged, but I also need
to erase the remaining n-k.
So a partial_sort followed by a resize of the vector should be ok.
The algorithm is meant to expand and evaluate the n branches of a tree
node and then keep only k of them where the search continues.
Cheers,
Giulio.
SG ha scritto:
Stuart Golodetz
whereas nth_element doesn't: if you don't care about the order of the
elements afterwards, I guess you'd expect nth_element to involve less
work, but I don't know how much difference it would make in practice
without profiling it.
The bit in Effective STL I was referring to was Item 31, in case it's
useful.
Regards,
Stu
Jerry Coffin
@libero.it says...
std::partial_sort should do the job reasonably well. Technically it
does a little more than you need (the first N elements are sorted)
but for small k, the difference is unlikely to mean much.
--
Later,
Jerry.
Jerry Coffin
@p15g2000vbl.googlegroups.com>, s.ges...@gmail.com says...
[ ... ]
> There's std::partial_sort which does what you want. But it
> obviously modifies the vector. If you don't want to alter that
> vector you can process the sequence in one pass and remember the k
> smallest elements.
Or look up std::partial_sort_copy.
--
Later,
Jerry.
Digital Puer
> Hello,
>
> is there a better way to find the first k ranked elements of a vector of
> size n (with k < n) without sorting it first.
>
> Roughly I have n in the range [200..2000] and k = 3 or 4.
>
> Sorting would cost at least n*log(n) which in my opinion is a waste of time.
>
> Maybe I could hardwire a loop with a few comparisons for a given k (say
> k=3). I mean specialize a function for a certain k.
>
>
> Cheers,
> Giulio.
You can do it in O(n) time. In the "Introduction to Algorithms"
book by Cormen, et al., 2001, there are two algorithms to find
the kth largest (or smallest) element in an unordered list.
One of them is a randomised algorithm with theta(n) expected /
O(n^2) worst case running time, and another is O(n) worst case.
The second one is quite difficult to implement and has a high
hidden constant (it implements a median-of-median search).
Anyways, once you find the kth largest element in O(n) time,
you can take one pass through the list in O(n) time to find
the elements that are smaller (or larger). Total running time
is O(n).