Уже совсем скоро – 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-сертификаты, администрирование серверов и поддержка сайтов.