Дональд Кнут —  автор «Искусства программирования»  и  великий мастер ордена программистов Земли

Уже совсем скоро – 10 января  гранд-мастеру программирования исполнится 84 года,  а он считает, что для окончания основного труда его жизни «Искусства программирования» ему необходимо еще 25 лет.  Дай бог ему здоровья, сил и ясный ум, а со всем остальным он точно справится сам. Кстати, рост у него не как у мастера Йоды – 190 см, вот здесь хорошо видно по плечам, хотя он, конечно, сильно сутулится.

На Хабре писали про Кнута  предостаточно, потому ограничусь здесь  моими любимыми цитатами и одной замечательной историей из его жизни, про которую здесь почему-то еще не упоминали.

Именно  ее я поведал  своим ученикам на самых первых уроках программирования лет 20 назад (да, был такой период, когда я преподавал в техническом лицее в маленьком  провинциальном городке у полярного круга).  Зачем же я ее рассказал? Чтобы объяснить, какие именно качества необходимы будущему программисту, хотя в нашей истории нет ни единого слова ни о программировании, ни о компьютерах.

«Дональд Кнут был  младше вас, сидящих здесь в классе, ему едва ли исполнилось 14 лет,  когда он услышал, как по  ТВ объявили о конкурсе местной кондитерской компании: предлагалось из букв использованных в названии нового шоколадного батончика «Гигантские батончики Циглера» («Ziegler’s Giant Bar») составить наибольшее количество слов. Приз  для победителя  держали в тайне, но как обещали, он  точно должен быть весьма ценным.  Игры в слова, настолки  типа скрэббла, до сих популярны в США и являются традиционным семейным досугом. Потому многие любители настольных  игр, конечно же, тут же подписались на участие в конкурсе.

Поразмыслив Дональд тоже решил принять участие. Что он мог противопоставить  компании (семье) из 5-6 друзей  заядлых игроков- «монстров  скрэббла», которые за считанные минуты  могли составить десятки слов, а за один  только вечер уж точно не менее нескольких сотен слов в сумме?

Если на короткой дистанции в 2-3 дня  у него точно нет ни единого шанса, то на длинной  –  в две недели он вполне может победить, просто потому что примерно знал, как именно его соперники  будут действовать.  Каждый из игроков  станет составлять список слов самостоятельно в течение определенного времени, затем они соберутся в одной большой комнате и начнут  по очереди их зачитывать, при этом каждый  игрок будет вычеркивать у себя уже  прозвучавшие слова. В конце  все полученные незачеркнутые слова будут занесены  (переписаны)  в основной список. На второй и третий день количество таких слов  уменьшится в разы.  При этом все больше времени станет уходить на сверку  новых слов с предыдущим списком.  Очевидно, что скорость роста основного списка будет неуклонно и быстро падать с каждым днем.

Так каким  же образом  Дональд  мог обогнать целую команду таких игроков?

Только если выберет иной путь к достижению цели.  И он делает это:  зачем  составлять  слова из данного набора букв, когда можно  проверять готовый список слов на наличие в нем этих самых букв?!

 Если взять  достаточно полный словарь английского языка, то база для поиска  слов будет просто огромной, а, следовательно,  итоговый  результат должен быть заметно лучше  чем у «монстров скрэббла». Тем более, что такой словарь  у Дональда, а точнее у его отца  – владельца типографии,  был:  New Standard Unabridged Dictionary of the English Language, Funk & Wagnalls. Замечательный  двухтомник  — всего навсего на две тысячи страниц.

Что же такое словарь? Это, по сути, список всех слов в алфавитном порядке. Значит, отпадает одна из главных проблем – проверка  найденных слов на уникальность,  поскольку в словаре изначально нет повторов. Скорость поиска слов таким методом хоть изначально не слишком высока, но будет практически постоянной все две недели, не снижаясь к концу срока.

Идея использовать словарь, конечно же, замечательная, но как ее осуществить?  Каким образом перебрать более 50 тысяч слов на наличие  в них определенного набора букв за столь короткий срок?   Кнут  в воспоминаниях не описывает своего  алгоритма,  но, уверен,  мы сами сможем восстановить его, используя его упоминания про закладки и карточки.  

Для начала Дональд аккуратно   выписывает буквы из фразы «Ziegler’s Giant Bar»,  удаляя  повторы и размещая их в алфавитном порядке (11 букв).  На втором листе  он выписывает все буквы  невходящие  в эту фразу так же в алфавитном порядке (15 букв).  Затем вносит закладки в словарь по начальным буквам, которых нет в ключевой фразе.  На этом этапе таким образом он исключает  для будущего анализа, не менее 30  тысяч слов.  Потом   приступает к делу, составляя карточки с сочетаниями первых и вторых букв, пропуская ровно так же слова, у которых вторые буквы не входят  в  ключевую фразу. Уже на этом этапе  у него остается всего около 10 тысяч слов.   Поскольку словарь, напоминаю,  упорядочен по алфавиту,  натыкаясь, например, на третью букву невходящую в список,  он листает словарь, пока эта или предыдущие по порядку буквы в словах не сменятся.

Тем не менее, такой  кропотливый труд требует много времени,  и с началом второй недели до окончания конкурса,  понимая, что он катастрофически не успевает закончить перебор всех слов,  Дональд  отпрашивается с уроков на неделю, сославшись на сильные боли в животе, и запирается дома в  подвале на восемь часов в день и больше, анализируя и выписывая полученные слова.

