Недавно я понял, что сказка про Теремок имеет под собой алгоритмическую основу.
Давайте посмотрим:
Мышка-норушка приходит к пустому Теремку и спрашивает, кто там живёт. Там никого нет (получено 0 ответов), и Мышка селится в Теремке.
Затем приходит Лягушка-квакушка, и спрашивает, кто живёт в Теремке. Ей отвечает Мышка (получен 1 ответ). Лягушка селится в Теремке.
Затем приходит Зайчик-побегайчик, и задаёт тот же вопрос. Ему отвечают Мышка и Лягушка (получено 2 ответа).
Итого, каждый N-й зверь, приходящий к Теремку, получает N-1 ответов, прежде чем поселиться в нём.
Такую прогрессию мы уже видели и её сумма равна (N² + N) / 2, то есть печально известная сложность O(N²).
Это даёт нам интересный побочный эффект. Мы можем точно предсказать, сколько времени займёт изложение сказки для любого заданного количества зверей.
Скажем, если один ответ занимает 10 секунд, то сказка с 64 зверями будет длиться почти 6 часов, а сказка со 128 зверями займёт почти двое суток.
Также возникает интересный парадокс. Если количество зверей стремится к бесконечности, то и количество ответов стремится к бесконечности. Каждый конкретный зверь при заселении в Теремок всегда выслушивает ограниченное количество ответов, то есть этот процесс когда-то заканчивается, и зверь заселяется. Но зверь, который существует в пределе, заселиться уже не сможет, так так должен выслушать бесконечность ответов.
Теремок представляет собой коллекцию типа стека FIFO – порядок уже находящихся в нём элементов изменить нельзя. Мышка всегда отвечает первой, Лягушка второй и т.д., а новые элементы могут добавляться только в конец.
Описать ответы зверей можно с помощью цикла:
foreach ($teremok as $animal) echo "I am {$animal->name}\n";
Как помочь зверям заселяться побыстрее, то есть снизить вычислительную сложность?
Например, они могли бы ничего не спрашивать и сразу заселяться. Но в сказке так не работает, там реальность такова, что нужно сначала получить детальную информацию о всех жителях Теремка. Поэтому рассмотрим вопрос получения этой информации.
Контекстное знание
Вместе с конкретной, необходимой нам информацией мы зачастую получаем и косвенную, которую нам никто не сообщал. Мы можем вывести её логически из того, что есть, или просто знать заранее.
Например, когда нам сообщают, что сегодня 8 марта, то мы знаем, что в марте 31 день, а в одном дне 24 часа. Это косвенная информация. Мы также знаем, что завтра будет 9 марта, потому что дни в месяце всегда идут по порядку. Это тоже косвенная информация.
В программировании, если вы хотите что-то оптимизировать, вы должны по максимуму использовать любую косвенную информацию.
Например, известно, что звери, живущие в Теремке, всегда отвечают в одном и том же порядке.
Если договориться, что отвечает только самый последний заселившийся зверь, то стоимость такой операции составила бы всего O(1). Гарантируется, что ни один зверь не промолчит, не ответит дважды или за другого зверя.
Но каждый приходящий зверь должен иметь информацию о всех зверях, проживающих в Теремке, а не только о последнем. Что делать в этом случае?
Кеширование информации
Если процесс получения информации связан с какими-то трудностями, то добыв эту информацию, её можно где-нибудь сохранить, чтобы воспользоваться позже.
Предположим, перед Теремком стоит доска объявлений. Каждый зверь, приходя к Теремку, получает ответ от последнего заселившегося зверя, записывает его имя на доске, и заселяется сам.
Тогда следующий зверь при взгляде на доску уже знает, кто там живёт, и должен дописать только последнего зверя.
Данный процесс можно упростить: любой зверь читает доску, потом просто записывает на доске собственное имя и заселяется. Никто ничего не спрашивает и никто никому не отвечает. Но это ломает ритуал сказки.
Нужно отметить, что на чтение доски требуется время того же порядка, что и на выслушивание ответов. То есть мы опять попадаем в парадокс бесконечности.
Но мы можем отказаться от последовательного чтения. Предположим, что звери обладают фотографической памятью и запоминают изображение доски, не читая её. Они заселяются, но в любой момент, если понадобится, могут вспомнить изображение доски и перечислить все написанные на ней имена. Информация есть? Да, есть.
В программировании это решается с помощью ссылки на структуру, где хранится доска. Звери запоминают только ссылку. Когда им нужна информация с доски, они находят её по ссылке.
Виртуальный Теремок
Мы также можем воспользоваться знанием, которое есть заранее. Например, мы уже читали сказку про Теремок и поэтому знаем, когда и какие звери приходили к нему. В этом случае мы можем создать виртуальную копию Теремка, уже полностью заселённую (или, что аналогично, доску с заранее написанным полным списком имён).
Тогда реальный Теремок схлопывается просто до одного числа. Это число даёт нам ответ, в каком состоянии сейчас находится Теремок.
Например, если это число 3, то там проживают (сверяемся с заранее составленным списком) Мышка, Лягушка и Зайчик.
Возникает ещё один интересный случай. Зайчик, подходя к Теремку, может самостоятельно восстановить его состояние просто исходя из факта, что он – Зайчик. Он должен прийти третьим, значит состояние Теремка в данный момент равно 2. Зайчик не может прийти не третьим, это уже предопределено заранее заданной информацией.
Ещё одно следствие такого подхода – звери могут не жить в Теремке по-настоящему.
Что значит "по-настоящему"? Мы могли бы смоделировать Теремок в виде массива (как было описано ранее), и создать объекты-зверей, и поместить их в массив. То есть каждый зверь физически существовал бы в виде объекта.
А здесь мы храним только таблицу имён и одно число – текущее состояние Теремка. Зверей как таковых не создано, но как только нам потребуются какие-то операции с ними, можно восстановить всю необходимую информацию и создать объекты. Проделав с ними требуемые операции, мы затем можем уничтожить объекты, и звери, подобно виртуальным частицам в вакууме, снова вернутся в состояние небытия.
