?

Log in

No account? Create an account
о шаблонах в программировании - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

о шаблонах в программировании [мар. 5, 2013|01:35 am]
Anatoly Vorobey
Думаю, в программировании есть полезные шаблоны мышления. Только это не приевшиеся и по большей части бесполезные design patterns, а нечто более фундаментальное и одновременно аморфное. Такое, что трудно описать и непонятно, можно ли вообще научить.

Попробую объяснить на примере кода, который недавно писал - 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 раз быстрее набирает исходники и запускает компилятор? Нет. Лучшие программисты действительно отлаживают одну и ту же программу и чинят в ней баги намного быстрее средних и плохих, это верно. Но другой значительный вклад, а может и основной, в их эффективность - то, что они пишут намного меньше кода, и он намного проще, чем то, что выходит у простых смертных вроде нас с вами.

Если это полезный шаблон, то как его описать, определить, научить им пользоваться? Вот этого я как раз и не знаю. Какая абстрактная идея скрывается за решением представить разные черные блоки объектами разных цветов? Может быть, скажем, "вещи, которые выглядят одинаково на поверхности, могут быть совсем разными внутри". Но такая сентенция, с таким уровнем общности - это трюизм. Никому не поможет, если она будет написана в учебнике или высказана лектором. Почему мне пришла в голову эта идея? Может, потому, что я видел что-то похожее, когда читал другие исходники черт знает чего черт знает сколько лет назад, и вот этот шаблон отложился где-то в памяти: вот какой полезный трюк, типа. А сейчас всплыл. Но точно не потому, что меня этому кто-то пытался научить.

Может быть, полезные и важные шаблоны мышления в программировании есть, но они существуют главным образом как неясные метафоры у нас в голове, трудно определимые и не поддающиеся емкому описанию в словах; их трудно или невозможно преподать, ими можно лишь заразиться в процессе чтения исходников, своих и чужих, решения проблем, накопления опыта.
СсылкаОтветить

Comments:
Страница 1 из 3
<<[1] [2] [3] >>
[User Picture]From: leontodys
2013-03-04 11:50 pm

Идею под кат

Очень хотелось, чтобы когда я это читал было так, и можно было подумать.
(Ответить) (Thread)
[User Picture]From: avva
2013-03-04 11:54 pm

Re: Идею под кат

Хорошо, сделано. Я не подумал об этом, потому что не думаю, что идея так уж важна сама по себе, скорее это просто удобный пример. Но если очень хотелось, тогда можно и под кат.
(Ответить) (Parent) (Thread)
From: dmpogo
2013-03-05 12:18 am
Хм, интересно, практически идентичной идеей 'раскрасок карты' я пользуюсь уже 25 лет :) Действительно, однажды придумав, потом находятся многие применения.
(Ответить) (Thread)
[User Picture]From: amosk
2013-03-05 12:19 am
Кстати в тот момент когда у вас в тексте возникли черные объекты, мне сразу пришел в голову вопрос, а надо ли их сливать между собой и так как я еще не знал ответа не прочитав следующий абзац, то сразу возникла идея разные группы черных обозначать разными буквами.
И эта идея таки лежит на поверхности, раз придумывается прямо по ходу чтения постановки задачи.

На самом деле я думаю принцип который использован для придумывания этого приема - это индукция. А простота придумывания обусловлена что мы начинаем не с нуля а с готового формата карты, на котором уже реализованы частные случаи, и нам лишь надо обобщить их.
А "как известно" обобщение это одна из основных фоновых задач мозга человека.
(Ответить) (Thread)
[User Picture]From: nibb13
2013-03-05 12:37 am
Очень наглядная демонстрация того факта, что model и view - всё-таки разные вещи. :)
(Ответить) (Thread)
[User Picture]From: cema
2013-03-05 05:01 am
Ха, можно и так посмотреть.
(Ответить) (Parent) (Thread)
[User Picture]From: vvagr
2013-03-05 12:42 am
Как Вы рассказываете - пример оказывается совсем условным.

В Вашем последовательном изложении сначала чётко говорится, что чёрные блоки - это обычные чёрные блоки, потом говорится, что они не сливаются, потом оказывается, что они бывают слитыми. К этому моменту и у программиста мушка уже будет полностью сбита.

