Znajdź identyfikatory w jednym pliku, których nie ma w innym

Mam dwa pliki:

abc.txt

abcd
xyz
pqrs

mno.txt

zzon
mkno
abcd

• Chcę sprawdzić, czy w pliku mno.txt znajduje się „abcd” .
• Nie jest konieczne, aby jeśli „abcd” było pierwsze w abc.txt , będzie również pierwsze w mno.txt .
• W obu plikach są tysiące takich identyfikatorów.
• Chcę również sprawdzić, ile identyfikatorów nie ma w mno.txt, które są w abc.txt .

W jaki sposób mogę to zrobić ?

Jeśli twoim celem jest znalezienie wspólnych lub nietypowych linii, commpolecę tutaj.

Porównuje dwa pliki i pokazuje - w trzech kolumnach - linie, które są unikalne dla pliku 1, linie, które są unikalne dla pliku 2 oraz linie, które pojawiają się odpowiednio w obu plikach. Możesz przekazać flagi, aby ukryć dowolne z tych danych wyjściowych. Np. comm -1 file1 file2Pominie pierwszą kolumnę, rzeczy unikalne dla file1. comm -12 file1 file2pokaże tylko rzeczy w obu plikach.

Jest jedno duże zastrzeżenie: dane wejściowe muszą być posortowane. Możemy to obejść.

To pokaże ci wszystko w abc, którego nie ma w mno:

comm -23 <(sort abc.txt) <(sort mno.txt)

Możesz wc -lto przeliczyć, żeby policzyć.

Powodem commjest to, że po posortowaniu plików porównanie obok siebie jest bardzo proste obliczeniowo. Jeśli masz do czynienia z milionami tych, to zrobi różnicę.

Można to wykazać za pomocą kilku próbnych plików. Mam dość szybki komputer, więc aby pokazać różnicę między podejściami, potrzebuję całkiem dużego zestawu próbek. Poszedłem do 10 milionów 10-znakowych ciągów na plik.

$ cat /dev/urandom | tr -dc '0-9' | fold -w 10 | head -10000000 > abc.txt
$ cat /dev/urandom | tr -dc '0-9' | fold -w 10 | head -10000000 > mno.txt

$ time comm -23 <(sort abc.txt) <(sort mno.txt) | wc -l
... 0m10.653s

$ time grep -Fcxv -f abc.txt mno.txt
... 0m23.920s

$ time grep -Fcwv -f abc.txt mno.txt
... 0m40.313s

$ time awk 'NR==FNR{a[$0]++};NR!=FNR && a[$0]' abc.txt  mno.txt | wc -l
... 0m12.161s

Sortowanie zajmuje mi większość czasu. Jeśli udajemy, że abc.txt jest statyczny, możemy go wstępnie posortować, co znacznie przyspieszy przyszłe porównania:

$ sort abc.txt abc-sorted.txt
$ time comm -23 abc-sorted.txt <(sort mno.txt) | wc -l
... 0m7.426s

Możesz na nie spojrzeć i uznać kilka sekund za nieistotne, ale muszę podkreślić, że działają one na wysokiej klasy komputerze. Jeśli chcesz to zrobić na (np.) Raspberry Pi 3, będziesz patrzył na znacznie wolniejsze zwroty, a różnica wzrośnie do punktu, w którym rzeczywiście ma znaczenie.

aby uzyskać listę:

grep -Fwf abc.txt mno.txt

daje ci coś podobnego do:

abcd
abcd
zef

jeśli chcesz uzyskać unikalną listę, użyj jej w następujący sposób:

grep -Fwf abc.txt mno.txt | sort | uniq

i uzyskać liczby:

grep -Fcwv -f abc.txt mno.txt

• -F oznacza: interpretuj WZÓR jako listę stałych ciągów zamiast wyrażeń regularnych.
• -fuzyskaj wzory z PLIKU, który będzie abc.txt.
• szukamy mno.txtwzorów
• -c Policz liczbę dopasowań
• -wSzukaj tylko „całych słów”: pasujące podłańcuchy muszą znajdować się na początku wiersza lub poprzedzone znakiem składającym się z innych słów. Podobnie musi znajdować się na końcu wiersza lub musi zawierać znak nie będący składnikiem. Znaki składające się na słowo to litery, cyfry i znak podkreślenia.
• -v Cofnij wyszukiwanie

Przy pomocy awk możemy wykonać zadanie, przekazując dwa pliki, najpierw plik sygnatur, a następnie plik, który chcemy sprawdzić. Kiedy czytamy pierwszy plik, wiemy o tym NR==FNRi wtedy możemy wczytywać linie do tablicy. Kiedy NR!=FNRsprawdzamy, czy ustawiona jest tablica dla takiej linii.

$ cat abc.txt                                                      
abcd
xyz
pqrs
$ cat mno.txt                                                      
zzon
xyz
mkno
abcd
$ awk 'NR==FNR{a[$0]++};NR!=FNR && a[$0]' abc.txt  mno.txt         
xyz
abcd

I odwrotnie, możemy zanegować wzór, aby wydrukować te linie, których nie ma abc.txt

$ awk 'NR==FNR{a[$0]++};NR!=FNR && ! a[$0]' abc.txt  mno.txt       
zzon
mkno

A jeśli chcemy wydrukować liczbę osób, które możemy zatrudnić sorti wc:

$ awk 'NR==FNR{a[$0]++};NR!=FNR && ! a[$0]' abc.txt  mno.txt | sort -u | wc -l         
2

Jeśli jedna z list słów nie jest posortowana, szybsze byłoby użycie wydajnej struktury danych do zapamiętania typowych słów.

Pyton

#!/usr/bin/env python3
import sys

with open(sys.argv[1]) as minuend_file:
    minuend = frozenset(map(str.rstrip, minuend_file))
with open(sys.argv[2]) as subtrahend_file:
    subtrahend = frozenset(map(str.rstrip, subtrahend_file))

difference = minuend - subtrahend
#print(*difference, sep='\n') # This prints the content of the set difference
print(len(difference)) # This prints the magnitude of the set difference

Stosowanie:

python3 set-difference.py abc.txt mno.txt

Python (bardziej wydajny)

Jeśli chcesz zaoszczędzić trochę pamięci na pamięć pośrednią i czas działania, możesz użyć tego nieco trudniejszego do zrozumienia programu:

#!/usr/bin/env python3
import sys

with open(sys.argv[1]) as minuend_file:
    minuend = set(map(str.rstrip, minuend_file))
with open(sys.argv[2]) as subtrahend_file:
    subtrahend = map(str.rstrip, subtrahend_file)
    minuend.difference_update(subtrahend)
    difference = minuend
    del minuend

#print(*difference, sep='\n') # This prints the content of the set difference
print(len(difference)) # This prints the magnitude of the set difference

Wydajność

Biorąc pod uwagę, abc.txtoraz mno.txtz 1 mln nieposortowane linii 10 losowych znaków ASCII cyfr każda (patrz odpowiedź Oli za set-up):

$ time python3 set-difference.py abc.txt mno.txt
user    0m10.453s

vs.

$ export LC_COLLATE=C
$ time sort abc.txt > abc_sorted.txt
user    0m10.652s
$ time sort mno.txt > mno_sorted.txt
user    0m10.767s
$ time comm -23 abc_sorted.txt mno_sorted.txt | wc -l
9989882
user    0m1.600s

łącznie: 23 sekundy