Sort and remove duplicates in place and recursively

Question

I would like to sort all files in all subdirectories in place. I have 65536 files in 256 directories, every file containing one word a line, and each file contains duplicates.

What I would like is to sort these with -u option (I don't know why but if I pipe sort to uniq -u command it actually removes unique lines that were duplicates, which is weird but anyway), but I don't want any ouput file, I want sort to read the files in memory, then overwrite them. I tried the -o option but it needs a filename.

Is there a way to perform this recursively ?

Thank you :)

Answer 1

That can be just:

find . -type f -size +1c -exec sort -uo {} {} ';'

(here skipping the files that are less than 2 byte large as you need at least 3 bytes to make two different lines, or possibly 2 for "\nx" which is an empty line followed by an undelimited line¹).

Beware the default sort order in sort is based on the locale's collation algorithm.

Two lines can sort the same even if they're not byte-to-byte identical, especially if the lines contain sequences of bytes that don't form valid characters, and also on GNU systems such as Debian on characters whose collation order is not defined.

You can do:

LC_ALL=C find . -type f -exec sort -uo {} {} ';'

Instead which on ASCII based systems (such as Debian on all architectures and kernels it's available for) will sort the lines by byte value instead of locale collation order (or IOW, the collation order of the C locale is based on byte value) and should guarantee that two byte-to-byte-different lines don't sort the same.

That runs one invocation of sort per file. To speed things up if the files are reasonably short, you could instead do with zsh:

zmodload zsh/mapfile
for f (**/*(N.)) print -rC1 -v 'mapfile[$f]' - ${(fou)mapfile[$file]}

Which avoids running an external sort command so many times and uses its o and u parameter expansion flag to sort and unique the lines instead. Note that it strips empty lines in the input if any, and skips hidden files (add the D glob qualifier if you want them).

Contrary to GNU sort -u, zsh won't consider as duplicate two strings that are not byte-to-byte identical (even if they sort the same), so you don't need to fix the locale to C there.

$ locale title charmap
English locale for Britain
UTF-8
$ a=(🧚 🧛)
$ print -rC1 - $a | sort -u
🧚  (oops, the vampire vanished as it sorted the same as the fairy)
$ print -rC1 - ${(ou)a}
🧚
🧛

As to your question about uniq -u, that's what it's for, uniq -u reports lines that are unique in the input. To remove duplicates, it's just sort | uniq. The complement of uniq -u would be uniq -D (report all duplicated lines).

GNU uniq used to report the first of sequences of lines that sort the same (so sort -u would be the same as sort | uniq). Newer versions report the first of sequences of identical lines, so sort | uniq cannot be used anymore if there can be different lines that sort the same.

Here, with newer GNU versions:

$ print -rC1 🧚 🧛 🧛 🧚 🧛 | sort | uniq
🧚
🧛
🧚
🧛

Since fairies and vampires sort the same in my locale, the sort result will be left as in the input (as GNU sort uses a stable sort algorithm), and uniq will only remove duplicates if the input happened to original contain adjacent duplicates.

What we can do though is first sort by byte value, and then by collation order before calling uniq:

LC_ALL=C sort | sort | LC_ALL=C uniq

Calling uniq under LC_ALL=C will make older and newer versions work the same.

---

^{sort does add back that newline character if it was missing in the input, in effect making a text file out of that non-text file. By skipping the 1-byte size files that contain non-newline bytes, that means those files are not fixed, so you may want to skip that optimisation if you still want the benefit of that text-file fixing, or extend the optimisation to -size +2c if you know all your files are properly formed text files.}

Answer 2

$ find . -type f -exec perl -MList::MoreUtils=uniq -i -0 -n -e \
    'print join("\n", uniq split /\n/), "\n"' {} +

This uses find to pass the filenames to a perl script which uses the -i edit-in-place option, and the List::MoreUtils to provide a uniq function to perl (perl has sort built-in, but not uniq). perl's -n option does pretty much the same thing as sed's -n option - it iterates over each input record, but prints nothing by default (i.e. it only prints what is explicitly printed).

The script sets the input record separator to NUL (with the -0 option) so it can slurp in each file in one go. Then it splits each input file by newlines, and prints them out in unique sorted order.

List::MoreUtils is in the liblist-moreutils-perl package on Debian (and Ubuntu, Mint, etc), and probably has a similar package name on Fedora, Centos, and maybe RHEL. Other distros probably have it packaged too. Otherwise install it from CPAN.

If you don't want to (or can't) install List::MoreUtils, you can use an associative array (aka "hash") instead. e.g.

$ find . -type f -exec perl -i -0 -n -e \
    '%uniq = map {$_ => 1} split /\n/;
     print join("\n", sort keys %uniq), "\n"' {} +

I'd run either of these on some junk files first, to make sure that it does what you want. And/or test it without the -i option so it just prints to stdout. I tested it on a file called junk that had the contents:

6
5
5
4
3
2
1
1

after running either of the versions above, junk contained:

1
2
3
4
5
6

If you want them in reverse sorted order, you can add reverse before either the sort or uniq function. e.g. print join("\n", reverse sort keys %uniq),"\n".

---

Alternatively, if you have sponge from Joey Hess's moreutils installed, you can use find, shell, sort -u, and sponge:

find . -type f -exec sh -c \
  'for f in "$@"; do sort -u "$f" | sponge "$f" ; done' find-sh {} +

This will be significantly slower than the perl version because the sh has to fork sort and sponge once for each input file, instead of perl being forked just once(*) by find to process all of the input files.

(*) assuming all the filenames fit into one command line. On Linux, that's about 2 million characters worth. If all the filenames combined are longer than that, it might have to fork perl two or three times (or maybe more).

The same applies to sh being forked by find, it might need to be forked more than once - but the cost of forking sh (or perl) a few times is negligible compared to the cost of forking sort and sponge once for each file. The time saving comes from using + with find ... -exec ... {} instead of \;.