А ведь на самом деле тот, кто придумал эту игру, наверняка сразу придумал эти усложняющие игру чёрные объекты как отдельную сущность, о которой так и рассказал программисту. И в этой ситуации придумать имплементацию программисту гораздо проще.
(Ответить) (Thread)
[User Picture]From: bolk
2013-03-05 01:21 am
Может да, а может нет. Очень нередки случаи додумывания ПО на ходу.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: angerona
2013-03-05 12:55 am
подтверждаю: это не гениальная идея, а средняя, потому что она мне пришла в голову первой и тут же, без особых размышлений (а я не только не гениальный програмист, а даже и не средний и не програмист, так что будем считать, что идея вполне на поверхности :) ).
(Ответить) (Thread)
[User Picture]From: meshko
2013-03-05 01:05 am
Да, отличный пример и, наверное, можно использовать на интервью, если как-то обработать. Я считаю, что программист с опытом работы должен это видеть более или менее сходу.

А научить, думаю, можно. Я отлично помню, как в школе классе этак в 8 нас учили на системе Кумир Русскому Алгоритмическому Языку. Мне было очень скучно, я уже знал (ну или думал, что знал) Си и Паскаль. Но вот мы дошли до исполнителя "Чертежник", содранного с Лого. И там была куча задач -- давался сложный орнамент с повторениями и нужно было его нарисовать. И вот пока я их решал, я почувствовал, как у меня в голове что-то встало на место. То есть на первый взгляд те задачи не имеют никакого отношения к черным кубикам, но, судя по тому, что я их сразу же вспомнил, какое-то все-таки имеют.
Кстати, ничему подобному, скажем, в университете уже не учили, и очень зря. Человеку можно и нужно показать, как видеть такие обобщения, и однажды их увидев, уже потом видишь их легко.
(Ответить) (Thread)
[User Picture]From: meshko
2013-03-05 01:09 am
Кстати, интересно, а идея с соединениями -- вам правда пришла в голову, или это искусственная?
Мне такой вариант в головы бы ни за что не пришел и рассматривать я бы его не стал: слишком сложная обработка. Я могу восстановить как я пришел к "правильному" решению: я решил, что нужно в каждой ячейке хранить не букву, а объект с несколькими свойствами: цветом и, скажем, материалом. Ну и эта идея автоматически перетекает в следующую, что можно хранить только материал кубика и знать снаружи какого разные материалы цвета.
(Ответить) (Parent) (Thread)
[User Picture]From: vanja_y
2013-03-05 01:28 am
А потом появились блоки состоящие из нескольких черных и нескольких цветных кубиков...
(Ответить) (Thread)
[User Picture]From: topcoderer
2013-03-05 02:08 am
Выливаем воду из чайника и задача сводится к предыдущей :-)
(Ответить) (Thread)
[User Picture]From: e2pii1
2013-03-05 03:36 am
"
K хакеру подходит ламер, протягивает исходник своей неработающей программы и спрашивает:
- Где у меня ошибка?
- В ДHK!!!
"
:-)
(Ответить) (Thread)
From: huzhepidarasa
2013-03-05 03:57 am
Ага, а потом появляются прибитые клетки...
(Ответить) (Thread)
From: glukanat
2013-03-05 04:39 am
Это не только к программистам относится. К математикам он относится не меньше. Основная проблема додуматься до указанного выше - найти в модели случайные черты и забыть о них. Вот этот взгляд сверху в математике оччень помогает. Слова на тему сложности кода и прочая-прочая тоже более чем актуальны. В математике впрочем некоторые вещи в принципе без ухода в стратосферу не делаются. Если я правильно понимаю 100 программистов средней руки все-таки одного мощного программиста заменить могут...
(Ответить) (Thread)
[User Picture]From: substractor
2013-03-05 04:46 am
Я тоже сразу догадался про разные цвета черного. Значит внутри меня помирает программист..3(
(Ответить) (Thread)
[User Picture]From: cema
2013-03-05 05:03 am
Вариации могут быть в коде или в данных, так что...
(Ответить) (Thread)
From: a_shen
2013-03-05 05:35 am

наверно,

притчу Дейкстры про вагоны и туалеты Вы знаете, но, может быть, не все читатели видели - см. например
http://koi8.pp.ru/dijkstra.html
(Ответить) (Thread)
[User Picture]From: pavelm123
2013-03-08 11:07 pm

Re: наверно,

Спасибо за линк, очень интересно! Шикарное собеседование может получится на основе этой притчи.
(Ответить) (Parent) (Thread)
Страница 1 из 3
<<[1] [2] [3] >>