11 Mar
2020
11 Mar
'20
12:42 a.m.
This begs questions of stability
Astute question. I had that in my original draft, but eliminited
it for what I thought was clarity. Anyway, depending on implementation
of sort, you may need sort -s. Of course it doesn't matter which copy
among several equal lines uniq produces, nor does it matter in sort
when there are no comparison options--they're all the same.
I don't know enough about the
internals of sed to know even what algorithm it uses
(... a disk-based merge sort?)
sed is not a sorting program--basically it copies input to
output, making line-by-line editing changes. That's the
way I meant to use it in sed s/nonkeys//|sort -keys|uniq.
(I have added options to sort, hopefully for clarity).
The argument to sed here means substitute the empty
string for the nonkey fields (specified by a regular expression).
If "sed" was a typo for "sort", all versions of sort that
I know of use an internal sorting algorithm for big chunks
of the file, then combines the chunks by merge. But internal
sorting varies all over the map--variations on quicksort,
radix sort, merge sort, ...
Doug
11 Mar
11 Mar
1:38 a.m.
New subject: Command line options and complexity
On Tue, Mar 10, 2020 at 2:43 PM Doug McIlroy <doug(a)cs.dartmouth.edu> wrote:
Thanks. That's interesting.
Did `sort -s` come later? The idea that you preferred clarity over
stability for `sort -u` would indicate so, otherwise one might imagine that
`-u` would just imply `-s` and that would be that.
This begs
questions of stability
Astute question. I had that in my original draft, but eliminited
it for what I thought was clarity. Anyway, depending on implementation
of sort, you may need sort -s. Of course it doesn't matter which copy
among several equal lines uniq produces, nor does it matter in sort
when there are no comparison options--they're all the same.
I don't know enough about the
`sed` in my email was a typo, as you speculated below.
Interestingly, this `sed` construction prior to `sort` loses information,
which perhaps doesn't matter in any given specific case, but is
insufficient in general, which I gathered to be the entire reason you
implemented `sort -u`.
If "sed" was a typo for "sort",
It was.
all versions of sort that
internals of sed to know even what algorithm it
uses
(... a disk-based merge sort?)
sed is not a sorting program--basically it copies input to
output, making line-by-line editing changes. That's the
way I meant to use it in sed s/nonkeys//|sort -keys|uniq.
(I have added options to sort, hopefully for clarity).
The argument to sed here means substitute the empty
string for the nonkey fields (specified by a regular expression).
I know of use an internal sorting algorithm for big
chunks
of the file, then combines the chunks by merge. But internal
sorting varies all over the map--variations on quicksort,
radix sort, merge sort, ...
It's the details of the internal sorts that are most interesting in some
sense, as the merges are probably fairly straight forward but the internal
sorts will affect stability and have other interesting characteristics.
As an aside, one must imagine that, in this day and age, a "big chunk" is
probably big enough to hold the vast majority of files entirely in RAM, and
only exceptionally large files actually require merging multiple blocks.
- Dan C.
1748
days inactive
1748
days old
1 comments
2 participants
participants (2)
-
Dan Cross -
Doug McIlroy