WordCount: jak nieskuteczne jest rozwiązanie McIlroya?

Question

Krótka historia: w 1986 r. Ankieter poprosił Donalda Knutha o napisanie programu, który pobiera tekst i numer N na wejściu, i wymienia N najczęściej używanych słów posortowanych według ich częstotliwości. Knuth przygotowała 10-stronicowy Pascal program, do którego Douglas McIlroy odpowiedział z następujących 6 linii shell script:

tr -cs A-Za-z '\n' | 
tr A-Z a-z | 
sort | 
uniq -c | 
sort -rn | 
sed ${1}q 

Przeczytaj pełną historię na http://www.leancrew.com/all-this/2011/12/more-shell-less-egg/.

Oczywiście miały bardzo różne cele: Knuth pokazywał swoje koncepcje programowania literackiego i budował wszystko od zera, podczas gdy McIlroy używał kilku popularnych narzędzi UNIX, aby uzyskać najkrótszy kod źródłowy.

Moje pytanie brzmi: jak źle to jest?
(wyłącznie z punktu widzenia środowiska wykonawczego prędkości, ponieważ jestem całkiem pewien, że wszyscy zgadzają się, że 6 linii kodu jest łatwiejsze do zrozumienia/utrzymaniu niż 10 stron, literat programowania, czy też nie).

mogę zrozumieć że sort -rn | sed ${1}q może nie być najskuteczniejszym sposobem wyodrębnienia popularnych słów, ale co jest nie tak z tr -sc A-za-z '\n' | tr A-Z a-z? Dla mnie wygląda całkiem nieźle. O sort | uniq -c, jest to strasznie powolny sposób na określenie częstotliwości?

Kilka względy: (?)

• tr powinien być czas liniowy
• sort Nie jestem pewny, ale jestem przy założeniu, że nie jest że złe
• uniq powinny być czas liniowy zbyt
• procesy odradzania powinny być liniowe (w liczbie procesów)

Answer 1

Skrypt Unix ma kilka operacji liniowych i 2 sortowania. Będzie to porządek obliczeniowy O(n log(n)).

Dla algorytmu Knuth do robienia tylko górną N: http://en.wikipedia.org/wiki/Selection_algorithm gdzie można mieć kilka opcji w czasie i przestrzeni złożoności algorytmu, ale teoretycznie mogą one być szybsze dla niektórych typowych przykładów z dużą liczbą (różnych) słów .

Tak więc Knuth może być szybszy. Z pewnością dlatego, że angielski słownik ma ograniczony rozmiar. Może się zmienić w pewną dużą stałą, choć może zużywającą dużo pamięci.

Ale może to pytanie lepiej pasuje do: https://cstheory.stackexchange.com/