?

Log in

No account? Create an account
о силе юникса - По делам сюда приплыл, а не за этим — ЖЖ [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

о силе юникса [дек. 13, 2018|01:18 pm]
Anatoly Vorobey
[Tags|]

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, и пару раз пришлось бы запустить ее для отладки.
СсылкаОтветить

Comments:
[User Picture]From: shadow_ru
2018-12-13 12:10 pm
Вот поэтому я не понимаю, как можно девелопить под виндой.
(Ответить) (Thread)
[User Picture]From: the_chiffa
2018-12-13 12:17 pm
Notepad++, регулярки, csv, Excel :)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: livelight
2018-12-13 12:14 pm
> На программу Кнута написал рецензию Даг Макилрой, который помимо прочего решил ту же задачу с помощью шести команд юниксовской командной строки:

Вдвойне гениально, если учесть, что весь функционал подсчёта частоты находится внутри команды uniq -c, которую гении баша просто вызывают.
(Ответить) (Thread)
[User Picture]From: avva
2018-12-13 12:22 pm
uniq -c всего лишь подсчитывает частоту *идущих подряд* одинаковых строчек - это намного легче подсчета частоты вразброс. Всего лишь надо помнить последнюю строку и увеличивать на 1 счетчик, пока она не сменится - а потом послать на вывод и забыть.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: leo715
2018-12-13 12:31 pm
В что будет с апострофами? Т.е it’s, don’t и т.д.
(Ответить) (Thread)
[User Picture]From: avva
2018-12-13 12:36 pm
Все будет плохо, но насколько я понимаю, в сложной программе Кнута то же самое. Если текст не пользуется апострофами как кавычками, можно просто сделать их частью слов; если пользуется, то сложнее.
(Ответить) (Parent) (Thread) (Развернуть)
From: wordbuff
2018-12-13 01:07 pm

А теперь зачем это нужно

А теперь зачем это нужно в жизни --
на днях где-то в ЖЖ видел вопрос о поисковых
запросах, нынче Гугле так замутил, что запросы
становятся непредсказуемыми.

Ему посоветовали находить типичные тексты по
теме, которые дают термины (например, статьи
Википедии),

.. которые надо обработать, выбрав самые частые
слова, которые нетипичны (т.е. их частотка в тексте
описывающем проблему вообще выше частотности таких
слов "в среднем")

И задав поиск с набором (неочевидных человеку, часто)
подобных слов, мы на удиввление, начинаем вылавливать
в поисковиках хорошие и отличные выборки.

ОТ СЕБЯ ДОБАВЛЮ - можно не сравнивать с частотой
в среднем в языке, можно просто выбирать 'длинные'
слова (по числу букв) в верху самых частых слов
текста-образца.

Т.е. в конце вашего invocation из примера надо сделать
"| head -20" например и вбивать в поисковик длинные слова
(игнорируя "и", "не" ,"под", и т.д.)

Edited at 2018-12-13 13:20 (UTC)
(Ответить) (Thread)
[User Picture]From: freedom_of_sea
2018-12-13 02:02 pm
поразительно, что все эти команды существовали в 1970
(Ответить) (Thread)
[User Picture]From: avva
2018-12-13 04:36 pm
Вот да.
(Ответить) (Parent) (Thread)
[User Picture]From: meshko
2018-12-13 02:10 pm
Меня забавляет то, как революция веб сервисов вписалась в парадигму командной строки в Линуксе. У меня в .bashrc больше дюжины функций, которые вызывают curl на всякие внутринние сервисы и перенаправляют результат в awk/sed/jq.
(Ответить) (Thread)
From: karpion
2018-12-13 03:02 pm
Если исходный текст сильно больше оперативной памяти - то у sort будут большие проблемы с производительностью. Тогда как Дональд Кнут получит аналогичные проблемы только если его хитрая структура не влезет в память - а она размером всего лишь со словарь текста (т.е. каждое слово там всего один раз).
(Ответить) (Thread)
[User Picture]From: grey_kristy
2018-12-14 07:50 am
эээ а где вы видели текст, который больше оперативной памяти?
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: xgrbml
2018-12-13 05:42 pm
Про эти волшебные ключи у tr, sort и uniq не знал.
(Ответить) (Thread)
[User Picture]From: cpt_alatriste
2018-12-13 07:11 pm
Нужна седьмая команда, чтобы tr что-то на вход подавать :-)
(Ответить) (Thread)
[User Picture]From: akss
2018-12-13 07:20 pm
Почему-то команду tr я так и не понял. Пользуюсь sed.
(Ответить) (Thread)
[User Picture]From: avva
2018-12-13 10:41 pm
Я тоже.
(Ответить) (Parent) (Thread)
[User Picture]From: vyhuhol
2018-12-13 07:31 pm

Master Foo and the Ten Thousand Lines

Master Foo once said to a visiting programmer: “There is more Unix-nature in one line of shell script than there is in ten thousand lines of C.”

The programmer, who was very proud of his mastery of C, said: “How can this be? C is the language in which the very kernel of Unix is implemented!”

Master Foo replied: “That is so. Nevertheless, there is more Unix-nature in one line of shell script than there is in ten thousand lines of C.”

The programmer grew distressed. “But through the C language we experience the enlightenment of the Patriarch Ritchie! We become as one with the operating system and the machine, reaping matchless performance!”

Master Foo replied: “All that you say is true. But there is still more Unix-nature in one line of shell script than there is in ten thousand lines of C.”

The programmer scoffed at Master Foo and rose to depart. But Master Foo nodded to his student Nubi, who wrote a line of shell script on a nearby whiteboard, and said: “Master programmer, consider this pipeline. Implemented in pure C, would it not span ten thousand lines?”

The programmer muttered through his beard, contemplating what Nubi had written. Finally he agreed that it was so.

“And how many hours would you require to implement and debug that C program?” asked Nubi.

“Many,” admitted the visiting programmer. “But only a fool would spend the time to do that when so many more worthy tasks await him.”

“And who better understands the Unix-nature?” Master Foo asked. “Is it he who writes the ten thousand lines, or he who, perceiving the emptiness of the task, gains merit by not coding?”

Upon hearing this, the programmer was enlightened.
(Ответить) (Thread)
[User Picture]From: avva
2018-12-13 10:40 pm

Re: Master Foo and the Ten Thousand Lines

Точно!
(Ответить) (Parent) (Thread)
[User Picture]From: p2004r
2018-12-13 08:14 pm
Каждый человек использующий юникс в своей деятельности писал эту последовательность самостоятельно :)

Но для биг дата возвратиться к концепции баз данных последовательного доступа при нехватке ресурса вполне себе очевидное решение.
(Ответить) (Thread)
[User Picture]From: bolk
2018-12-14 07:56 pm
Я бы вместо первой команды написал egrep -oi '[a-z]+', остальное бы сделал так же.
(Ответить) (Thread)