Говоришь людям, что в современном подходе к программированию всё уже не так, как раньше — не верят. Однако не только управление памятью, но и циклы отходят в прошлое. И что там циклы — даже условия, оформленные в виде if-then-else, в хорошем коде теперь нечасто встретишь. И перехват ошибок при помощи try-catch.
Разумеется, на это временами возражают не только прошаренные граждане, тридцать лет назад для интереса изучавшие программирование по первой попавшейся книге, но и даже некоторые вроде бы программисты. Которые заодно постоянно порождают код, полный контрпримеров этому самому «отходят в прошлое», поскольку не подозревают, что можно как-то иначе.
И правда, как иначе? Давно ведь сложился стереотип, что программирование — это такая особая элитарная штука для особых людей, умеющих разговаривать с компьютером на компьютерном языке. Где какие-то там регистры, прерывания, двоичное счисление, вот это вот всё.
Сейчас, конечно, уже основной носитель стереотипов не первое поколение программистов, поэтому не «регистры и прерывания», а «вложенные циклы и условное ветвление в три экрана длиной» считаются вещью, от которой решительно невозможно избавиться.
Но фишка в том, что таки можно. И люди таки избавляются. И программирование становится всё ближе к «формальному языку для человеческих рассуждений» и всё дальше от минимализма и неинтуитивности Машины Тьюринга.
Сейчас у меня для иллюстрации того, как это сейчас работает, появился отличный пример — задача о выдумывании несуществующих слов.
Словогенерация — штука не только занимательная, но и практически полезная. Нужно вам, например, создать фэнтезийный мир для компьютерной игры или художественного произведения, а в нём, в этом мире, сотня персонажей и тысяча городов на карте — весьма проблематично придумать такое количество несуществующих слов. Фантазия, скорее всего, сдастся уже на втором десятке.
И вот оттуда возникает идея поручить придумывание слов компьютеру. Ну а сами сценаристы потом из списка выберут наиболее прикольные.
Любой, кто пытался думать на тему того, как случайным образом сгенерировать слово, довольно быстро понимал, что для этого совершенно не подходит случайный выбор буквы для каждой позиции. Слова в этом случае получаются не просто некрасивыми, но и совершенно нечитаемыми. Конечно, вероятность генерации прикольного слова не нулевая, но довольно низкая, а потому придётся перерывать горы шлака, чтобы такое слово отыскать среди десятков тысяч «фдвлафлдывайу» и «ыйзукъчамвафкнйук».
Потом иногда (но не обязательно) приходит в голову, что можно генерировать буквы не совсем случайно, а согласно частоте их использования: «т» встречается в словах чаще, чем «ш», и так далее. Однако положения это не спасает. Слова всё равно оказываются нечитаемыми, хотя теперь распределение букв по частоте использования в них примерно соответствует их распределению в каком-нибудь естественном языке.
В общем, единственный вариант — учитывать то, что не любая буква может идти после любой буквы. Вот «и» после «т» встречается, а после «ы» — нет.
Этот вариант уже неплох, однако перечислять вручную все возможные пары довольно долго. Кроме того, не всегда сходу понятно, бывают ли такие пары.
Вдобавок, внезапно, всё равно генерируется множество нечитаемых слов. Да, каждая пара букв реалистична, но вот сочетание из трёх и более букв при этом может оказаться нереалистичным. Например, встречаются сочетания «тр» («трамвай»), «рн» («корни») и «нт» («грунт»). Если алгоритм пользуется исключительно разрешёнными парами букв, то сочетание «трнтрнтр» для него вполне допустимо. А для нашего фэнтезийного мира — обычно нет.
То есть желательно использовать более длинные цепочки. Однако количество возможных вариантов растёт как степенная функция от количества букв в них. Если возможных пар в русском языке 33*33 = 1089 (что, впрочем, не вполне так, поскольку в названиях городов ещё могут быть, как минимум, апостроф, дефис и пробел), то троек уже 33*33*33 = 35 937. Задолбаешься перебирать.
А четвёрок — 1 185 921. Тут ручное их перечисление уже за гранью реальности.
Выход из положения нам подсказывает ещё одна наличествующая проблема: если просто перечислить допустимые пары, то названия будут слишком «беззубые». Поскольку топонимы связаны с языками местного населения, у них есть определённый «стиль». Названия английских городов звучат немного не так, как, например, голландских или японских. Даже при переносе национальных названий на другой язык, некий национальный колорит в них всё равно сохраняется: в том языке для топонимов возможны не все сочетания, которые в принципе возможны в этом языке.
Отсюда напрашивается решение: надо взять список городов некоторой страны или региона и извлечь из них допустимые сочетания. А потом именно ими пользоваться для генерации названий — тогда эти названия будут в основном читабельными и нести в себе некий «колорит» этого региона.
Когда-то, лет десять назад, я реализовывал этот алгоритм. И хотя я не был большим любителем всяких низкоуровневых штук, «циклов» (правда, в виде итераторов, а не просто счётчиков) в том коде было навалом. Ну и в целом реализация получилась довольно длинной и тяжёлой для понимания.
Прошло время, и мне снова захотелось реализовать этот алгоритм. В том числе потому, что, например, в Mathematica есть возможность запрашивать названия городов по регионам, что изрядно упрощает составление списков.
Однако времена изменились. Там, где раньше мои мысли сразу же рвались в гущи итераторов и чащи условий, сейчас в первую очередь думалось о трансформациях множеств.
Реально, смысл современных подходов именно в этом: примерно так же, как я описывал алгоритм на естественном языке, он должен описываться и на языке программирования. У нас есть некие множества, и мы их неким способом трансформируем.
Предположим, у нас уже есть «словарь» — множество имён собственных. Для простоты рассуждений, их пока что будет всего два.
words = {"Lond", "Lund"};
Для начала нам надо реализовать превращение слова в цепочки букв. Формат их описания будет максимально простой. Что-то типа
Lo → n
Lon → d
То есть сначала идёт некое сочетание уже существующих букв, а потом — через стрелку — какая буква может идти после этого сочетания.
Если нам дано слово и номер буквы, для которой мы строим цепочку, то способ построения этой цепочки практически очевиден. Мы берём первые n−1 букву, добавляем стрелку, а после неё добавляем n-ую букву.
makeChain[word_, n_] := StringTake[word, n − 1] → StringTake[word, {n}]
Работает оно примерно так.
makeChain[«Lond», 2]L → o
makeChain[«Lond», 4]
Lon → d
Чтобы получить все цепочки из слова, надо применить эту функцию для букв от второй до последней.
Возможно, кто-то на этом месте уже задумался о цикле. Однако цикл нам нафиг не нужен: нам ведь надо сконструировать список правил, а не повторить что-то там сколько-то там раз.
makeChains[s_] := Table[makeChain[s, n], {n, 2, StringLength@s}]
Да, тут есть что-то, напоминающее цикл: «n меняется от 2 до длины строки». Но я не думаю о данной подзадаче в такой терминологии. Я не думаю: «нам надо инициализировать переменную числом 2, а потом увеличивать это число на один, пока оно не станет равным длине строки». Нет, я думаю «нам надо создать список результатов функции makeChains для одной и той же строки, но для разных порядковых номеров буквы».
Просто потому, что так думать ощутимо проще. Фактически, я рассматриваю слово, как список букв, из которого хочу получить список их возможных цепочек.
makeChains[«Lond»]
{L → o, Lo → n, Lon → d}
Теперь надо проделать аналогичное для каждого слова из словаря и соединить результаты.
Тут я снова воспринимаю ситуацию не как потенциальную возможность для написания цикла, а как трансформацию множеств: при помощи makeChains мы можем преобразовать множество слов во множество цепочек букв, соответствующих этим словам.
makeAllChains[dict_] := makeChains /@ dict
f /@ {1, 2, 3}
{ f[1], f[2], f[3] }
makeAllChains[words]{ {L → o, Lo → n, Lon → d}, {L → u, Lu → n, Lun → d}}
После этого для получившегося множества нужные некоторые другие трансформации.
Во-первых, нам нужен обычный список, а не набор вложенных.
makeAllChains[dict_] := makeChains /@ dict // Flatten
Во-вторых, из него, видимо, надо удалить повторяющиеся элементы. В данном примере их нет, но в общем случае они там могут появиться.
makeAllChains[dict_] := makeChains /@ dict // Flatten // DeleteDuplicates
Трансформации множеств буквально нанизываются одна на другую. Конечно, так можно было бы сделать и с циклами, но сам стиль такого мышления, скорее всего, склонил бы программиста к заполнению тела этого цикла кучей дополнительных проверок, суровых хаков и т. д. При мышлении же множествами алгоритм сразу же видится как цепочка независимых друг от друга преобразований.
Так проще думать о смысле происходящего, поскольку вопросы технической реализации почти что от этого не отвлекают.
В частности, на данном этапе я замечаю, что для генерации слов нам пригодятся символы начала и конца слова — с их помощью будет легко найти первые буквы для слов и буквы, на которых слова могут закончиться.
Это — ещё одна трансформация: ко всем словам надо дописать символы начала и окончания (для этого я буду использовать один и тот же символ — подчёркивание).
stopSign = "_"; signs[dict_] := stopSign ~~ # ~~ stopSign & /@ dict
signs[words]{ _Lond_, _Lund_}
Эту трансформацию следует добавить к самому началу процесса: преобразовать таким образом весь поступивший на вход словарь.
makeAllChains[dict_] := makeChains /@ signs@dict // Flatten // DeleteDuplicates
makeAllChains[words]{_ → L, _L → o, _Lo → n, _Lon → d, _Lond → _, _L → u, _Lu → n, _Lun → d, _Lund → _}
Собственно, половина пути до составления правил генерации уже пройдена. И самое время задуматься о том, как она будет работать.
Видимо, мы начнём с подчёркивания, как начала слова, найдём те символы, которые могут идти после него, и добавим случайно выбранный из их числа. Потом возьмём строку из двух символов и снова найдём в списке все буквы, которые могли бы идти после них, и так далее, пока на каком-то этапе мы не выберем подчёркивание, означающее, что генерация слова завершилась.
То есть нам было бы удобнее, если бы список правил сразу бы содержал списки вариантов следующей буквы. Сейчас, например, у нас есть два варианта того, что может идти после «_L»:
Но было бы удобнее, если бы оно хранилось в другой форме:
_L → {o, u}
Иными словами, нам нужна ещё одна трансформация: группировка правил по «ключу» — левой от стрелки части.
makeRules[dict_] := GroupBy[makeAllChains@dict, First@# &]
Вторым параметром GroupBy тут передана функция извлечения первой части выражения со стрелкой, созданная прямо на месте — без имени функции и имени параметра.
Но пока что получается не совсем то, что хотелось бы.
_Lond → {_Lond → _}, _Lu → {_Lu → n}, _Lun → {_Lun → d}, _Lund → {_Lund → _}|>
Здесь действительно произошла группировка, но нам не нужно повторение «ключей» и стрелок в списках букв, возможных после данного сочетания. Благо, при группировке можно указать тот фрагмент, который следует оставить. Нам, в частности, нужна только вторая часть выражения — та, что справа от стрелки.
makeRules[dict_] := GroupBy[makeAllChains@dict, First@# &, Extract@{All, 2}]
_Lu → {n}, _Lun → {d}, _Lund → {_} |>
На данный момент, вся программа занимает пять строк. И ещё одна строка понадобилась, чтобы как-то назвать символ подчёркивания.
При этом она делает уже практически всё, что нужно: берёт словарь и генерирует из него список цепочек с альтернативами.
Точнее, не список, а «ассоциацию» (её нам вернула функция GroupBy).
В других языках программирования «ассоциации» часто называют «картами» или «словарями». Основной смысл этой структуры в том, что по «ключу» — тому, что слева от стрелки, можно быстро получить соответствующее ему «значение» — то, что справа от стрелки.
Делается это примерно таким образом:
2
Именно этим мы воспользуемся при генерации слов: просто будем запрашивать у ассоциации список дальнейших возможных букв по строке, уже сгенерированной в данный момент времени, которая будет «ключом». И выбирать из списка букву наугад.
nextLetter[rules_, wordPart_] := RandomChoice@rules[[wordPart]]
Заметьте, сколь удобно рассуждать таким образом. Я просто формально записываю на языке программирования ровно то, что сказал на естественном языке: «Попросим у набора правил список букв, соответствующий уже сгенерированной части. А потом выберем из этого списка букву наугад». Я ведь в рассуждениях ничего не говорю про «циклы», «счётчики», if-then и так далее. Нет их и в написанной мной программе.
Да, что-то такое сокрыто где-то внутри используемых мной методов, но в этом-то вся суть: современный язык программирования с самого начала содержит набор универсальных операций, при помощи которых легко рассуждать практически о любой задаче. И эти рассуждения ближе к естественному человеческому языку, нежели к низкоуровневым компьютерным «регистрам» и «прерываниям». И даже чем к циклам со счётчиком или получению значений списка по их порядковому номеру.
Если бы этих универсальных операций, подобных «человеческому» языку рассуждений, изначально не было в языке или в его стандартной библиотеке, их бы стоило реализовать в общем виде и только потом уже переходить к решению конкретных задач.
Так вот, теперь у нас есть генерация буквы и остаётся описать генерацию слова целиком.
Как уже говорилось, она весьма проста: мы берём уже сгенерированную часть, запрашиваем по ней следующую букву, добавляем её к сгенерированной части и повторяем процесс.
proceed[rules_, wordPart_, letter_] := With[
{r = wordPart ~~ letter},
proceed[rules, r, nextLetter[rules, r]]
]
Окончиться процесс должен на генерации подчёркивания — конца слова. Тут, казалось бы, нужно условие, но мы обойдёмся без него — просто объявим частный случай proceed: уже не для произвольной буквы, а для подчёркивания, названного нами stopSign.
Он, соответственно, должен просто отбросить первый символ — подчёркивание — от того, что уже сгенерировано, и вернуть результат.
proceed[rules_, wordPart_, stopSign] := StringTake[wordPart, -(StringLength@wordPart — 1)]
Чтобы запустить процесс, нам надо вызвать proceed со знаком подчёркивания в качестве затравки.
rules = makeRules[words]; proceed[rules, stopSign, ""]
Удивительно, но процесс описания алгоритма практически на этом и заканчивается. Разве что, запуск процесса ещё можно было бы оформить в отдельную функцию.
Вот вся содержательная часть программы.
stopSign = "_";
signs[dict_] := stopSign ~~ # ~~ stopSign & /@ dict
makeChain[word_, n_] := StringTake[word, n − 1] -> StringTake[word, {n}]
makeChains[s_] := Table[makeChain[s, n], {n, 2, StringLength@s}]
makeAllChains[dict_] := makeChains /@ signs@dict // Flatten // DeleteDuplicates
makeRules[dict_] := GroupBy[makeAllChains@dict, First@# &, Extract@{All, 2}]
nextLetter[rules_, wordPart_] := RandomChoice@rules[[wordPart]]
proceed[rules_, wordPart_, letter_] := With[
{r = wordPart ~~ letter},
proceed[rules, r, nextLetter[rules, r]]
]
proceed[rules_, wordPart_, stopSign] :=
StringTake[wordPart, -(StringLength@wordPart — 1)]
Правда, в ней пока что не учтён один нюанс: на данный момент она может генерировать слова только из словаря. Ведь все построенные нами сочетания начинаются от самого старта одного из слов словаря, а потому иные слова, кроме тех, по которым построены правила, не могут быть сгенерированы.
Для генерации случайных слов нам надо брать из буквосочетаний в правилах только некоторое количество последних букв. И при генерации слова, соответственно, брать из уже сгенерированной части слова то же количество букв. И уже по вот этому урезанному фрагменту извлекать список возможных следующих букв.
Удобно будет завести для этого соответствующую функцию, в которой учесть, что часть слова на данный момент может быть меньше интересующего нас количества букв, и в этом случае надо просто взять все имеющиеся.
cut[len_][wordPart_] := StringTake[wordPart, -Min[len, StringLength@wordPart]]
В принципе, можно было бы обойтись и одним набором параметров, однако с двумя набора проще вызывать эту функцию для трансформации списков.
Вот как будет выглядеть код, после внедрения в него урезания.
stopSign = "_";
signs[dict_] := stopSign ~~ # ~~ stopSign & /@ dict
cut[len_][wordPart_] := StringTake[wordPart, -Min[len, StringLength@wordPart]]
makeChain[word_, n_] := StringTake[word, n − 1] -> StringTake[word, {n}]
makeChains[s_] := Table[makeChain[s, n], {n, 2, StringLength@s}]
makeAllChains[dict_] := makeChains /@ signs@dict // Flatten // DeleteDuplicates
makeRules[len_][dict_] := GroupBy[makeAllChains@dict, cut[len]@First@# &, Extract@{All, 2}]
nextLetter[len_][rules_, wordPart_] := RandomChoice@rules[[cut[len]@wordPart]]
proceed[len_][rules_, wordPart_, letter_] := With[
{r = wordPart ~~ letter},
proceed[len][rules, r, nextLetter[len][rules, r]]
]
proceed[len_][rules_, wordPart_, stopSign] :=
StringTake[wordPart, -(StringLength@wordPart — 1)]
Тут, конечно, явно слишком много лишних повторений нового параметра, от них можно было бы избавиться, определив все эти функции внутри другой функции, но, в принципе, можно оставить, как есть.
Ну и полезно было бы иметь ещё одну вещь: функцию, которая обрабатывает словарь и по нему строит сразу много слов.
Реализация этой функции практически не отличается от тех строк, которые были выше использованы для запуска процесса генерации одного слова. Просто надо повторить этот процесс требуемое количество раз и класть результаты каждой генерации в список.
gen[len_][dict_, size_] := With[{rules = makeRules[len][dict]},Table[proceed[len][rules, stopSign, ""], size]
]
Сейчас, однако, несмотря на то, что мы используем цепочки букв конечного размера, функция генерации всё равно может случайно сгенерировать какое-то слово из исходного словаря. Поскольку нам нужны новые слова, из получившегося списка надо выбрать только слова, отсутствующие в изначальном словаре. Ну и заодно убрать все дубликаты.
gen[len_][dict_, size_] := With[
{rules = makeRules[len][dict]},
Table[proceed[len][rules, stopSign, ""], size]
// Select[! MemberQ[dict, #] &]
// DeleteDuplicates
]
В принципе, на этом месте у нас уже есть полностью готовый к практическому использованию инструмент. Разумеется, ещё имеет смысл написать какие-то функции, чтобы было проще запрашивать список городов по списку регионов. Возможно, к этому надо приделать некий пользовательский интерфейс, однако вся содержательная часть непосредственно словогенерации уложилась в код, влезающий на один экран.
И вместе с тем осмысление этого кода было практически тождественным осмыслению самого алгоритма на уровне «человеческих рассуждений», а не «компьютерных». Действительно, ни циклы, ни условия в явном виде не понадобились. Как не понадобилось обращение к элементам списка по порядковому номеру, вложенные друг в друга ветвления в коде и прочие «низкоуровневые», ассоциирующиеся с «настоящим программированием» вещи.
Можно предположить, что за всё это мы заплатили скоростью работы программы. И да, тут действительно есть несколько мест, где работу программы можно сделать чуть более быстрой, в обмен на ухудшение читаемости и понятности программы.
Однако уже в данном виде программа выдаёт ответ «мгновенно» — за столь короткое время, что кажется, будто бы ответ появился сразу же после запуска. Имеет ли смысл ускорять её ещё сильнее?
Наверно было бы неправильно просто закончить на этом, не показав результаты работы этой программы. Поэтому всё-таки немного скажу и об этом.
Эксперименты показывают, что при длине буквосочетаний 4 и более, возможное количество слов сильно сокращается, и одновременно с тем слова начинают слишком сильно напоминать слова исходного словаря.
Для оптимального баланса между «стильностью» и отличием от исходных слов хорошо подходит длина буквосочетаний 3 (соответствие трёх предыдущих букв одной следующей за ними).
Попробуем это на примере городов Московской, Воронежской и Брянской областей.
gen[3][words, 100]Шерелицыно, Грибаново, Нахабинка, Юбилка, Латная Посад, Хорловорохол, Электрогоробьевский, Черноговая Чигла, Архановский, Вождь Пролёв, Вербино, Вересенский, Павловка, Быковск, Абрамон, Ореховицк, Землянец, Пирогорногожск, Бронки, Юбилейный Ткач, Фирсаново, Фирский, Вишняковохопёрск, Сход, Ватутинский, Шиловая Усмань, Средний Пойма, Галь, Купавловка, Черустиль, Лытка, Яково, Чеховохово, Ильича, Пречицы, Электростантемироголовка, Кубино, Щёлковка, Обуховица, Шерельский, Щёлковская, Яковский, Высокольский, Гальный, Эртильщик, Шерея, Хотьковский, Наровск, Пересвет, Куровка, Яхромайск, Елань, Мишеронеж, Пеский, Шиловка, Жуково, Щёлковорино, Кратовка, Пущиновское, Пречисточный, Зелешинское
Если же хочется более вычурных названий, то можно пользоваться длиной 2.
Длина же 1 приводит к почти полной потере «стильности» названий. Хотя наверно тоже способна навести на какие-то идеи.
gen[1][words, 100]Купаво, Аний, Хргльеборскинска, Юбагов, Ивовк, Вий, Невкахо, Уволбревки, Жа, Гаяняногицый, Щель, Протыноск, Ве, Фий, Чехома, Групана, Юбускалорая, Дугоерсковосковньсий, Пий, Нов, Бучнко, Ще, Щёвонскало, Крхоенскадеульший, Кеедря, Моруньскавоузвсконовкатиниродиново, Тк, Ний, Елёвоов, Увскореня Талонирая, Трстужний, Ро, Юбигохо, Рая, Ольерк, Яханининово, Нирич, Елолая Лухртнальёвиценовоме, Руд, Миноглнки, Искиновскорукод, Ренса, На, Ат, Шеро, Мы, Новстискикишекиц, Чевлинахононский, Новетеча, Иль, Повноволк, Узька, Эруха, Яхожд, Не, Элины, Гай, Лерины, Яко, Сежены, Льнье, Юбречий, Нашеротрха, Аня, Оло, Хилене, Яхо-Аль, Фоговой, По, Зукиго-По, Икзно, Зашежбов, Щёло, Эремкакало, Егопьщельк, Жингуч, Наязнскабины Внововск, Га, Ко, Путель, Фрово, Юбийсканозле, Юбихная, Схоро, Грыч, Аль, Па, Илутутвстый, Лытезиратино, Хреугининоший Ма, Щёвскиламчи
Далее всё генерируется с длиной буквосочетаний 3.
Фэнтезийные города Англии.
Фэнтезийные города Мексики.
Фэнтезийные японские города.