Hi all,

What would be a good algorithm for finding the top 256 of a million
items?

I suppose the "top 256" list would remain sorted and any candidates
greater than the minimum would be inserted into the list. Would a
linear array be the best representation for this list?

-Brad

According to Brad Eckert tinyboot.com>:

It sure is simple enough. If you have n elements and want to keep the
top t, you should have something like O(t*log n) insertions. I am mostly
making this up, but the bottom line is that insertions shall be
sufficiently rare so that the cost of an insertion, even if it involves
moving O(t) elements, will be negligible next to the O(n) comparisons.

On Wed, 03 Sep 2008 07:05:21 -0700, Brad Eckert wrote:

Tony Hoare has a good algorithm, which is problem 9 in chapter 11 of Jon
Bently's Programming Pearls 2nd edition. It does require that you can
permute the elements, but it has expected O(n) running time.

It is a varient of quicksort.

Brad Eckert tinyboot.com> writes Re: Partial sorting

I don't think the top 256 need to be sorted, as a just-in-time linear
search for the minimum might be more efficient. A CS type should be
able to spew Forth the relevant O(n) numbers right away.

-marcel

mhx@iae.nl (Marcel Hendrix) wrote:

Yes. By the time you've checked the first 25000 records then the ones
you have will be around the top 1%%. From then on you'll be replacing
items less than 1%% of the time. So if you can do something to speed up
the case when you compare-and-discard it will probably have more effect
than speeding up the compare-and-replace.

Jonah Thomas gmail.com> writes Re: Partial sorting

Let's see. Both schemes (a = keep sorted, b = search) can cache the
current minimum, so searching candidates is equally fast.

In article <0e738bad-3556-447e-821f-56e9b4bf7ad2@59g2000hsb.googlegroups.com>,
Brad Eckert tinyboot.com> wrote:

A heap would be better, allowing for 8 instead of 128 moves.
But your algorithm would be order of a million anyway, and
the "top 256" list would affect only a small factor.
Most of the time you would be skipping numbers that would
not beat the worst of the "top 256" list anyway.

If you have a good sorting algorithm available to just sort
the million items, you may discover that it is hard to beat
it, even if it does more than necessary.

mhx@iae.nl (Marcel Hendrix) wrote:

Yes, and if you can find any way to speed up that part it can
potentially make a big difference. It happens about a million times and
the rest happens much fewer.

Are you figuring a maximum of 8 compares and so 4 compares on average?
But half the time it takes 8 compares, 1/4 the time it takes 7, 1/8 the
time it takes 6, etc.

You can build a binary tree with linked lists but then it isn't just a
linked list -- you have to rebuild the tree.

3 writes? Because you have the list ordered. That looks like a good
trade, 2 extra writes to avoid on average 128 compares.