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.
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...