2 ms·
I'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
by dredmorbius 5y ago
I'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.