Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

о силе юникса

More Shell, Less Egg рассказывает подробно историю, которая случилась в 1970-х. Джон Бентли (автор колонки "Programming Pearls", которая потом вышла отдельной книгой, очень хорошей, кстати) попросил Дональда Кнута написать небольшую программу в стиле literate programming, который изобрел Кнут (когда код пишется буквально внутри его подробного словесного описания).

Кнут написал программу для нахождения N самых частых слов в данном тексте. Он придумал хитрую структуру данных для хранения промежуточных частот, которую было особенно удобно поддерживать в процессе сканирования текста. На программу Кнута написал рецензию Даг Макилрой, который помимо прочего решил ту же задачу с помощью шести команд юниксовской командной строки:
$ tr -cs A-Za-z \n | 
tr A-Z a-z
sort | uniq -c | sort -rn | head -$1

Здесь:
  • первый вызов tr переводит все символы, кроме букв, в перевод строки и потом схлопывает все эти переводы между словами,
  • второй переводит большие буквы в маленькие (теперь у нас все слова текста по порядку, каждое в отдельной строке),
  • потом сортируем,
  • uniq -c схлопывает идентичные слова, идущие рядом (после сортировки) и ставит перед каждым его частоту, напр. "1000 the",
  • sort -rn
    сортирует по этим числам в обратном порядке,
  • и наконец head выбирает первые N строк, т.е. первые N самых частотных слов.

Убедительно и в общем-то несложно, я много раз решал мелкие проблемы подсчета чего-то с помощью sort |uniq -c |sort -n. Думаю, первый запуск tr я бы так сразу не написал, а вместо этого написал бы эквивалентную команду для sed, и пару раз пришлось бы запустить ее для отладки.
Tags: программирование
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 70 comments