What would be the most efficient method (no repeated command execution) to remove items listed in one file from another file (unordered) ?

One can easily get the list of non-matching items in the second file by

cat first_file.txt second_file.txt | sort | uniq -u

but that would also contain all unmatched items from the first file too... now what?


This awk program takes a single pass through each file:

awk '
    NR == FNR {f1[$0] = 1; next}
    !($0 in f1)
' file1 file2

comm is useful for this job. It does require it's input files to be sorted:

# output lines unique to file2
comm -13 <(sort file1) <(sort file2)
  • I have no idea of how !($0 in f1) works internally, I mean in inside awk. If it scans all the array simply, we should have over there O(n!). :-| sort it seems to be highly optimized... Do you have any reference about? – Hastur Sep 16 '15 at 15:53
  • the in operator tests if the left-hand operand is an index of the (associative or indexed) array. It should be an O(1) operation. For gawk, documented here: gnu.org/software/gawk/manual/html_node/… – glenn jackman Sep 16 '15 at 16:52
  • Thanks for the reference. in should scan the full array f1 not only one element, from here O(n^2) [BTW Errata in the previous comment O(n^2) and not O(n!)]. I did a test with 10^4 up to 10^6 random strings of 32 bytes and awk solution scales linearly: it has to be order inside. (comm solution is more vary 2x at 10^4, ~1x at 10^5 and 2x 10^6, but I suppose it depends from the memory available). – Hastur Sep 16 '15 at 17:52
  • Cool, I didn't know about comm. – dronus Sep 16 '15 at 20:45
  • the same thing can be done with grep like this: grep -v -f <(command1) <(command2) – Andy Jan 18 at 1:53

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.