8

I have ~30k files. Each file contains ~100k lines. A line contains no spaces. The lines within an individual file are sorted and duplicate free.

My goal: I want to find all all duplicate lines across two or more files and also the names of the files that contained duplicated entries.

A simple solution would be this:

cat *.words | sort | uniq -c | grep -v -F '1 '

And then I would run:

grep 'duplicated entry' *.words

Do you see a more efficient way?

  • 1
    As a side note, shell commands may not be the greatest tool if your aim is performance – Ikaros Feb 12 '18 at 13:32
  • 3
    @Ikaros citation needed. The shell is slow, yes, but these are utilities written in C and are usually the fastest way available. It will not be easy to beat this sort of pipeline for speed unless you go and write a dedicated C program. – terdon Feb 12 '18 at 17:08
  • Ah, just your basic 30,000-tape merge algorithm. :-) – Lee Daniel Crocker Feb 12 '18 at 18:16
10

Since all input files are already sorted, we may bypass the actual sorting step and just use sort -m for merging the files together.

On some Unix systems (to my knowledge only Linux), it may be enough to do

sort -m *.words | uniq -d >dupes.txt

to get the duplicated lines written to the file dupes.txt.

To find what files these lines came from, you may then do

grep -Fx -f dupes.txt *.words

This will instruct grep to treat the lines in dupes.txt (-f dupes.txt) as fixed string patterns (-F). grep will also require that the whole line matches perfectly from start to finish (-x). It will print the file name and the line to the terminal.

Non-Linux Unices (or even more files)

On some Unix systems, 30000 file names will expand to a string that is too long to pass to a single utility (meaning sort -m *.words will fail with Argument list too long, which it does on my OpenBSD system). Even Linux will complain about this if the number of files are much larger.

Finding the dupes

This means that in the general case (this will also work with many more than just 30000 files), one has to "chunk" the sorting:

rm -f tmpfile
find . -type f -name '*.words' -print0 |
xargs -0 sh -c '
    if [ -f tmpfile ]; then
        sort -o tmpfile -m tmpfile "$@"
    else
        sort -o tmpfile -m "$@"
    fi' sh 

Alternatively, creating tmpfile without xargs:

rm -f tmpfile
find . -type f -name '*.words' -exec sh -c '
    if [ -f tmpfile ]; then
        sort -o tmpfile -m tmpfile "$@"
    else
        sort -o tmpfile -m "$@"
    fi' sh {} +

This will find all files in the current directory (or below) whose names matches *.words. For an appropriately sized chunk of these names at a time, the size of which is determined by xargs/find, it merges them together into the sorted tmpfile file. If tmpfile already exists (for all but the first chunk), this file is also merged with the other files in the current chunk. Depending on the length of your filenames, and the maximum allowed length of a command line, this may require more or much more than 10 individual runs of the internal script (find/xargs will do this automatically).

The "internal" sh script,

if [ -f tmpfile ]; then
    sort -o tmpfile -m tmpfile "$@"
else
    sort -o tmpfile -m "$@"
fi

