search top n% of a vector member C++

Question

let's define

struct A
{ 
int m;
...
}

std::vector<A> vec; //a large vector (magnitude of million members)

I am interested to find top 2% member of vec where the members have highest value in their m method.

For that I was thinking something like this:

std::multimap<int, A> top_members;

const auto nr_top = std::lround(vec.size() * 0.02);
for (auto it = vec.begin(); it != vec.end(); ++it)
  {
  if(top_members.size() == nr_top + 1)
    top_members.erase(std::prev(top_members.end()));
  else
    top_members[it->m] = *it
  }

Do you think of any faster solution?

When you say "top 2%", do you mean 2% of the total number of vector entries? — PaulMcKenzie, Feb 27 '20 at 16:11
Is `vec` already sorted? Otherwise your solution only gets the **first** valid 2%, not the **top** 2% — Ajit Panigrahi, Feb 27 '20 at 16:13
To get the top `k` elements without sorting, one solution is to use a `min-heap` of `k` items. So if you know `k`, then you have a solution. — PaulMcKenzie, Feb 27 '20 at 16:14
@PaulMcKenzie: [All containers have O(1) size](https://stackoverflow.com/a/13751799/15416) so `k` is just `vec.size()/50`. But I think you need a max-heap, not a min-heap. — MSalters, Feb 27 '20 at 16:53
To get the top K, a min-heap would be used. (I know it sounds counter-intuitive). — PaulMcKenzie, Feb 27 '20 at 16:56

score 3 · Answer 1 · answered Feb 27 '20 at 16:54

3

It looks like you want partial_sort. It will sort 2% of your items, and the remaining 98% will be in essentially random order.

answered Feb 27 '20 at 16:54

MSalters

173,980
10
155
350

Philip Nelson · Accepted Answer · 2020-02-27T18:03:23.990

std::partial_sort has a complexity of n log m where n is the number of elements and m is the number elements you want sorted. You can use this to sort just the top 2%.

const auto nr_top = std::lround(vec.size() * 0.02);
std::partial_sort(vec.begin(), vec.begin() + nr_top, vec.end(),
  [](auto a, auto b){return a > b}
);
// the top 2% will be at the front of the vector

If you need the top 2% in a different container, you can use std::partial_sort_copy instead.

score 0 · Answer 3 · answered Feb 27 '20 at 19:43

If you can modify the vector and the elements inside are not already sorted, you can make use of std::nth_element:

template< class RandomIt, class Compare >
void nth_element( RandomIt first, RandomIt nth, RandomIt last,
                  Compare comp );

nth_element is a partial sorting algorithm that rearranges elements in [first, last) such that:

The element pointed at by nth is changed to whatever element would occur in that position if [first, last) were sorted.

All of the elements before this new nth element are less than or equal to the elements after the new nth element. ...

Complexity: Linear in std::distance(first, last) on average.

So that, given a std::vector<A> v, in your case you could write

size_t top_two = std::llround(v.size() * 0.02);

std::nth_element(v.begin(),
                 v.begin() + top_two,
                 v.end(),
                 [](A const& a, A const& b){ return b.m < a.m; });

search top n% of a vector member C++

3 Answers3