Итог его работы за две недели – четыре с половиной тысяч слов!

Ни один из других участников не составил  более двух тысяч слов,  у самих судей на руках изначально – список всего из двух с половиной тысяч. Такого результата от  долговязого 13-летнего школьника не ожидал никто. Его пригласили на телепередачу,  где торжественно вручили  главный приз  – телевизор   и большую  коробку шоколадных батончиков. Телевизор достался школе, а батончики  он раздал своим одноклассникам».  

Так какие же качества будущего программиста продемонстрировал  Дональд Кнут в данной истории?

Первое: умение выполнить постановку  задачи. То, чему в школе, да зачастую и в университетах не учат в принципе.  Вспомните формулировки задач в учебниках: вот вам необходимые и достаточные данные  для решения,  а теперь решайте задачу и  получите  ответ. В жизни так не бывает.  Ты получаешь задание,  а вот постановку задачи  ты должен сделать сам, как, впрочем, определить  и найти  нужные данные  для ее решения.  В нашем случае  задание: «Составить как можно больше слов из данного набора букв»,  он свел к очень конкретно  поставленной задаче:  «Найти  все слова в словаре Funk&Wagnalls,  полностью состоящих из данного набора букв».

Второе:  вместо того, чтобы действовать и сразу же приступить к поиску этих слов в словаре, он сначала разработал алгоритм отсеивания  слов, неподходящих  к требованиям задачи. К сожалению, у многих программистов умение остановиться  и подумать, прежде чем начать стучать по клавиатуре, напрочь отстутствует, они предпочитают, как я это называю,  «думать руками» –  кодят сразу: «Хрен ли здесь думать –  прыгать надо!» И это, уж извините, очень плохо.

Третье: хотя  постановка задачи и разработка алгоритма решения задачи весьма интересны и очень важны, но занимают они в самом лучшем случае лишь 5%  от затраченного времени и сил  в процессе решения той или иной задачи.  Остальное –  рутина:  реализация алгоритма  с учетом особенностей языка программирования,   доводка программы до рабочего состояния, затем  тестирование, бесконечное вылавливание блох (исправление багов)  в программе. Без огромного упорства и  концентрации на предмете в программировании абсолютно точно нечего делать. Именно эти свойства  и продемонстрировал нам тринадцатилетней подросток, работая без выходных две недели в подвале своего дома, просто потому что решил довести дело, за которое взялся, до конца. Увы, если у вас «шило в заднице»  — программирование не для вас, каким бы острым и быстрым  умом вы не обладаете.

После знакомства с основными  понятиями и операторами  языка программирования, давал ученикам эту задачу, как одну из начальных после освоения азов, причем  исходный словарь они должны были найти сами. При желании можете раскрыть спойлер и посмотреть.

with open("c:\wordbook.txt", "r") as file1:     mn_zgbar=set("zieglersgiantbar")     i=0     # итерация по строкам словаря     for line in file1:         if line[len(line)-1]=='\n':           line=line[:len(line)-1]         #line = line.replace('\n','')         mn_line=set(line)         if mn_zgbar >= mn_line:  # проверка вхождения букв слова в ключевую фразу             i+=1             print(i,' ', line)

with open("c:\wordbook.txt", "r") as file1:     zgbar="abegilnrstz"     i=0     # итерация по строкам словаря     for line in file1:         if line[len(line)-1]=='\n':            line=line[:len(line)-1]         k=0         flag=False         while k<len(line):             m=0             # Проверка букв слова на совпадение              while m<len(zgbar):                 if line[k]== zgbar[m]:                     flag=True                     break                 else:                     flag=False                 m+=1             k+=1             if flag == False:                 break                     # Вывод полученных слов          if flag:             i+=1             print(i,' ',line)

Ну и на закуску мои любимые цитаты Дональда Кнута. Добавляйте в комментариях свои!

Остерегайтесь ошибок в приведенном выше коде; я только доказал его правильность, но не проверял его.

Случайные числа не должны генерироваться случайным образом выбранным методом.

Наука — это знание, которое мы так хорошо понимаем, что можем обучить ему компьютер; а если мы не понимаем до конца, как с этим справляться — это искусство.

В этом смысле мы должны постоянно стремиться превратить каждое искусство в науку: в процессе этого мы продвигаем дальше искусство.

Давайте изменим наше традиционное отношение к построению программ: вместо того, чтобы воображать, что наша основная задача — указывать компьютеру, что ему делать, давайте сосредоточимся на объяснении людям того, что мы хотим, чтобы компьютер делал.

Я предполагаю, что Бог существует, и рад, что это невозможно доказать. [Потому что] я бы проверил доказательство один раз, а потом тут же его забыл бы, ведь иначе я никогда не смог бы рассуждать о духовных вещах и тайнах. И, думаю, моя жизнь была бы очень неполной.

@LKamrad

Дата-центр ITSOFT — размещение и аренда серверов и стоек в двух дата-центрах в Москве. За последние годы UPTIME 100%. Размещение GPU-ферм и ASIC-майнеров, аренда GPU-серверов, лицензии связи, SSL-сертификаты, администрирование серверов и поддержка сайтов.