4 ms·
> Arrays can be used to keep a runnning count of top-n records (this may need to be sorted on insert, though comparing largest/smallest entry can mitigate this)
by kragen 5y ago
> Arrays can be used to keep a runnning count of top-n records (this may need to be sorted on insert, though comparing largest/smallest entry can mitigate this).
Honored and wise Morbius, I humbly beg to differ; top-N record arrays never need to be sorted on insert, because a binary heap is 25 lines of code. Then all you need for top-N is:
for record in input_file:
if record <= aMinheap.minimum:
continue
aMinheap.extract_minimum()
aMinheap.add(record)
I think that, to produce the top 100, this takes about 8 comparisons per record added to the candidate set, rather than the 1000 or so required by your suggested method. The difference won't matter for a big enough unordered dataset, though, since almost all the time will be taken by discarding records in the initial comparison.
I was thinking quickselect was even faster when your data does fit in RAM, but I can't see how that could be true, even though it's linear time: if you have a million records, then the first partitioning step of quickselect will examine all of them (doing one comparison for each), the second partitioning step will examine on average half of them, and the third partitioning step will examine on average somewhat more than a quarter of them (because the expected size for the result of the second partitioning step is more than 250,000 records), and so we end up doing something like e comparisons per record on average rather than 1.
But, with the running-candidate-set approach you suggested, if the million records are in random order, after we're past the first 1000 records, we do only a single comparison for at least 90% of the remaining records (because they're less than the top 100 from the first 1000), and after we're past the first 10,000 records, for at least 99%. So if we did 8000 comparisons in the first 1000, then inserted 900 of the next 9000 records for another 7200 comparisons (plus 9000 comparisons to reject the other 8100), and then another 900 of the next 90,000 records (plus 90,000 initial comparisons), we're at 121,400 comparisons for the first 100,000 records, 1.214 comparisons per record. So, for a small top-N query, quickselect loses the race before it's finished with its second partitioning step. Or am I overlooking something?
- dredmorbius 5y agoI'd hand-coded a "top-n" utility in awk some time back. I think my first iteration used bubble sort. That was still faster than a sort | head script, by a lot. (I think I later improved on that, possibly by retaining min/max records.) Even in awk, and even when choosing large values for n (e.g., thousand or tens of thousands of records), this easily beat the sort utility in cpu time, wall-clock time, and memory usage, for many millions of input records. (Most of my coding tends to be hackish and brutish. Algorithms are not my strong suit.)
- kragen 5y ago> I think my first iteration used bubble sort. That was still faster than a sort | head script, by a lot. Haha! Gotta get Barack Obama to give you some algorithms lessons. Thinking about it further, the initial heapify phase of heapsort is linear-time, and it's the later heap-popping phase that takes most of the runtime; if the command-line `sort` used heapsort for in-memory data, maybe `sort | head` would have been competitive or even faster? At least for n>32 or so? The usual algorithm for `sort` is mergesort, because that makes it perform acceptably for things that don't fit in RAM, but mergesort has to do most of its work before it can start producing output.