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

Question

Короче говоря: в 1986 году интервьюер попросил Дональда Кнута написать программу, в которой вводятся текст и число N, а также перечисляются N наиболее часто используемых слов, отсортированных по частоте. Кнут создал 10-страничную программу Pascal, на которую Дуглас Макилрой ответил следующим 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/

Answer 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

Вот это очень быстро раствор в Rust Андерс Kaseorg.

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

                                     bible32       bible256       Asymptotical
Rust (prefix tree)                   0.632         5.284          O(?)
C++ (prefix tree + heap)             4.838         38.587         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 - небольшая константа)
• bible32 состоит из Библии 32 раза (135 МБ), bible256 - 256 раз соответственно (1,1 ГБ)
• Время AWK может сильно различаться в зависимости от того, какую версию AWK вы используете (gawk, nawk или mawk).

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