The general point is true, but the shell pipeline gets a lot more elegant if you use the sort-and-accumulate paradigm that the classic shell utilities were written for (which uses O(1) memory, by sorting on disk). Using mostly the author's own code, and adding --count to uniq:

    tr < README.md --complement --squeeze-repeats '[:alpha:]' '\n' \
    | tr A-Z a-z \
    | nl \
    | sort --key=2,2 --key=1,1n \
    | uniq --skip-fields=1 --count \
    | sort --key=2,2n \
    | awk '{ print $3, $1 }'

(Where the final awk papers over the fact that we're mixing tabs and spaces here; obviously, awk is also good at doing the accumulation step, but uniq --count suffices here.)

(I originally posted the above as a comment on lobste.rs, on this same article.)

▲ FattiMei 3 hours ago | parent [-]

Very interesting solution, and in the spirit of the original article. If I understood the snippet right, you are sorting the input sequence on the first column (the words) and then on the second one (the frequencies)

It is nevertheless "complecting": the uniq assumes the data is sorted and the columns of your data structure move together. Maybe this algorithm is already complex regardless of the implementation.

btw, this paradigm reminds me of APL

	▲	JoachimSchipper 2 hours ago \| parent \| next [-]
		The sort is on line numbers, as aozgaa said. Again, the paradigm here - and this is designed for a different time - is that your data most definitely does not fit in RAM, so you use sort(1) to sort on disk and run your software using only constant memory. (In modern software, databases can and do sort on disk, but few programs do.) In detail, for input "foo bar FOO qux FOO foo", we convert to [1 foo, 2 bar, 3 foo, 4 qux, 5 foo, 6 foo] (with newlines instead of commas, obviously), then sort by word (then line number) to [2 bar, 1 foo, 3 foo, 5 foo, 6 foo, 4 qux] at which point the uniq invocation gives <count> <first_line> <word>, i.e. [1 2 bar, 4 1 foo, 1 4 qux] albeit with an ugly mix of tabs and spaces. One final sort by <first_line> gives us [4 1 foo, 1 2 bar, 1 4 qux] and then it's just a matter of formatting the output: [foo 4, bar 1, qux 1] The generally-useful point is that the classic shell utilities really do work pretty well if you're operating within their paradigm, which isn't "throw everything in a hash table". (That's the paradigm of later scripting languages.)
	▲	aozgaa 3 hours ago \| parent \| prev [-]
		the point is to do a stable sort on (word, line number) lexicographically, then when we do "uniq" we can take the first line number. In contrast to the "we need a frequency table" idea in the article, this solution trades off memory by transferring all the line numbers in the stream. This is very much in the spirit of the infamous McIlroy/Knuth "bakeoff"[1] -- tradeoff some efficiency (via extra book-keeping or sorts) in return for composability. Agreed, very neat. [1] https://homepages.cwi.nl/~storm/teaching/reader/BentleyEtAl8...