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

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

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 также должно быть линейным.
Процессы нереста должны быть линейными (в количестве процессов)

Ответ 1

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

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

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

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

Ответ 2

Решение Дуга Макилроя имеет временную сложность O (T log T), где T - общее количество слов. Это связано с первым sort.

Для сравнения приведем три более быстрых решения одной и той же проблемы:

Вот реализация C++ с верхней временной границей сложности O ((T + N) log N), но практически - почти линейной, близкой к O (T + N log N).

Ниже приведена быстрая реализация Python. Внутренне он использует хэш-словарь и кучу со сложностью времени O (T + N log Q), где Q - количество уникальных слов:

import collections, re, sys

filename = sys.argv[1]
k = int(sys.argv[2]) if len(sys.argv)>2 else 10
reg = re.compile('[a-z]+')

counts = collections.Counter()
for line in open(filename):
    counts.update(reg.findall(line.lower()))
for i, w in counts.most_common(k):
    print(i, w)

И еще одно решение оболочки Unix с использованием AWK. Он имеет временную сложность O (T + Q log Q):

awk -v FS="[^a-zA-Z]+" '
{
    for (i=1; i<=NF; i++)
        freq[tolower($i)]++;
}
END {
    for (word in freq)
        print(freq[word] " " word)
}
' | sort -rn | head -10

Сравнение времени процессора (в секундах):

                                     bible32       bible256       Asymptotical
C++ (prefix tree + heap)             5.659         44.730         O((T + N) log N)
Python (Counter)                     14.366        115.855        O(T + N log Q)
AWK + sort                           21.548        176.411        O(T + Q log Q)
McIlroy (tr + sort + uniq)           60.531        690.906        O(T log T)

Заметки:

T> = Q, обычно Q >> N (N - маленькая константа)
Библия32 объединена в Библии 32 раза (135 МБ), Библия256 - 256 раз соответственно (1,1 ГБ)

Как вы можете видеть, решение McIlroy легко обгоняет процессорное время даже при использовании стандартных инструментов Unix. Тем не менее, его решение все еще очень элегантно, его легко отлаживать и, в конце концов, оно не так уж плохо по производительности, если только вы не начнете использовать его для мультигигабайтных файлов. Плохая реализация более сложных алгоритмов в C/C++ или Haskell может легко работать намного медленнее, чем его конвейер (я видел это!).