2 ms·
The best thing to do when it comes to sorting data is to not do that. Sorts frequently are used in merges or to find some top-n / bottom-n instance rate. If y
by dredmorbius 5y ago
The best thing to do when it comes to sorting data is to not do that. Sorts frequently are used in merges or to find some top-n / bottom-n instance rate.
If you've got to sort (or writing an alternative is too time-consuming), do it after eliminating as much data (variables, records) as possible.
Hash tables (or other comparable tools such as btrees or Bloom filters) can be used for dataset comparisons or key-value lookups.
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).
Random sampling is very often as good as complete processing, especially where the goal is to find the general characteristics of a dataset rather than an exhaustive view or precise tabulation. Even in accounting and financial operations, sampling methods may be acceptable (see for example, mechanical copyright royalties on performance of recorded music broadcasts, or advertising and circulation rates in publishing). It's fairly staggering how clearly a small sample (as few as 30 records, often only a few hundred or thousand) can describe an immense dataset (millions or billions of entries) with reasonable accuracy, so long as it is randomly selected. And if the first sample seems off, try pulling a few others and seeing how they compare. (Effectively: Monte Carlo method.)
The place where sampling methods break down most is in iterative-calculation forecasts (e.g., weather modeling), where larger aggregations (typically measured as datapoints over both area and time) greatly reduce accuracy. Though even with very precise reporting density, today's weather forecasts tend to be limited to 7--10 days. Sometimes randomness simply wins.
- 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.