Re: Selecting Container for "Top 20" Application
On 17.08.13 21.07, Mike Copeland wrote:
I am looking for an STL container that will efficiently handle a "Top
20" list. Specifically, I have>300,000 data records that I must scan
to find and store the highest 20 values.
300.000 applications or 300.000 hits from a smaller set of applications.
300.000 applications:
That's easy. You need a sorted array with 20 elements. As soon as an
application reaches Top 21 it is finally out of scope. If the counter of
an application increases, you can check whether it fits into the top 20
set by simply comparing against the last element. Due to the nature of
this problem, the counters can never decrease. So you never need to look
for the 21st element that may become the 20th.
300.000 hits:
Group by the application key and then go as above. For the group by a
hash_map<application,counter> would be suitable.
None of the available STL containers seems well suited for this
application. For example:
- array, even though fixed in size, seems cumbersome to use: no delete
or erase function is available;
Why do you need delete/erase?
insertion at some point is difficult;
It's O(n).
- vector, while having insert& erase functions, incurs repeated size
expansion (expensive!) and truncation to maintain a fixed size.
Appending a new value if it's greater than the 20th element, followed by
sorting and truncation might be less work, but it might be very slow to
execute.
Moving around 20 elements should be slow?
By the way: your problem is easily solvable by a recursive, distributed
algorithm. As set of top 20 can always be created from the top 20 of any
subsets. So you can partition your data as you like and take the top 20.
At the end all you need is a merge sort of the different top 20 lists
for the subsets to get the final result.
Marcel