о шаблонах в программировании
Mar. 5th, 2013 01:35 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaДумаю, в программировании есть полезные шаблоны мышления. Только это не приевшиеся и по большей части бесполезные design patterns, а нечто более фундаментальное и одновременно аморфное. Такое, что трудно описать и непонятно, можно ли вообще научить.
Попробую объяснить на примере кода, который недавно писал - HTML5-версии игры Jelly No Puzzle.
В начальных уровнях игры по карте двигаются цветные блоки, и каждый раз, когда два блока одинакового цвета соприкасаются, они соединяются друг с другом. В исходниках для этого есть функция checkForMerges(), которая вызывается после каждого движения.
Кроме того, есть описание карты каждого уровня, начальной позиции. Оно сделано простым и наглядным - содержимое карты описывается построчно символами, пробел сооветствует пустой клетке, x - стенке, r/g/b - цветным клеткам red/green/blue соответственно. Например:
В этом примере две голубые клетки находятся рядом друг с другом, и две красные тоже. В самой игре они должны с самого начала быть соединенными. Это достигается простым вызовом checkForMerges() в начале уровня. Понятно, что это куда проще и элегантней, чем пытаться внутри карты указывать, какая клетка должна соединиться с какой, и во время обработки карты это выполнять.
Но теперь программист доходит до более продвинутых уровней, в которых в игре появляются черные клетки. У них есть несколько особенностей, которые необходимо учесть при написании их поддержки. Это не просто еще один цвет. На карте их легко изобразить: ну, буква b у нас уже занята, так используем букву B. Но поведение у них другое.
Во-первых, черные блоки, если они соприкасаются друг с другом, не сливаются, как другие цвета. Что ж, думает программист, я добавлю в функцию doOneMerge(), главную рабочую лошадку соединения блоков, исключение: если клетки черные, не соединять.
Но тогда возникает проблема с начальной картой: в ней есть целые блоки черных клеток, которые формируются к началу игры уже готовыми. До сих их формировал вызов checkForMerges() в начале уровня, но черные клетки он теперь соединять откажется. Придется, видимо, делать исключение и тут. Пусть функция checkForMerges() пример дополнительный аргумент - если он true, то будет соединять черные, если false, то не будет. В начале уровня мы вызовем с true, а в течение игры после каждого движения - с false.
Но тут программист смотрит на карты следующих уровней, и ругается вслух:
Есть уровни, в которых черные блоки с самого начала стоят рядом, и при этом не соединены. Это означает, что checkForMerges() в начале уровня сработает неправильно и соединит их все.
Что же делать? Кажется, нет иного выхода, как указывать на карте, какие черные клетки должны соединяться, а какие нет. Но это же очень неприятно. Придется добавлять кучу информации, когда описываешь уровень. Эта информация не влезет удобным образом в один символ, поэтому карта перестанет быть простой ASCII-картинкой, придется как-то усложнять. Можно, например, оставить место вокруг каждого символа, и ставить черточки-соединения там, где нужно:
В этом отрывке карты некоторые соседние 'B' соединены вместе, а некоторые нет. Но это будет довольно муторно выписывать, не говоря уж о том, что код, который считывает карту и строит из нее объекты, сильно усложнится.
Еще до того, однако, как программист пытается все это написать, ему приходит в голову одна идея. Это не гениальная идея, и надо специально отметить, что программист в этой истории (то есть я) не считает ее каким-то особенным достижением. С определенной точки зрения она буквально лежит на поверхности; но при этом верно и то, что есть много программистов, которые ее не заметят и будут продолжать примерно по указанному выше рецепту.
Идея следующая: черные блоки, которые стоят рядом и не соединяются - на самом деле блоки разных цветов; это просто обман зрения, что они все черные.
Немедленно после этого открытия все исключения, которые нужно было вносить в код, все усложнения и дополнительная информация - все это исчезает.
Во-первых, описание уровня остается простой ASCII-картинкой, в которой мы просто пользуемся (например) цифрами 0,1,2... для обозначения разных цветов "черный-0", "черный-1", "черный-2" итд.
Во-вторых, не нужно отдельного исключения в функции doOneMerge(): когда два черных блока встречаются, они не соединяются по той же причине, по которой не соединяются красный и зеленый.
В-третьих, не нужно особого поведения в начале уровня и дополнительного аргумента к checkForMerges(). В начале уровня клетки '0' все соединяются вместе, а клетки '1', '2' и '3', стоящие рядом с ними, остаются обособленными, как и требуется.
В-четвертых, даже в функции, проверяющей, закончил игрок уровень или нет, не нужно дополнительного кода. Я о ней раньше не упоминал, но эта функция проверяет, что для каждого цвета все его клетки соединены вместе; очевидно, для черного цвета нужно было делать исключение, потому что черные блоки для прохождения уровня соединять не надо (да и невозможно). Теперь это исключение можно убрать, потому что каждый из цветов черный-0, черный-1 и так далее, оказывается "законченным" уже в начале уровня, и не мешает проверке. Мелочь, а приятно.
Единственный дополнительный код, который вообще нужно писать - это в том месте, где мы собственно названию 'red' сопоставляем реальный HTML-цвет, и так же всем другим цветам, нам нужно черному-0, -1, -2 итд. всем прописать одинаковый черный цвет. И все. Вот и вся поддержка "черных блоков", которая, как думал поначалу программист, потребует немало строк кода.
Эта идея, которая пришла в голову программисту - пример определенного шаблона, паттерна мышления. Этот шаблон очень и очень полезен, потому что без него пришлось бы писать лишний код в четырех разных местах. Конечно, этот конкретный пример - игрушечный, и пришлось бы написать, скажем, 30 лишных строчек кода, и он был бы немного более сложен и неудобен. Но игрушечный пример хорошо иллюстрирует общий принцип. Та огромная разница в эффективности между лучшими программистами и худшими (или средними), о которой часто говорят и упоминают разницу то ли в 10, то ли в 25 раз (хотя исследования, которые якобы это доказали, сомнительны) - откуда она берется? Из того, что супер-программист в 10 раз быстрее набирает исходники и запускает компилятор? Нет. Лучшие программисты действительно отлаживают одну и ту же программу и чинят в ней баги намного быстрее средних и плохих, это верно. Но другой значительный вклад, а может и основной, в их эффективность - то, что они пишут намного меньше кода, и он намного проще, чем то, что выходит у простых смертных вроде нас с вами.
Если это полезный шаблон, то как его описать, определить, научить им пользоваться? Вот этого я как раз и не знаю. Какая абстрактная идея скрывается за решением представить разные черные блоки объектами разных цветов? Может быть, скажем, "вещи, которые выглядят одинаково на поверхности, могут быть совсем разными внутри". Но такая сентенция, с таким уровнем общности - это трюизм. Никому не поможет, если она будет написана в учебнике или высказана лектором. Почему мне пришла в голову эта идея? Может, потому, что я видел что-то похожее, когда читал другие исходники черт знает чего черт знает сколько лет назад, и вот этот шаблон отложился где-то в памяти: вот какой полезный трюк, типа. А сейчас всплыл. Но точно не потому, что меня этому кто-то пытался научить.
Может быть, полезные и важные шаблоны мышления в программировании есть, но они существуют главным образом как неясные метафоры у нас в голове, трудно определимые и не поддающиеся емкому описанию в словах; их трудно или невозможно преподать, ими можно лишь заразиться в процессе чтения исходников, своих и чужих, решения проблем, накопления опыта.
Попробую объяснить на примере кода, который недавно писал - HTML5-версии игры Jelly No Puzzle.
В начальных уровнях игры по карте двигаются цветные блоки, и каждый раз, когда два блока одинакового цвета соприкасаются, они соединяются друг с другом. В исходниках для этого есть функция checkForMerges(), которая вызывается после каждого движения.
Кроме того, есть описание карты каждого уровня, начальной позиции. Оно сделано простым и наглядным - содержимое карты описывается построчно символами, пробел сооветствует пустой клетке, x - стенке, r/g/b - цветным клеткам red/green/blue соответственно. Например:
[ "xxxxxxxxxxxxxx",
"x x",
"x r x",
"x b x",
"x x x",
"x b r x",
"x b r b x",
"xxx x xxx",
"xxxxx xxxxxxxx",
"xxxxxxxxxxxxxx", ],
В этом примере две голубые клетки находятся рядом друг с другом, и две красные тоже. В самой игре они должны с самого начала быть соединенными. Это достигается простым вызовом checkForMerges() в начале уровня. Понятно, что это куда проще и элегантней, чем пытаться внутри карты указывать, какая клетка должна соединиться с какой, и во время обработки карты это выполнять.
Но теперь программист доходит до более продвинутых уровней, в которых в игре появляются черные клетки. У них есть несколько особенностей, которые необходимо учесть при написании их поддержки. Это не просто еще один цвет. На карте их легко изобразить: ну, буква b у нас уже занята, так используем букву B. Но поведение у них другое.
Во-первых, черные блоки, если они соприкасаются друг с другом, не сливаются, как другие цвета. Что ж, думает программист, я добавлю в функцию doOneMerge(), главную рабочую лошадку соединения блоков, исключение: если клетки черные, не соединять.
Но тогда возникает проблема с начальной картой: в ней есть целые блоки черных клеток, которые формируются к началу игры уже готовыми. До сих их формировал вызов checkForMerges() в начале уровня, но черные клетки он теперь соединять откажется. Придется, видимо, делать исключение и тут. Пусть функция checkForMerges() пример дополнительный аргумент - если он true, то будет соединять черные, если false, то не будет. В начале уровня мы вызовем с true, а в течение игры после каждого движения - с false.
Но тут программист смотрит на карты следующих уровней, и ругается вслух:
Есть уровни, в которых черные блоки с самого начала стоят рядом, и при этом не соединены. Это означает, что checkForMerges() в начале уровня сработает неправильно и соединит их все.
Что же делать? Кажется, нет иного выхода, как указывать на карте, какие черные клетки должны соединяться, а какие нет. Но это же очень неприятно. Придется добавлять кучу информации, когда описываешь уровень. Эта информация не влезет удобным образом в один символ, поэтому карта перестанет быть простой ASCII-картинкой, придется как-то усложнять. Можно, например, оставить место вокруг каждого символа, и ставить черточки-соединения там, где нужно:
" x x",
" ",
" x b B B x",
" | | ",
" x b B g-g g x",
" | | | ",
" x b B B B g B b x",
" ",
В этом отрывке карты некоторые соседние 'B' соединены вместе, а некоторые нет. Но это будет довольно муторно выписывать, не говоря уж о том, что код, который считывает карту и строит из нее объекты, сильно усложнится.
Еще до того, однако, как программист пытается все это написать, ему приходит в голову одна идея. Это не гениальная идея, и надо специально отметить, что программист в этой истории (то есть я) не считает ее каким-то особенным достижением. С определенной точки зрения она буквально лежит на поверхности; но при этом верно и то, что есть много программистов, которые ее не заметят и будут продолжать примерно по указанному выше рецепту.
Идея следующая: черные блоки, которые стоят рядом и не соединяются - на самом деле блоки разных цветов; это просто обман зрения, что они все черные.
Немедленно после этого открытия все исключения, которые нужно было вносить в код, все усложнения и дополнительная информация - все это исчезает.
Во-первых, описание уровня остается простой ASCII-картинкой, в которой мы просто пользуемся (например) цифрами 0,1,2... для обозначения разных цветов "черный-0", "черный-1", "черный-2" итд.
"x x",
"xb01 x",
"xb0gg g x",
"xb023 g4bx",
Во-вторых, не нужно отдельного исключения в функции doOneMerge(): когда два черных блока встречаются, они не соединяются по той же причине, по которой не соединяются красный и зеленый.
В-третьих, не нужно особого поведения в начале уровня и дополнительного аргумента к checkForMerges(). В начале уровня клетки '0' все соединяются вместе, а клетки '1', '2' и '3', стоящие рядом с ними, остаются обособленными, как и требуется.
В-четвертых, даже в функции, проверяющей, закончил игрок уровень или нет, не нужно дополнительного кода. Я о ней раньше не упоминал, но эта функция проверяет, что для каждого цвета все его клетки соединены вместе; очевидно, для черного цвета нужно было делать исключение, потому что черные блоки для прохождения уровня соединять не надо (да и невозможно). Теперь это исключение можно убрать, потому что каждый из цветов черный-0, черный-1 и так далее, оказывается "законченным" уже в начале уровня, и не мешает проверке. Мелочь, а приятно.
Единственный дополнительный код, который вообще нужно писать - это в том месте, где мы собственно названию 'red' сопоставляем реальный HTML-цвет, и так же всем другим цветам, нам нужно черному-0, -1, -2 итд. всем прописать одинаковый черный цвет. И все. Вот и вся поддержка "черных блоков", которая, как думал поначалу программист, потребует немало строк кода.
Эта идея, которая пришла в голову программисту - пример определенного шаблона, паттерна мышления. Этот шаблон очень и очень полезен, потому что без него пришлось бы писать лишний код в четырех разных местах. Конечно, этот конкретный пример - игрушечный, и пришлось бы написать, скажем, 30 лишных строчек кода, и он был бы немного более сложен и неудобен. Но игрушечный пример хорошо иллюстрирует общий принцип. Та огромная разница в эффективности между лучшими программистами и худшими (или средними), о которой часто говорят и упоминают разницу то ли в 10, то ли в 25 раз (хотя исследования, которые якобы это доказали, сомнительны) - откуда она берется? Из того, что супер-программист в 10 раз быстрее набирает исходники и запускает компилятор? Нет. Лучшие программисты действительно отлаживают одну и ту же программу и чинят в ней баги намного быстрее средних и плохих, это верно. Но другой значительный вклад, а может и основной, в их эффективность - то, что они пишут намного меньше кода, и он намного проще, чем то, что выходит у простых смертных вроде нас с вами.
Если это полезный шаблон, то как его описать, определить, научить им пользоваться? Вот этого я как раз и не знаю. Какая абстрактная идея скрывается за решением представить разные черные блоки объектами разных цветов? Может быть, скажем, "вещи, которые выглядят одинаково на поверхности, могут быть совсем разными внутри". Но такая сентенция, с таким уровнем общности - это трюизм. Никому не поможет, если она будет написана в учебнике или высказана лектором. Почему мне пришла в голову эта идея? Может, потому, что я видел что-то похожее, когда читал другие исходники черт знает чего черт знает сколько лет назад, и вот этот шаблон отложился где-то в памяти: вот какой полезный трюк, типа. А сейчас всплыл. Но точно не потому, что меня этому кто-то пытался научить.
Может быть, полезные и важные шаблоны мышления в программировании есть, но они существуют главным образом как неясные метафоры у нас в голове, трудно определимые и не поддающиеся емкому описанию в словах; их трудно или невозможно преподать, ими можно лишь заразиться в процессе чтения исходников, своих и чужих, решения проблем, накопления опыта.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
Идею под кат
Date: 2013-03-04 11:50 pm (UTC)Re: Идею под кат
Date: 2013-03-04 11:54 pm (UTC)Re: Идею под кат
From:Re: Идею под кат
From:no subject
Date: 2013-03-05 12:18 am (UTC)no subject
Date: 2013-03-05 12:19 am (UTC)И эта идея таки лежит на поверхности, раз придумывается прямо по ходу чтения постановки задачи.
На самом деле я думаю принцип который использован для придумывания этого приема - это индукция. А простота придумывания обусловлена что мы начинаем не с нуля а с готового формата карты, на котором уже реализованы частные случаи, и нам лишь надо обобщить их.
А "как известно" обобщение это одна из основных фоновых задач мозга человека.
no subject
Date: 2013-03-05 12:37 am (UTC)no subject
Date: 2013-03-05 05:01 am (UTC)(no subject)
From:(no subject)
From:no subject
Date: 2013-03-05 12:42 am (UTC)В Вашем последовательном изложении сначала чётко говорится, что чёрные блоки - это обычные чёрные блоки, потом говорится, что они не сливаются, потом оказывается, что они бывают слитыми. К этому моменту и у программиста мушка уже будет полностью сбита.
А ведь на самом деле тот, кто придумал эту игру, наверняка сразу придумал эти усложняющие игру чёрные объекты как отдельную сущность, о которой так и рассказал программисту. И в этой ситуации придумать имплементацию программисту гораздо проще.
no subject
Date: 2013-03-05 01:21 am (UTC)(no subject)
From:(no subject)
From:no subject
Date: 2013-03-05 12:55 am (UTC)no subject
Date: 2013-03-05 01:05 am (UTC)А научить, думаю, можно. Я отлично помню, как в школе классе этак в 8 нас учили на системе Кумир Русскому Алгоритмическому Языку. Мне было очень скучно, я уже знал (ну или думал, что знал) Си и Паскаль. Но вот мы дошли до исполнителя "Чертежник", содранного с Лого. И там была куча задач -- давался сложный орнамент с повторениями и нужно было его нарисовать. И вот пока я их решал, я почувствовал, как у меня в голове что-то встало на место. То есть на первый взгляд те задачи не имеют никакого отношения к черным кубикам, но, судя по тому, что я их сразу же вспомнил, какое-то все-таки имеют.
Кстати, ничему подобному, скажем, в университете уже не учили, и очень зря. Человеку можно и нужно показать, как видеть такие обобщения, и однажды их увидев, уже потом видишь их легко.
no subject
Date: 2013-03-05 01:09 am (UTC)Мне такой вариант в головы бы ни за что не пришел и рассматривать я бы его не стал: слишком сложная обработка. Я могу восстановить как я пришел к "правильному" решению: я решил, что нужно в каждой ячейке хранить не букву, а объект с несколькими свойствами: цветом и, скажем, материалом. Ну и эта идея автоматически перетекает в следующую, что можно хранить только материал кубика и знать снаружи какого разные материалы цвета.
no subject
Date: 2013-03-05 01:28 am (UTC)no subject
Date: 2013-03-05 02:08 am (UTC)no subject
Date: 2013-03-05 03:36 am (UTC)K хакеру подходит ламер, протягивает исходник своей неработающей программы и спрашивает:
- Где у меня ошибка?
- В ДHK!!!
"
:-)
no subject
Date: 2013-03-05 03:57 am (UTC)no subject
Date: 2013-03-05 03:59 am (UTC)Кто-нибудь хочет 3Д?
no subject
Date: 2013-03-05 04:39 am (UTC)no subject
Date: 2013-03-05 04:46 am (UTC)no subject
Date: 2013-03-05 05:03 am (UTC)наверно,
Date: 2013-03-05 05:35 am (UTC)http://koi8.pp.ru/dijkstra.html
Re: наверно,
Date: 2013-03-08 11:07 pm (UTC)no subject
Date: 2013-03-05 05:55 am (UTC)no subject
Date: 2013-03-05 06:09 am (UTC)no subject
Date: 2013-03-05 06:10 am (UTC)no subject
Date: 2013-03-05 06:15 am (UTC)1. Одинаковые объекты сливаются друг с другом
2. Критерием одинаковости является цвет
После появления черных блоков модель приходится расширять и это возможно сделать несколькими способами:
1. Добавить исключение в принцип 1 – черные блоки не сливаются динамически
2. Дополнить принцип 2 – для черных блоков отображаемый цвет всего лишь маскирует «внутренний» цвет, который и является критерием идентичности
3. Вообще отменить принцип 2 и сделать критерием идентичности не цвет, а какое-то другое свойство
Стоимость реализации для 2-го способа оказалась ниже, чем для 1-го, и вообще он выглядит элегантнее (введение новой общей концепции «скрытого цвета» вместо простого исключения») и поэтому представляется предпочтительным. Но в целом каждый из способов ведет к созданию разных моделей, живущей по собственным законам. Например, при реализации 2-го способа возможны уровни, когда часть черных блоков может сливаться друг с другом, а другая часть – нет. В первом способе такая ситуация возникнуть не может.
Можно пойти еще дальше и разрешить отображаемому черному цвету скрывать не только различные «оттенки черноты», выраженные цифрами, но маскировать реальные цвета, кодируя их на карте заглавными буквами R, G, B и т.д. Тогда в игру добавится еще и тренировка памяти.
no subject
Date: 2013-03-05 06:36 am (UTC)Хотя я и не программист не разу )
no subject
Date: 2013-03-05 06:46 am (UTC)Ещё стороннему наблюдателю тут легко подумать, что импульсом к поиску "другого" ответа является лень, хотя для самого программиста это скорее любовь к прекрасному.
no subject
Date: 2013-03-05 06:55 am (UTC)А вообще, свойство "слипаемости" получается отдельным от "цвета".
А если в пределе при кодировании можно использовать принцип битовых полей.
P.S. Только я не понял как функционирует функция checkForMerges() (;)). По мне было бы логичнее сделать функцию, которой на вход подаётся пара цветов - она возвращает результат блоки "вместе" или нет. Её можно использовать в обоих функциях - при движении и в конце. Правда придётся на выходе использовать три значения - блоки "раздельные", "слипшиеся", "раздельные, но пусть так и будет".
P.P.S. Чёрный цвет - два вида, "слипающиеся" и "не слипающиеся", или просто "много разных цветов"?
no subject
Date: 2013-03-05 07:10 am (UTC)Одного и того же геймплейного эффекта всегда можно достичь многими различными методами. Эти методы могут отличаться по сложности реализации в десятки раз.
Но там это вопрос не столько гениальности, сколько успешности, и не столько программистов, сколько команд. Эффект применения особенно чувствуется, если о нём знают гейм-дизайнеры (т.е. постановщики задач программистам).
По моему опыту, это вообще первое правило, только не программирования, а product management.
no subject
Date: 2013-03-05 10:25 am (UTC)(no subject)
From:(no subject)
From:(no subject)
From:no subject
Date: 2013-03-05 07:25 am (UTC)