2
$\begingroup$

I have an uncommon use case

I have a vector, which contains a fixed number of taxi's real-time fees (the red/green number that keeps bumping up when you sit in the back).

This vector is continuously updated by message sent back from taxis. I need to find the top 10 taxis every time when there is an update.

if I only need to do this once, then std::sort() or std::partial_sort would easily solve the problem. However, since the vector is largely the same after only a few updates, the sorting result from step T should be largely the same as sorting result of step T+1

I am wondering if the std::partial_sort will be 'smart' enough to 'incrementally' sort the vector, rather than start-over again from scratch.

Can anyone share any ideas here?

Thanks!

$\endgroup$
2
  • $\begingroup$ The specific implementation of C++ functions is off topic on this site. Although, we'll be able to help you find an algorithm for your problem, you'll have to handle the implementation yourself. $\endgroup$
    – Discrete lizard
    Jan 14, 2018 at 21:24
  • 2
    $\begingroup$ perhaps look at some self-balancing binary search tree's insert operation. $\endgroup$ Jan 14, 2018 at 21:50

3 Answers 3

1
$\begingroup$

Look at what your problem actually is: Your problem is not sorting the list, but finding the largest ten items. That's a much easier problem, which can be solved without sorting the list again and again.

Start by finding the top ten items once. Let $X_{10}$ be the value of the tenth largest item.

If an item outside the top ten is changed to a value ≤ $X_{10}$, ignore it. If it is changed to a value > $X_{10}$, then drop the tenth item and insert the changed item in the array in the right position.

If an item in the top ten is changed then move it up or down according to the new value. If the new value is less than < $X_{10}$ then remove it from the top ten leaving you with the top nine, find the largest item that is currently not in the top nine, and put it into the tenth position.

So most of the time you do no work at all, a lot of the time very little work, and occasionally it takes linear time.

$\endgroup$
0
$\begingroup$

If your list of taxi numbers has only a few 'incorrect' positions that are close to their 'correct' sorted position, you could try to use insertion sort.

Although insertion sort is not very efficient to sort tributary lists, it works pretty well for almost sorted lists: if all elements in the list have distance of at most $k$, insertion sort takes only $O(kn)$ time to sort the list, for instance. Additionally, insertion sort is a rather simple algorithm, so you should be able to implement it yourself if there is no library function available.

$\endgroup$
0
$\begingroup$

As Billiska suggests, very good idea is to keep the balanced tree (Red Black, AVL), which gives $\mathcal O(\log n)$ per update. In case of monotonous increments, using the max-heap would be also viable option. If there is any known rate, it may be good idea to keep two separate trees, one with say twice amount of last top items and keeping those that would not bump into top-10 any time soon. It is more manual handling of the data, but it benefits vastly in the terms of time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.