Erik Wikström
10/16/2008 4:34:00 PM
On 2008-10-16 18:52, Giuliano Bertoletti wrote:
> Hello,
>
> I'm looking for a clever way to solve this problem.
>
> Suppose I've been given M > N items, each one with a score associated.
> I need to extract the top N items, sorted by score (decreasing order).
>
> The point is that I would typically have M >> N (far greater than) and I
> cannot simply store all M items in memory and perform a sort operation.
>
> I need to process items on the fly, as soon as I see them.
>
> My best guess is to use a list and delete items at the end as soon as
> its size grows larger than N, but I have a linear time item insertion
> (to keep it properly sorted) which I would like to avoid if possible.
>
> Any suggestions ?
Unless M is really huge and thus N quite large itself you probably will
not have to worry about the time used to manage the N largest elements,
since the time used to read the items from file will dominate.
Anyway, use a sorted container, such as std::set, or std::vector
together with push_heap()/pop_heap().
--
Erik Wikström