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

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óż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.