WordCount: Wie ineffizient ist McIlroys Lösung?

Question

Lange Rede, kurzer Sinn: Im Jahr 1986 bat ein Interviewer Donald Knuth, ein Programm zu schreiben, das einen Text und eine Zahl N in die Eingabe aufnimmt und die N am häufigsten verwendeten Wörter sortiert nach ihren Häufigkeiten auflistet. Knuth produzierte eine 10-Seiten Pascal-Programm, zu denen Douglas McIlroy mit den folgenden 6-Zeilen antwortete Shell-Skript:

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

die ganze Geschichte an http://www.leancrew.com/all-this/2011/12/more-shell-less-egg/ Lesen.

Natürlich hatten sie sehr unterschiedliche Ziele: Knuth zeigte seine Konzepte der alphabetischen Programmierung und baute alles von Grund auf neu auf, während McIlroy einige gängige UNIX-Dienstprogramme verwendete, um den kürzesten Quellcode zu erhalten.

Meine Frage ist: Wie schlimm ist das?
(Rein aus einer Runtime-Geschwindigkeit Sicht wir uns alle einig, da ich ziemlich sicher bin, dass 6 Zeilen Code leichter zu verstehen/pflegen als 10 Seiten, belesen Programmierung oder nicht.)

kann ich verstehen dass sort -rn | sed ${1}q möglicherweise nicht die effizienteste Möglichkeit ist, die gängigen Wörter zu extrahieren, aber was ist los mit tr -sc A-za-z '\n' | tr A-Z a-z? Es sieht ziemlich gut aus für mich. Über sort | uniq -c, ist das ein schrecklich langsamer Weg, um die Frequenzen zu bestimmen?

Einige Überlegungen: (?)

• tr sollte die lineare Zeit sein
• sort bin ich nicht sicher, aber ich nehme an, es nicht ist, dass schlecht
• uniq sein sollte lineare Zeit zu
• Laichprozesse sollten lineare Zeit sein (in der Anzahl der Prozesse)

Answer 1

Das Unix Skript hat ein paar lineare Operationen und 2 Sortierungen. Es wird die Berechnungsreihenfolge O(n log(n)) sein.

Für Knuth-Algorithmus nur die Top-N unter: http://en.wikipedia.org/wiki/Selection_algorithm Wo Sie ein paar Optionen in Zeit und Raum Komplexität des Algorithmus haben kann, aber theoretisch kann sie schneller für einige typische Beispiele mit einer großen Anzahl von (unterschiedlichen) Worte .

So könnte Knuth schneller sein. Sicherlich, weil das englische Wörterbuch eine begrenzte Größe hat. Es könnte log(n) in einer großen Konstante drehen, obwohl es viel Speicher verbraucht.

Aber vielleicht ist diese Frage besser geeignet für https://cstheory.stackexchange.com/