WordCount: насколько неэффективно решение Макилроя?

Question

Короче говоря: в 1986 году интервьюер попросил Дональда Кнута написать программу, в которой вводится текст и число N, и перечислены N наиболее используемых слов, отсортированных по их частотам. Кнут выпустил 10-страниц Паскаль программу, в которой Дуглас Макилрой ответил со следующими 6 линий оболочки сценарий:

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

Читайте полный рассказ на http://www.leancrew.com/all-this/2011/12/more-shell-less-egg/.

Конечно, у них были разные цели: Кнут показывал свои концепции грамотного программирования и строил все с нуля, в то время как Макилрой использовал несколько общих утилит UNIX для достижения кратчайшего исходного кода.

Мой вопрос: насколько это плохо?
(Чисто с точки выполнения скорости зрения, так как я уверен, что мы все согласны с тем, что 6 строк кода легче понять/поддерживать более 10 страниц, грамотного программирования или нет.)

Я могу понять что sort -rn | sed ${1}q может быть не самым эффективным способом извлечения общих слов, но что не так с tr -sc A-za-z '\n' | tr A-Z a-z? Это выглядит очень хорошо для меня. О sort | uniq -c, это ужасно медленный способ определения частот?

Несколько соображений: (?)

• tr должно быть линейное время
• sort Я не уверен, но я предполагаю, что это не , что плохо
• uniq должен быть линейное время тоже
• Процессы нереста должны быть линейными (в количестве процессов)

Answer 1

Сценарий Unix имеет несколько линейных операций и 2 вида. Это будет порядок расчета O(n log(n)).

Для алгоритма Кнута для принятия только верхний N: http://en.wikipedia.org/wiki/Selection_algorithm Где вы можете иметь несколько вариантов во времени и пространстве сложности алгоритма, но теоретически они могут быть быстрее для некоторых типичных примеров с большим количеством (различных) слов ,

Так что Кнут мог бы быть быстрее. Конечно, потому что английский словарь имеет ограниченный размер. Он мог бы превратить log(n) в некоторую большую константу, хотя, возможно, она потребляет много памяти.

Но возможно этот вопрос лучше подходит для https://cstheory.stackexchange.com/