Muszę deduplikować dużą listę słów. Wypróbowałem kilka poleceń i przeprowadziłem badania tutaj i tutaj, w których wyjaśniają, że najszybszym sposobem na zduplikowanie listy słów wydaje się być użycie awk.
awk -> O (n)? sort -> O (n log n)?
Stwierdziłem jednak, że to nieprawda. Oto moje wyniki testów:
sort -u input.txt -o output.txt
rzeczywisty 0m12.446s
użytkownik 0m11.347s
sys 0m0.906s
awk '!x[$0]++' input.txt > output.txt
rzeczywisty 0m47.221s
użytkownik 0m45.419s
sys 0m1.260s
Zatem użycie sort -u jest 3,7 razy szybsze. Dlaczego to? czy istnieje jeszcze szybsza metoda przeprowadzenia deduplikacji?
*********** Aktualizacja ********
Jak ktoś zauważył w komentarzach, być może moja lista słów była już do pewnego stopnia posortowana. Aby wykluczyć tę możliwość, wygenerowałem dwie listy słów za pomocą tego skryptu python .
List1 = 7 Mb
List2 = 690 Mb
Wyniki AWK:
List1
rzeczywisty 0m1.643s
użytkownik 0m1.565s
sys 0m0.062s
List2
real 2m6.918s
użytkownik 2m4.499s
sys 0m1.345s
Sort:
listy1
prawdziwych 0m0.724s
0m0.666s użytkownik
SYS 0m0.048s
List2
real 1m27.254s
użytkownik 1m25.013s
sys 0m1.251s
źródło
Odpowiedzi:
Zadajesz niewłaściwe pytanie lub niewłaściwie zadajesz to pytanie i na niewłaściwym stosie, to jest lepsze pytanie, które należy zadać podczas programowania / przepełnienia stosu, aby ludzie udzielali odpowiedzi na podstawie algorytmów używanych w awk i sortowaniu.
PS: rób także potrzebne nawk, mawk i gawk, aby dać nam więcej szczegółów na „strefę do”;) i wykonuj przebiegi jak 100 razy każdy z minimalną, maksymalną, średnią i odchyleniem standardowym.
W każdym przypadku wracając do pytania, od CompSci 210, chodzi o zastosowane algorytmy. Sortowanie korzysta z kilku, w zależności od rozmiarów i ograniczeń pamięci, które trafiły, aby zapisać pliki na dysku w plikach tymczasowych do scalenia posortowane, gdy zabraknie pamięci, i będziesz musiał zajrzeć do kodu źródłowego, aby zobaczyć, co polecenie konkretne sort (1) używa w konkretnym systemie operacyjnym, na którym go uruchomiłeś, ale z doświadczenia ładuje się do pamięci tak dużo, jak to możliwe, wykonaj szybkie sortowanie, wypisz na dysk, powtórz płukanie i na koniec zrobi scalanie małych posortowanych plików. Więc tutaj będziesz mieć O (n * log2 (N)) dla części, a następnie przybliżoną operację scalania O (n * log (n))
awk: Mechanizm x [$ 0] ++ „przypuszcza”, że używa skrótu. Ale problem z haszowaniem, rzekomą operacją „wyszukiwania” O (1), są kolizje i obsługa kolizji. Może to powodować problem, gdy dane nie są ładnie rozłożone, nie wypełniają wiader itp., A na dużych listach haszowanie może być dużym problemem z pamięcią, jeśli obsługa kolizji nie jest wykonana poprawnie (i może być konieczne dostroić algorytmy mieszające dla oczekiwanych danych), a następnie trzeba spojrzeć na wydajność rzeczywistych funkcji mieszających, a następnie O (1) może być bliższe O (log (n)) dla wstawek (tj. O (1) dla pierwszego wyszukiwania, a jeśli NIE istnieje, dodajesz je, które może być O (log (n))), a następnie n * O (1) staje się * O (log (n)) = > O (n * log (n)), nie wspominając o tym, że robisz również rzeczy w „interpretowany” sposób :)
źródło
Różnica prędkości wynika z tego, że „sort” to polecenie ( link ), podczas gdy „awk” to język programowania ( link ).
Polecenie „sort” pobiera dane wejściowe i zwraca dane wyjściowe. Natomiast „awk” jest językiem programowania, który najpierw interpretuje kod (polecenie terminala), a następnie rozpoczyna przetwarzanie na nim. Proste.
źródło