Poprawa wydajności grepowania ponad dużym plikiem

10

Mam FILE_A, który ma ponad 300 000 linii i FILE_B, który ma ponad 30 milionów linii. Utworzyłem skrypt Bash, który przechwytuje każdą linię w pliku FILE_A w pliku FILE_B i zapisuje wynik polecenia grep w nowym pliku.

Cały ten proces trwa ponad 5 godzin.

Jak mogę poprawić wydajność mojego skryptu?

Używam grep -F -m 1jako polecenia grep. FILE_A wygląda następująco:

123456789 
123455321

a FILE_B wygląda następująco:

123456789,123456789,730025400149993,
123455321,123455321,730025400126097,

Tak więc w Bash mam whilepętlę, która wybiera następną linię w FILE_A i greps w FILE_B. Kiedy wzorzec zostanie znaleziony w PLIKU_B, zapisuję go w pliku wynikowym.txt.

while read -r line; do
   grep -F -m1 $line 30MFile
done < 300KFile
rogerio_marcio
źródło

Odpowiedzi:

17

Spróbuj użyć grep --file==FILE_A. Niemal na pewno ładuje wzorce do pamięci, co oznacza, że ​​skanuje PLIK_B tylko raz.

grep -F -m1 --file==300KFile 30MFile
Gort the Robot
źródło
To działałoby tylko przy założeniu, że mam wystarczającą ilość pamięci, prawda?
rogerio_marcio
Szczerze mówiąc, nie wypróbowałem tego sam na plikach tej wielkości, ale uważam, że powinno to znacznie poprawić twoją szybkość. Jeśli korzystasz z nowoczesnego komputera, nie powinieneś mieć problemów z przechowywaniem pliku 300K w pamięci. (Lub 30M za to.)
Gort the Robot
kiedy użyłem opcji -f (--file), po prostu odtworzyłem plik 30M. czy robię coś źle?
rogerio_marcio
Hmmm ... może plik 300K miał pustą linię?
Gort the Robot
na miejscu! to było to! działało idealnie, zakończyło się w 30 sekund! Dziękuję Ci!!
rogerio_marcio
2

Oto odpowiedź Perla na potomstwo. Rutynowo robię to w celu dopasowania linii 1M do linii 30-35M. Zakończenie zajmuje około 10 sekund.

Najpierw haszuj FILE_A:

my %simple_hash;
open my $first_file, '<', 'FILE_A' or die "What have you done?! $!";
while (<$first_file>) {
  chomp;                 ## Watch out for Windows newlines
  $simple_hash{$_} = 1;  ## There may be an even faster way to define this
}
close $first_file;

Następnie, jeśli twój duży plik jest rozdzielany i wiesz, po której kolumnie chcesz szukać, po prostu sprawdź, czy istnieje klucz skrótu podczas uruchamiania FILE_B, co jest znacznie, dużo szybsze niż sprawdzanie równości lub dopasowania wyrażeń regularnych:

open my $second_file, '<', 'FILE_B' or die "Oh no, not again.. $!";
while (<$second_file>) {
  my ($col1, undef) = split ',';
  if (exists($simple_hash{$col1}) {
    print $_;
  }
}
close $second_file;

Jeśli większy plik docelowy nie daje się łatwo przeanalizować, skrypt traci swoją wartość, ponieważ duża część jego szybkości wynika z konieczności uruchamiania silnika wyrażeń regularnych .

Mintx
źródło
1

Jeśli nie masz nic przeciwko bardziej zaangażowanemu programowaniu, rozważ użycie drzewa sufiksów (lub jego wariantu).

Możesz wstępnie przetwarzać FILE_Bprzy użyciu algorytmu Ukkonen w czasie liniowym. Następnie przeszukujesz każdą linię w FILE_Aczasie liniowo wzdłuż linii i otrzymujesz wszystkie pasujące numery linii (może być konieczne dostosowanie drzewa tad), które możesz zapisać do pliku wynikowego.

Cała procedura przebiega w czasie O (n + Nm), jeśli n jest długością FILE_B, Njest liczbą linii FILE_Awm, a m jest długością najdłuższej linii w FILE_A- jest to zasadniczo liniowy czas działania. Pokonuje kwadratowy czas, jakiego potrzebuje twoje oryginalne podejście pod względem wielkości.

Raphael
źródło
1

--mmapOstatnio znalazłem flagę, nie miałem okazji jej przetestować, ale z przyjemnością usłyszę o twoich ustaleniach. Oto opis ze strony man:

--mmap If  possible, use the mmap(2) system call to read input, instead
      of the default read(2) system call.  In some situations,  --mmap
      yields  better performance.  However, --mmap can cause undefined
      behavior (including core dumps) if an input file  shrinks  while
      grep is operating, or if an I/O error occurs.

Zobacz to lub to, aby uzyskać dodatkowe informacje na temat mmap.

Ramzi Kahil
źródło
Zdecydowanie dam temu szansę i dam ci znać, jak to wygląda. Jak prawdopodobne jest, że napotkam zrzut rdzenia?
rogerio_marcio
@rogerio_marcio Cóż, jak rozumiem tego człowieka, „jeśli plik kurczy się podczas działania grep lub jeśli wystąpi błąd we / wy.”. Raczej nie, ale powinieneś to wiedzieć lepiej. (Jeśli, jak zakładam, plik jest nietknięty podczas grep - to nie powinno się zdarzyć)
Ramzi Kahil
Do testowania tej --mmapdawki niczego nie zrzucam, zalecałbym bieg z --mmap, i jeden bez. A potem użyj, wcaby zobaczyć, że masz taką samą moc wyjściową - to powinien być solidny test, biorąc pod uwagę, że uruchomiliśmy 2 razy grep, a tylko flaga się różniła.
Ramzi Kahil
@rogerio_marcio Czy próbowałeś tego? Jakieś spostrzeżenia?
Ramzi Kahil,
-1

dlaczego nie umieścisz tego pliku w bazie danych, bazy danych są naprawdę dobre w wykonywaniu efektywnego łączenia, mieszania, łączenia zagnieżdżonego w ten sposób. I są naprawdę dobrzy w wykorzystaniu pamięci wirtualnej

Andyz Smith
źródło
Wszystko, co robisz z pozostałymi odpowiedziami, to wynalezienie koła bazy danych
Andyz Smith