uses sort -o tmpfile to output to tmpfile (this won't overwrite tmpfile even if this is also an input to sort) and -m for doing the merge. In both branches, "$@" will expand to a list of individually quoted filenames passed to the script from find or xargs.

Then, just run uniq -d on tmpfile to get all line that are duplicated:

uniq -d tmpfile >dupes.txt

If you like the "DRY" principle ("Don't Repeat Yourself"), you may write the internal script as

if [ -f tmpfile ]; then
    t=tmpfile
else
    t=/dev/null
fi

sort -o tmpfile -m "$t" "$@"

or

t=tmpfile
[ ! -f "$t" ] && t=/dev/null
sort -o tmpfile -m "$t" "$@"

Where did they come from?

For the same reasons as above, we can't use grep -Fx -f dupes.txt *.words to find where these duplications came from, so instead we use find again:

find . -type f -name '*.words' \
    -exec grep -Fx -f dupes.txt {} +

Since there is no "complicated" processing to be done, we may invoke grep directly from -exec. The -exec option takes a utility command and will place the found names in {}. With + at the end, find will place as many arguments in place of {} as the current shell supports in each invocation of the utility.

To be totally correct, one may want to use either

find . -type f -name '*.words' \
    -exec grep -H -Fx -f dupes.txt {} +

or

find . -type f -name '*.words' \
    -exec grep -Fx -f dupes.txt /dev/null {} +

to be sure that filenames are always included in the output from grep.

The first variation uses grep -H to always output matching filenames. The last variation uses the fact that grep will include the name of the matching file if more than one file is given on the command line.

This matters since the last chunk of filenames sent to grep from find may actually only contain a single filename, in which case grep would not mention it in its results.


Bonus material:

Dissecting the find+xargs+sh command:

find . -type f -name '*.words' -print0 |
xargs -0 sh -c '
    if [ -f tmpfile ]; then
        sort -o tmpfile -m tmpfile "$@"
    else
        sort -o tmpfile -m "$@"
    fi' sh 

find . -type f -name '*.words' will simply generate a list of pathnames from the current directory (or below) where each pathnames is that of a regular file (-type f) and that has a filename component at the end that matches *.words. If only the current directory is to be searched, one may add -maxdepth 1 after the ., before -type f.

-print0 will ensure that all found pathnames are outputted with a \0 (nul) character as delimiter. This is a character that is not valid in a Unix path and it enables us to process pathnames even if they contain newline characters (or other weird things).

find pipes its output to xargs.

xargs -0 will read the \0-delimited list of pathnames and will execute the given utility repeatedly with chunks of these, ensuring that the utility is executed with just enough arguments to not cause the shell to complain about a too long argument list, until there is no more input from find.

The utility invoked by xargs is sh with a script given on the command line as a string using its -c flag.

When invoking sh -c '...some script...' with arguments following, the arguments will be available to the script in $@, except for the first argument, which will be placed in $0 (this is the "command name" that you may spot in e.g. top if you are quick enough). This is why we insert the string sh as the first argument after the end of the actual script. The string sh is a dummy argument and could be any single word (some seem to prefer _ or sh-find).

  • At the end of your 1st block of shell script, what is the use of fi' sh? – dan Feb 12 '18 at 11:22
  • @danielAzuelos The fi is the end of the if statement in the "internal" sh shell script. The ' ends that shell script (the whole script is a singly quoted string). The sh will be passed to the internal script in $0 (not part of $@, which will contain the filenames). In this instance, that sh string may actually be any word. If leaving out sh at the end, the first filename would be passed in $0 and would not be part of the processing that the internal shell script is doing. – Kusalananda Feb 12 '18 at 11:26
  • 1
    Nice answer. My question was about the sh at the end. May I suggest you to explain its function in xargs. I think it might help many of us. – dan Feb 12 '18 at 14:51
  • @danielAzuelos I have now expanded on the answer. – Kusalananda Feb 12 '18 at 16:25
  • 1
    Great answer, thank you . I'll remove all my now useless comments. – dan Feb 12 '18 at 16:57
8

The lines within an individual file are sorted and duplicate free.

Which means you probably might find some use for sort -m:

 -m, --merge
        merge already sorted files; do not sort

The other obvious alternative to doing this would be a simple awk to collect the lines in an array, and count them. But as @dave_thompson_085 commented, those 3 000 million lines (or however many unique ones there are) would likely take some considerable amount of memory to store, so that may not work very well.

  • Since the awk won't sort the 3 M lines, I bet it should be much faster. – dan Feb 11 '18 at 23:34
  • @danielAzuelos Merging sorted files has linear time complexity. Besides, what would you have awk do, that would be so different? – T. Verron Feb 12 '18 at 9:47
  • You are right, uniq -d will be faster. – dan Feb 12 '18 at 11:20
  • just what i wanted – Edwin Ikechukwu Feb 12 '18 at 16:25
3

With awk you can get all repeated lines in all files in one short command:

$ awk '_[$0]++' *.words

But it will repeat lines if a line exist 3 or more times.
There is a solution to get only the first duplicate:

$ awk '_[$0]++==1' *.words

It should be pretty quick (if repeats are few) but will eat a lot of memory to keep all lines in memory. Maybe, depending on your actual files and repeats, try with 3 or four files first.

$ awk '_[$0]++==1' [123]*.words

Otherwise, you can do:

$ sort -m *.words | uniq -d

Which will print uniq repeated lines.

  • 2
    +1 for sort -m * | uniq -d – Jeff Schaller Feb 12 '18 at 1:19
  • awk can avoid the repeats with 'x[$0]++==1' but will indeed need a lot of memory; if the 3G lines have say 1G distinct values, and if your awk needs say 50 bytes for a hasharray entry mapping a (presumably shortish) string to the uninit value, that's 50GB. For sorted input, you can do uniq -d manually with awk '$0==p&&n++==1;$0!=p{p=$0;n=1}' but why bother? – dave_thompson_085 Feb 12 '18 at 4:30
  • @dave_thompson_085 Thanks for the concept of ==1, great idea. – Isaac Feb 12 '18 at 4:45
  • Assuming 30000 files with 100000 lines of 80 characters each and no duplicates, this will require awk to store 2.4E11 bytes (223 GiB). – Kusalananda Feb 12 '18 at 7:31
  • sort -m *.words | uniq -d works great! After the process I run grep to find a files that contain a duplicated entry. Do you see a way to print the at least one filename that contains a duplicated entry? – Lars Schneider Feb 12 '18 at 12:15
3

Optimized sort + uniq solution:

sort --parallel=30000 *.words | uniq -d
  • --parallel=N - change the number of sorts run concurrently to N
  • -d, --repeated - only print duplicate lines, one for each group

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.