tag:blogger.com,1999:blog-13541481323984180752024-03-21T01:31:53.005-07:00Бредогенератор работаетallchemisthttp://www.blogger.com/profile/17364609418296639508noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-1354148132398418075.post-67245473256325579702011-06-22T06:05:00.000-07:002011-06-25T02:53:58.839-07:00Lambda: the Gathering - поиграть штангой в карты<div dir="ltr" style="text-align: left;" trbidi="on">На прошедшем ICFPC авторы предложили мозговыносящую задачу, впрочем, как и в прошлые годы. Хотя, в этом году неплохое преимущество было у штангистов.<br />
<br />
По формату этот ICFPC напоминал Google AI Challenge (вероятно, оттуда они и потырили часть идеи).<br />
<br />
<b><span style="font-size: small;">Описание задачи.</span></b><br />
<br />
Предлагается написать бота, который будет сражаться с другими ботами турнирным методом. Боты играют попарно и ходят по-очереди. У каждого игрока имеется 256 слотов и фиксированный набор карт. Каждый слот имеет поле и очки жизней (хит-поинты). Поле слота может содержать либо целое число от 0 до 65535, либо функцию. Хит-поинты слота могут иметь значение от -1 до 65535. Слот считается живым, если его хит-поинты больше нуля. В начале матча каждый слот инициализируется тождественной функцией и 10 000 хит-поинтами.<br />
<br />
На каждом ходу игрок может выполнить одно из двух действий: 'левое' либо 'правое'. Левое действие применяет заданную карту (функцию) к полю заданного слота. Правое применяет поле слота (содержащее функцию) к карте. Действие завершается ошибкой, если применяемая карта или поле не являются функцей, или заданный слот мертв.<br />
<br />
Ход завершается, если происходит ошибка, если количество применений функций в результате левых или правых действий (включая их самих) превысит 1000 (фактически, это ограничение глубины стека виртуальной машины), или если применение завершается корректно без превышения этого лимита. В последнем случае полю слота присваивается полученное значение, а во всех других случаях оно перезаписывается в тождественную функцию. Все побочные эффекты, произведенные применениями функций, не откатываются, даже если применение завершилось аварийно.<br />
<br />
<br />
Каждому игроку отводится на матч не более 100 000 ходов. Игра может завершиться раньше, если все слоты игрока мертвы. В любом случае, победа присуждается тому игроку, у кого осталось больше живых слотов. Если слотов осталось поровну, засчитывается ничья.<br />
<br />
<b>Карты</b><br />
<br />
Дан следующий набор карт. <br />
<ul style="text-align: left;"><li class="level1"><div class="li">Карта “I” - тождественная функция.</div></li>
<li class="level1"><div class="li">Карта “zero” - целое число 0 (не функция).</div></li>
<li class="level1"><div class="li">Карта “succ” - функция, принимающая аргумент n и возвращающая n+1, если n<65535 (или 65535, если n=65535). Возвращает ошибку, если n - не целое число.</div></li>
<li class="level1"><div class="li">Карта “dbl” - функция, принимающая аргумент n и возвращающая n*2, если n<32768 (или 65535, если n>=32768). Возвращает ошибку, если n - не целое число.</div></li>
<li class="level1"><div class="li">Карта “get” - функция, принимающая аргумент i и возвращающая значение поля i-го слота игрока-зашитника, если этот слот жив. Возвращает ошибку, если i - некорректный номер слота, или слот мертв.</div></li>
</ul><ul style="text-align: left;"><li> Карта “put” - функция, принимающая (неиспользуемый) аргумент и возвращающая функцию #'identity.</li>
</ul><ul style="text-align: left;"><li>Карта "S" - S-комбинатор λf.λg.λx.fx(gx).</li>
<li>Карта "K" - K-комбинатор λx.λy.x.</li>
<li>Карта "inc" - увеличивает на 1 хит-поинты слота защитника, если слот жив и количество хит-поинтов не привысит допустимого лимита.</li>
<li>Карта "dec" - увеличивает на 1 хит-поинты слота противника, если слот жив.</li>
<li>Карта "attack" - функция, принимеющая аргумент i и возвращающая другую функцию, которая (будучи применена) примет другой аргумент j и возвратит еще одну функцию, которая (будучи применена) примет аргумент n и уменьшит на n*9/10 хитпоинты (255-i)-го слота противника, при этом уменьшит также и хитпоинты атакующего j-го слота на n, после чего возвратит тождественную функцию.</li>
<li> Карта "help" - действует похожим образом, но, вместо уменьшения жизней слота противника на n*9/10, увеличивает количество жизней слота защитника на n*11/10.</li>
<li>Карта "copy" - функция от i, которая возвращает функцию от j, которая копирует содержимое (255-i)-го слота притивника в поле j-го слота защитника.</li>
<li>Карта "revive" - функция, которая оживляет слот зашитника, давая ему 1 хит-поинт.</li>
<li>Карта "zombie" - функция от i, которая возвращает функцию от x, которая запишет x в (255-i)-й слот противника, если этот слот мертв, устанавливает его хит-поинты в -1 и возвращает тождественную функцию.</li>
</ul>Непосредственно перед началом каждого хода игрока функция в поле каждого слота с хит-поинтами -1 автоматически применяется к тождественной функции начиная с первого мертвого слота до конца по возрастающей. При каждом из таких автоматических применений происходит ошибка. если поле содержит не функцию, или количество применений функции привысило 1000. Если возникает ошибка, то слот перезаписывается тождественной функцией, а хитпоинты слота устанавливаются в 0.<br />
<br />
Кроме того, во время такого автоматического применения эффекты четырех карт изменяются:<br />
<ul><li class="level1"><div class="li">Эффекты карт “inc” и "dec" меняются между собой.</div></li>
<li class="level1"><div class="li">Третья функция в карте “attack” увеличивает, а не уменьшает хит-поинты атакуемого слота. </div></li>
<li class="level1"><div class="li">Третья функция в карте “help” уменьшает, а не уменьшает хит-поинты подлечиваемого слота.</div></li>
</ul>Такое автоматическое применение позволяет делать нетривиальные вещи с помощью зомбей.<b> </b><br />
<br />
<b>Виртуальная машина</b><br />
<br />
Первое, что необходимо было сделать - написать виртуальную машину, которая симулировала бы состояние обоих игроков. Матчи велись отдельной спарринг-программой, которая принимала от ботов через stdin три значения. Так, "1 dbl 10" соответствует левому применению карты dbl к десятому слоту, а "2 zero 0" - правому применению слота 0 к карте zero. Это означает, что простейший бот мог просто посылать одну и ту же команду на каждом ходу, но для сколько-ниудь осмысленных действий необходимо было знать текущее состояние слотов.<br />
<br />
На написание первого приближения виртуальной машины у нас ушел весь первый день. К сожалению, мы долго тупили, проникаясь укуренностью остальной части задачи. Целый день на симулятор - это оказалось слишком много.<br />
<br />
<b>Собственно, штанга</b><br />
<br />
В середине первого дня в команду пришел еще один участник, который что-то соображал в комбинаторной логике. И это было очень здорово, потому как, чтобы натравить одного зомби, пришлось бы строить такую функцию: <span class="post ">S(K(S(K(zombie(zero)(1)))(get)))(succ)(zero), а это уже целое заклинание некромантии.</span><br />
<br />
<span class="post ">К концу второго дня стало ясно в общих чертах, как нужно сочетать карты с помощью SKI-комбинаторов, чтобы получать тот или иной эффект. К восьми часам утра я таки запостил на тестовый сервер примитивного бота, который атаковал всех по-очереди, пока не заканчивались хит-поинты, после чего я пошел спать.</span><br />
<br />
<span class="post ">Как ни странно, даже такой тупой бот выиграл бот 16 из 23 матчей, но еще в трех матчах он нарушил спецификацию и был дисквалифицирован. Это означало, что где-то в симуляторе были ошибки. Перспектива шерстить весь код на наличие несоответствий была безрадостной, но куда деваться.</span><br />
<span class="post "><br />
</span><br />
<span class="post ">Третий день стало понятно, что хорошие места в турнирной таблице нам не светят, потому как в конфе icfpc@cjr пробегали понты типа "я размочил все слоты за 500 ходов", а мы тогда знали, как убить все слоты за отведенные 100 000 ходов. К концу соревнования довольно результативно полистали код симулятора на предмет ошибок и оформили минимально вменяемую стратегию бота, после чего засабмитили на официальный и тестовый серверы и пошли спать. Всех ошибок в симуляторе мы обнаружить не смогли, но до дисквалификации на тестовом сервере он смог выиграть 12 из 42 матчей (к тому времени соперники стали умнее).</span><br />
<span class="post "><br />
</span><br />
<span class="post "><b>Итоговый бот</b></span><br />
<span class="post "><br />
</span><br />
<span class="post ">Виртуальная машина интерпретировала операции в последовательности инструкций, которые одна за другой передавались спарринг-программе. Одна операция могла преобразовываться в много или очень много инструкций. Серьезную проблему представляло получение больших чисел, т.к. для этой цели были доступны только карты zero, succ и dbl. Так, для записи числа 8 в слот 3 генерировалась следующая очередь:</span><br />
<div style="font-family: "Courier New",Courier,monospace;"><br />
</div><div style="font-family: "Courier New",Courier,monospace;"><span class="post ">1 put 3 ;; #'identity</span></div><div style="font-family: "Courier New",Courier,monospace;"><span class="post ">2 0 zero ;; 0</span></div><div style="font-family: "Courier New",Courier,monospace;"><span class="post ">1 succ 3 ;; 1</span></div><div style="font-family: "Courier New",Courier,monospace;"><span class="post ">1 dbl 3 ;; 2</span></div><div style="font-family: "Courier New",Courier,monospace;"><span class="post ">1 dbl 3 ;; 4</span></div><span class="post "><span style="font-family: "Courier New",Courier,monospace;">1 dbl 3 ;; 8</span></span><br />
<span class="post "><br />
</span><br />
<span class="post ">Доступ к слотам противника осуществлялся в обратном порядке, и, чтобы атаковать его нулевой слот, нужно было хранить в одном из слотов число 255. Первые слоты самые ценные, но и убить их наиболее трудно, потому что номер слота приходится "набирать" последовательным применением succ и dbl в определенном порядке, а это лишние ходы. Поэтому было выделено слотов-хранилищ, которые были своего рода кешем, позволяющим использовать имеющиеся числа повторно. Три слота-хранилища были расположены вначале, т.к. к ним наиболее быстрый доступ, а противнику их сложнее всего убить. Тем не менее, в начале каждого хода проверялось, живы ли эти слоты, и если они какой-либо из них был мертв, текущая очередь команд прерывалась, создавалась новая очередь, применяющся карту revive, а по ее завершению начиналось оживление нового слота, либо возвращалась прерванная очередь. За одну нашу атаку бот снимал с противника 3686 хит-поинтов, но при этом сам терял 4096 хит-поинтов. Если слот противника умирал, то значение слота-хранилица увеличивалось на 1, и атаковался следующий слот. Когда наши хит-поинты подходили к концу, генерировалась очередь, за один ход многократно применяющая карту inc. Полноценную рекурсию сделать не получилось, но многократное удвоенное действие позволило за один ход наращивать 1000 хит-поинтов (больше нельзя, но это тоже неплохо). Когда силы бота восстанавливались, то он снова переходил к атаке.</span><br />
<span class="post "><br />
</span><br />
<span class="post ">Вообще говоря, суть конкурса ICFPC в том, что авторы в игровой форме ставят сложные задачи так, чтобы знание предметной области было не обязательным (хотя и желательным). Короче говоря, мы слили, хотя и не так позорно, как в прошлом году. Не помог нам даже великий и славный common lisp (хотя и очень облегчил задачу, потому как жаберы и сиплюсплюсники страшно матерились, и это понятно). В целом, очень интересная задача, заставляет шевелить даже затекшие мозги. Код финального сабмишна, если вдруг кому интересно, лежит по адресу <a href="http://lisper.ru/files/icfpc/skobochka.tar.gz">http://lisper.ru/files/icfpc/skobochka.tar.gz</a></span><br />
<br />
<br />
<span class="post ">Спасибо всем участникам (turtle, gltronred, laser123, dmitry_vk).</span><br />
<span class="post "><br />
</span><br />
<span class="post ">ЗЫ. По завершении конкурса авторы написали, что картинки (на сайте кроме карт были еще две картинки) не так просты, как кажется. Первую картинку можно полуить из второй, а вторую из первой</span>:<br />
<div style="font-family: "Courier New",Courier,monospace;"><br />
</div><div style="font-family: "Courier New",Courier,monospace;">java -jar new_books.png > lambda.png</div><div style="font-family: "Courier New",Courier,monospace;">java -jar lambda.png > new_books.png</div><div style="font-family: "Courier New",Courier,monospace;"></div><br />
Вот уж действительно боевые человекоподобные японцы :)</div>allchemisthttp://www.blogger.com/profile/17364609418296639508noreply@blogger.com0tag:blogger.com,1999:blog-1354148132398418075.post-81718795342293901182011-06-22T03:43:00.000-07:002011-06-22T03:43:20.684-07:00Перевод книги ANSI Common Lisp, #2<div dir="ltr" style="text-align: left;" trbidi="on">К сожалению, выпуск перевода затягивается издательством на неопределенный срок из-за серьезных финансовых проблем. Короче говоря, они на грани банкротства.<br />
<br />
Если их трудности утрясутся, то ожидать выпуска книги можно в середине осени. Если им таки настанет крышка, то доработаем и издадим сами, вопрос с правообладанием как-нибудь разрешим.</div>allchemisthttp://www.blogger.com/profile/17364609418296639508noreply@blogger.com11tag:blogger.com,1999:blog-1354148132398418075.post-80345662552087149882011-02-14T08:20:00.000-08:002011-02-16T01:39:49.832-08:00Перевод книги ANSI Common Lisp<div dir="ltr" style="text-align: left;" trbidi="on">Сабж завершен. До верстки над ним поработают редакторы, до выхода в печать еще ориентировочно два-три месяца.<br />
<br />
Такие дела.<br />
<br />
upd.<br />
<br />
Всего 17 глав.<br />
Если кто-то желает взять одну или несколько глав на детальную вычитку (<b>важна техническая сторона вопроса</b>, грамматику и т.д. будет править редактор), отписывайте номер главы в коментах.<br />
<br />
Ожидают своей участи главы:<br />
<br />
4, 5, 6, 7, 8, 9, 12, 14, 15, 16, 17<br />
<br />
<b>ЗЫ.</b><br />
Высылаю pdfку на почту, не выкладываю в сети по понятным соображениям. Очень надеюсь, что она не окажется в сети (уже хотя бы потому, что на настоящий момент она наверняка содержит баги, а чтение бажных книжек может быть вредно)<br />
<br />
ЗЗЫ.<br />
Для тех, кто интересовался стоимостью печатного издания будущей книги, получил ответ: <span class="Apple-style-span" style="font-family: inherit;">"<span class="Apple-style-span" style="border-collapse: collapse;">Сколько будет стоить книга я не в курсе. Этот вопрос в</span><span class="Apple-style-span" style="border-collapse: collapse;">компетенции высшего руководства.</span>"</span></div>allchemisthttp://www.blogger.com/profile/17364609418296639508noreply@blogger.com22tag:blogger.com,1999:blog-1354148132398418075.post-12333985484114194142010-12-02T05:47:00.000-08:002011-02-15T12:26:32.132-08:00Замечания по отладке в SBCL и Slime<div dir="ltr" style="text-align: left;" trbidi="on">Оригнальный текст: <a href="https://gist.github.com/659495#file_sbcl_debugging_notes.txt">https://gist.github.com/659495#file_sbcl_debugging_notes.txt</a>, Nikodemus Siivola<br />
<br />
<b>0</b> Умение сокращать размеры тестового набора - это важный навык, не зависящий от языка или инструментария. Это целое искусство - сокращать до премлемых размеров количество примеров, приводящих к появлению ошибок, неверных результатов (например, моменты, связанные с указанием полного пути или текущей директории, выполнением кода в Slime или вне него). С одной стороны, чем меньше тестовых примеров, тем лучше, но здесь надо соблюдать осторожность. Если вы в состоянии распознать баг за пару минут каким-либо другим методом, очевидно, глупо тратить несколько часов на сжатие тестового набора. Однако, если другими методами вы не в состоянии этого сделать, придется смириться с временными затратами.<br />
<br />
<b>1</b> Осторожное программирование. Речь не только о том, как избегать ошибок в коде, но и о том, как делать его легкоотлаживаемым. Избегайте IGNORE-ERRORS, не позволяйте компилятору безмолвно проглатывать ошибки. Иногда это может быть полезным, но чем больше таких мест в коде, тем сложнее использовать *BREAK-ON-SIGNALS*. Избегайте SAFETY 0 как чумы - он скроет множество огрехов. Не используйте DEBUG 0 - от этого вы не получите выгоды. Определяйте PRINT-OBJECT методы для собственных объектов, давайте им имена. Никогда не употребляйте INTERRUPT-THREAD или WITH-TIMEOUT, пока вы не будете точно уверены в том, что делаете, и пока не поймете, почему их лучше не использовать.<br />
<br />
<b>2</b> Не задумывайтесь там, где не следует. Просто внимательно вчитывайтесь в сообщения об ошибках. Иногда они бесполезны, но иногда вы рискуете упустить много полезной информации.<br />
<br />
<b>3</b> Изучайте возможности инструментария. Здесь стоит остановиться подробнее.<br />
<br />
<div style="text-align: left;"><b> 3.0</b> M-. - это отличная вещь. Нажимая 'v' в отладочном окне Slime, вы также попадаете в участки кода, предоставляющего достаточно много информации для отладки, но M-. можно использовать везде.</div><br />
<b> 3.1</b> Slime Inspector - один из главных отладочных инструментов. Пригодится он вам или нет - зависит от задачи, но будет полезно познакомьться с его возможностями, они того стоят.<br />
<br />
<b> 3.2</b> Обратная трассировка (backtrace) в SBCL на настоящий момент реализована не лучшим образом, но ее использование может принести определенные плоды. Просто загляните (вызовите любую ошибку) в REPL и выясните, что происходит. Поразвлекайтесь с штатным отладчиком SBCL и модным Slime Debugger, прежде чем будете пользоваться ими на практике, и тогда они перестанут казаться вам враждебными. О том, как пользоваться обратной трассировкой, я напишу в другой раз.<br />
<br />
<b> 3.3</b> Разберитесь с *BREAK-ON-SIGNALS* и TRACE. Не забывайте, что SBCL предоставляет некоторые расширения возможностей TRACE.<br />
<br />
<b> 3.4</b> Пошаговое выполнение по сути не является отладочным инструментом. Я считаю, что это всего лишь средство наблюдения за ходом исполнения. Иногда это может быть полезным в отладке, но только при компиляции кода с DEBUG 3, когда (STEP (FOO)) доставит вас в нужное место.<br />
<br />
<b> 3.5</b> Пользуйтесь M-RET (macroexpand) в Slime. Попробуйте (SETF *PRINT-GENSYM* NIL) и посмотрите, что будет происходить. Это несет с собой потенциальные опасности, но зато может позволить легко копировать и вставлять код, в который раскрывается ваш тестовый пример. (Замена раскрытий макросов в пакете COMMON-LISP, как правило, нецелесообразна, но в пользовательских пакетах может быть очень полезным.)<br />
<br />
<b> 3.6</b> Если ничего не помогло, попробуйте (sb-ext:restrict-compiler-policy 'safety 3) и (sb-ext:restrict-compiler-policy 'debug 3), после чего перекомпилируйте весь код. Теперь отладка станет легче. Если ошибка исчезла, либо (а) вы ошиблись с типами (или допустили похожую ошибку) в коде, собранном с SAFETY 0, и она не терялась благодаря IGNORE-ERRORS или HANDLER-CASE, либо (б) вы обнаружили баг в SBCL: вообще говоря, политика компилятора не должна изменять поведение кода, за исключением нескольких допускаемых ANSI случаев при использовании SAFETY 3, или же когда высокий уровень отладки препятствует оптимизации хвостовой рекурсии. Знающие Scheme объяснят вам, что это может иметь значение.<br />
<br />
<b> 3.7</b> DISASSEMBLE не есть штатное средство отладки, но иногда может быть полезным. Это зависит от сути имеющейся проблемы.<br />
<br />
<b>4</b> Расширения отладочной печати. Часто это простейшее средство, которым можно воспользоваться. Не стыдитесь этого.<br />
<br />
<b> 4.1</b> Пользуйтесь специальными переменными:<br />
<br />
(LET ((*DEBUG* :MAGIC)) ...) и, где-либо в коде,<br />
<br />
(WHEN (EQ :MAGIC *DEBUG*) (PRINT (LIST :FOO FOO)))<br />
<br />
Будучи ленивым, я обычно использую глобальные переменные для управления отладочной печатью, как в примере выше. Это позволяет использовать ее только при необходимости, определять, на каком участве кода происходит вызов и т.д.<br />
<br />
<b> 4.2</b> Не бойтесь вставлять в отлаживаемый код (break "foo=~S" foo) или подобные вызовы.<br />
<br />
<b> 4.3 </b>SB-DEBUG:BACKTRACE все же можно использовать.<br />
<div><br />
</div></div>allchemisthttp://www.blogger.com/profile/17364609418296639508noreply@blogger.com1tag:blogger.com,1999:blog-1354148132398418075.post-17945359204901408712010-11-19T10:39:00.000-08:002010-11-27T06:28:50.657-08:00Решение задачи о двух спиралях с помощью пакета ANNIL<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;">Задача о двух спиралях известна как трудная, с высокой степенью нелинейности, задача для тестирования алгоритмов классификации.</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;">Две спирали, "одна в другой", симметричные относительно центра и поворота на 180 градусов.</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;">Обучающее множество генерируется так ("</span><a href="https://github.com/allchemist/annil/tree/master/tests/two-spirals.lisp"><span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;">annil/tests/two-spirals.lisp</span></a><span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;">")</span><br />
<br />
<div class="code"><span class="paren1"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/m_defun.htm"><i><span class="symbol"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">defun</span></span></i></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> 2spiral-radius </span><span class="paren2"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">i</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><span class="paren2"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">/ </span><span class="paren3"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/a_st.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">*</span></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> 6.5 </span><span class="paren4"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/a__.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">-</span></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> 104 i</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> 104</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><br />
<span class="paren1"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/m_defun.htm"><i><span class="symbol"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">defun</span></span></i></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> 2spiral-angle </span><span class="paren2"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">i</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><span class="paren2"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/a_st.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">*</span></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> i </span><span class="paren3"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">/ </span><span class="paren4"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/f_coerce.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">coerce</span></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/v_pi.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">pi</span></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> '</span><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/t_short_.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">single-float</span></a></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> 16</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><br />
<span class="Apple-style-span" style="font-family: Verdana, sans-serif;"><br />
</span> <br />
<span class="paren1"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/m_defun.htm"><i><span class="symbol"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">defun</span></span></i></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> genpat-2spirals </span><span class="paren2"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">&optional </span><span class="paren3"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">output-ranges '</span><span class="paren4"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">-1.0 1.0</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"><br />
</span><span class="paren2"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/s_let_l.htm"><i><span class="symbol"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">let</span></span></i></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><span class="paren3"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="paren4"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">patterns </span><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/a_nil.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">nil</span></a></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"><br />
</span><span class="paren3"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/m_dotime.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">dotimes</span></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><span class="paren4"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">i 97</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"><br />
</span><span class="paren4"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/s_let_l.htm"><i><span class="symbol"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">let</span></span></i></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><span class="paren5"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="paren6"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">r </span><span class="paren1"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">2spiral-radius i</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"><br />
</span><span class="paren6"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">a </span><span class="paren1"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">2spiral-angle i</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"><br />
</span><span class="paren5"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/s_let_l.htm"><i><span class="symbol"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">let</span></span></i></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><span class="paren6"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="paren1"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">x </span><span class="paren2"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/a_st.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">*</span></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> r </span><span class="paren3"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/f_sin_c.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">sin</span></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> a</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"><br />
</span><span class="paren1"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">y </span><span class="paren2"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/a_st.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">*</span></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> r </span><span class="paren3"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/f_sin_c.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">cos</span></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> a</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"><br />
</span><span class="paren6"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/m_push.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">push</span></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><span class="paren1"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/a_list.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">list</span></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><span class="paren2"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">make-matrix 2 </span><span class="keyword"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">:initial-contents</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> `</span><span class="paren3"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">,x ,y</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"><br />
</span><span class="paren2"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">make-matrix 1 </span><span class="keyword"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">:initial-element</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><span class="paren3"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/f_firstc.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">first</span></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> output-ranges</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"><br />
patterns</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"><br />
</span><span class="paren6"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/m_push.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">push</span></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><span class="paren1"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/a_list.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">list</span></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><span class="paren2"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">make-matrix 2 </span><span class="keyword"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">:initial-contents</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> `</span><span class="paren3"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">,</span><span class="paren4"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/a__.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">-</span></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> x</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> ,</span><span class="paren4"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/a__.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">-</span></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> y</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"><br />
</span><span class="paren2"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">make-matrix 1 </span><span class="keyword"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">:initial-element</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><span class="paren3"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/f_firstc.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">second</span></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> output-ranges</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"><br />
patterns</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"><br />
</span><span class="paren3"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/f_revers.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">nreverse</span></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> patterns</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></div><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;">Теперь создадим классификатор, обученный разделять эти спирали.</span><br />
<br />
<div class="code"><span class="paren1"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/m_defpar.htm"><i><span class="symbol"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">defparameter</span></span></i></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><span class="special"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">*classifier*</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"><br />
</span><span class="paren2"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">make-cascor-classifier </span><span class="special"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">*patterns*</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/a_nil.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">nil</span></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> 'tanh-fn 0.8 20<br />
`</span><span class="paren3"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="paren4"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="keyword"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">:iter</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> . 100</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><span class="paren4"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="keyword"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">:verbosity</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> . 2</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><span class="paren4"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="keyword"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">:cc-iter</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> . 100</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><span class="paren4"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="keyword"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">:cc-candidates</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> . 5</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></div><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;">Процедура обучения сети состоит из последовательного добавления нового узла (и настройки его входных весов) и настройки выходных весов</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;">Аргументы обучающей процедуры:</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"><br />
</span><br />
<b><span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;">*patterns*</span></b><span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"> - обучающий набор (пары вход -- желаемый выход)</span><br />
<b><span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;">nil</span></b><span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"> - тестовый набор для проведения перекрестной проверки (cross-validation, метод предупреждения переобучения сети)</span><br />
<b><span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;">'tanh-fn</span></b><span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"> - функция активации узлов.</span><br />
<b><span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;">0.8</span></b><span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"> - порог уверенной классификации. (выход в промежутке [-1.0;-0.2] - отрицательная классификация, [0.2;1.0] - положительная, [-0.2;0.2] - неуверенная, рассматривается как неверная)</span><br />
<b><span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;">20</span></b><span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"> - количество добавляемых скрытых узлов.</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;">Ассоциативный список содержит параметры самого алгоритма (довольно удобный способ хранения и передачи аргументов, не надо париться с порядком последовательности). В примере приведены обязательные аргументы (количество итераций настройки выходов (:iter), входов (:cc-iter), кандидатов на добавление в сеть (:cc-candidates, выбирается лучший из заданного количества узлов, обученных обученных).</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;">Параметр verbosity не обязательный, по умолчанию 0. Определяет "многословность", количество выдаваемой информации (0 - ничего не говорит, 4 - выдает максимум информации)</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;">Также алгоритму могут быть сообщены дополнительные параметры, влияющие на скорость сходимости, которые имеют по-умолчанию хорошие значения для случайной задачи, но могут быть настроены, а также параметры преждевременной остановки в случае длительного отсутствия или слишком слабого улучшения, а также некоторые другие полезные параметры. О них надо будет написать документацию.</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;">Дополнительная опция test-fn (последний аргумент) позволяет выводить состояние системы после обучения каждого нового узла, например, рисовать картинки с помощью gnuplot.</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;">Вернемся к процессу обучения. С параметром verbosity=2 вывод процедуры выглядит следующим образом:</span><br />
<br />
<div class="code"><span class="paren1"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/m_defpar.htm"><i><span class="symbol"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">defparameter</span></span></i></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><span class="special"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">*classifier*</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"><br />
</span><span class="paren2"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">make-cascor-classifier </span><span class="special"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">*patterns*</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/a_nil.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">nil</span></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> 'tanh-fn 0.8 20<br />
`</span><span class="paren3"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="paren4"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="keyword"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">:iter</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> . 100</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><span class="paren4"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="keyword"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">:verbosity</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> . 2</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><span class="paren4"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="keyword"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">:cc-iter</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> . 100</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><span class="paren4"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="keyword"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">:cc-candidates</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> . 5</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"><br />
#'</span><span class="paren3"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/a_lambda.htm"><i><span class="symbol"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">lambda</span></span></i></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><span class="paren4"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">net iter</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"><br />
</span><span class="paren4"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">visual-classify-2spirals net </span><span class="special"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">*pat*</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> 0.8<br />
</span><span class="paren5"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/f_format.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">format</span></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/a_nil.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">nil</span></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><span class="string"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">"'/tmp/test-known~A.png'"</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> iter</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"><br />
</span><span class="paren4"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">visual-test-2d net 10000 6.5 '</span><span class="paren5"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">-1.0 1.0</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> 0.8<br />
</span><span class="paren5"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">(</span><span class=""><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/f_format.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">format</span></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><a class="symbol" href="http://www.lispworks.com/reference/HyperSpec/Body/a_nil.htm"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">nil</span></a><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> </span><span class="string"><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">"'/tmp/test-unknown~A.png'"</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;"> iter</span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span></span><span class="Apple-style-span" style="font-family: Verdana, sans-serif;">)</span></span> </div><br />
<span id="fullpost"><span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;">Сделать нормальный cut с первой попытки не получилось, на то он и blogger, поэтому привожу только начало и конец вывода.</span></span><br />
<span id="fullpost"><span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"><br />
В начале ...</span></span><br />
<span id="fullpost"><span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"><br />
</span> <span class="Apple-style-span" style="font-size: xx-small;"><span class="Apple-style-span" style="font-size: x-small;"><span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"> ;; Final error: 0.9869251<br />
;;<br />
;; Training 0 node<br />
;; Training candidates: .....<br />
;; Best corr: 27.80652<br />
;; Connecting to outputs<br />
;; Final error: 0.97089535<br />
;; Epochs passed: 200<br />
;;<br />
;; Training 1 node<br />
;; Training candidates: .....<br />
;; Best corr: 24.884932<br />
;; Connecting to outputs<br />
;; Final error: 0.95397794<br />
;; Epochs passed: 300<br />
;;<br />
;; Training 2 node<br />
;; Training candidates: .....<br />
;; Best corr: 17.344604<br />
;; Connecting to outputs<br />
;; Final error: 0.94608283<br />
;; Epochs passed: 400<br />
<br />
И в конце ... </span> </span></span></span><br />
<span id="fullpost"><span class="Apple-style-span" style="font-size: xx-small;"><span class="Apple-style-span" style="font-size: x-small;"><span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"><br />
;; Training 17 node<br />
;; Training candidates: .....<br />
;; Best corr: 16.05864<br />
;; Connecting to outputs<br />
;; Final error: 0.062364805<br />
;; Epochs passed: 1900<br />
;;<br />
;; Training 18 node<br />
;; Training candidates: .....<br />
;; Best corr: 10.090686<br />
;; Connecting to outputs<br />
;; Final error: 0.052389637<br />
;; Epochs passed: 2000<br />
;;<br />
;; Training 19 node<br />
;; Training candidates: .....<br />
;; Best corr: 8.781674<br />
;; Connecting to outputs<br />
;; Final error: 0.043491814<br />
;; Epochs passed: 2100</span></span></span></span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;">После обучения каждого нового узла рисуются две картинки - результат работы сети на обучающем наборе (проверка качества запоминания) и на наборе случайных точек, которые он должен отнести к одной или другой спирали (проверка качества обобщения).</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;">По полученным изображениям можно проследить изменение запоминающей и обобщающей способностей в процессе обучения.</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;">Картинки лежат на <a href="https://github.com/allchemist/annil/tree/master/tests/two-spirals-data">гитхубе</a>. Приведу две соответствующие картинки после окончания обучения.</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"><br />
</span><br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://github.com/allchemist/annil/raw/master/tests/two-spirals-data/test-known19.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"><img border="0" height="480" src="https://github.com/allchemist/annil/raw/master/tests/two-spirals-data/test-known19.png" width="640" /></span></a></div><span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;">На последней картинке видны спиральные области красного и зеленого цветов, точки в которых сеть отнесла к одной или другой спирали, а также синие точки, которые сеть затруднилась отнести к конкретному классу.</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"><br />
</span><br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://github.com/allchemist/annil/raw/master/tests/two-spirals-data/test-unknown19.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"><img border="0" height="480" src="https://github.com/allchemist/annil/raw/master/tests/two-spirals-data/test-unknown19.png" width="640" /></span></a></div><span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;">Неплохо, однако. У Фальмана аналогичные картинки (в статье) более ломаные и меньше похожи на спираль.</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: Georgia, 'Times New Roman', serif;">Надо сказать, что после добавления 20 узлов среднекваратическая ошибка все еще довольно высока (0.04). Настройкой параметров алгоритма можно значительно ее уменьшить (мне удавалось получить меньше 0.001) и уменьшить время обучения.</span>allchemisthttp://www.blogger.com/profile/17364609418296639508noreply@blogger.com0tag:blogger.com,1999:blog-1354148132398418075.post-35593961365881349162010-11-17T22:03:00.000-08:002010-11-17T22:03:54.989-08:00Нейросетевое решение задачи классификацииНаконец-то удалось сделать нормальный классификатор для пакета нейросетевого анализа. (http://github.com/allchemist/annil).<br />
<div><br />
</div><div>Сеть каскадной корреляции, обучаемая с помощью алгоритма quickprop. Насколько я понимаю, эта связка является наиболее эффективным на настоящий момент алгоритмом такого назначения.</div><div><br />
</div><div>Затратил на реализацию этой связки достаточно много усилий, т.к. архитектура довольно редкая, литературы по ней мало.</div><div><br />
</div><div>Алгоритм quickprop решает задачу нелинейной регрессии с квадратичной сходимостью за время, линейно зависящее от количества весов сети, чем выгодно отличается от обратного распространения (линейная сходимость, линейное время) и от многомерной квазиньютоновской оптимизации (квадратичная сходимость, квадратичное время).</div><div><br />
</div><div>Алгоритм каскадной корреляции настраивает архитектуру сети самостоятельно, добавляя по одному узлу, который обучается извлекать следующий наиболее важный признак (процедура исчерпания, аналогичная ортогонализации Грама-Шмидта).</div><div><br />
</div><div>В результате, архитектура обладает отличной способностью к решению задач классификации, не обладая при этом многими неприятными особенностями обратного распространения.</div><div><br />
</div><div>Как quickprop, так и каскадная корреляция, разработаны <a href="http://www-2.cs.cmu.edu/~sef">Скотом Фальманом</a>, одним из разработчиков CMU CL, также известным как изобретатель смайликов. :)</div><div>Авторские статьи по этим алгоритмам лежат тут: <a href="http://www-2.cs.cmu.edu/~sef/sefPubs.htm">http://www-2.cs.cmu.edu/~sef/sefPubs.htm</a></div><div><br />
</div><div>Реализация тестировалась на нескольких задачах, которые считаются довольно сложными (two spirals, ocr, некоторые задачи проекта <a href="http://www.dice.ucl.ac.be/neural-nets/Research/Projects/ELENA/elena.htm">elena</a>). Сеть успешно справилась с задачами и показала даже большую эффективность, чем <a href="http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/neural/systems/cascor/lisp/cascor1.cl">авторская реализация</a>.</div><div><br />
</div><div>В ближайшее время подготовлю примеры использования с красявыми картинками :)</div>allchemisthttp://www.blogger.com/profile/17364609418296639508noreply@blogger.com5tag:blogger.com,1999:blog-1354148132398418075.post-73934776759323048582010-09-12T12:37:00.000-07:002010-09-27T01:32:44.988-07:00Математика в SBCL: бенчмаркПосле проведения некоторых оптимизаций кода <a href="http://github.com/allchemist/sb-math">sb-math</a> решил провести тест производительности функций умножения матрицы на матрицу и матрицы на вектор. Для сравнения взял <a href="http://common-lisp.net/project/gsll/">GSLL</a> и простым сишным кодом. Таким образом, сравнивался чистый вызов функций cblas_sgemv и cblas_sgemm из библиотеки GSL CBLAS и два интерфейса к ним.<br />
<br />
Код бенчмарков <a href="http://github.com/allchemist/sb-math/tree/master/tests">тут</a>:<br />
* bench.lisp - код для gsll и sb-math, а также вызова скомпилированного сишного кода, обработки результатов и отрисовки графиков.<br />
* gemm_bench.c, gemv_bench.c - сам сишный код<br />
* там же графики зависимостей (png)<br />
<br />
Итак, умножение матрицы на вектор. Для упрощения умножалась квадратная матрица NxN на вектор длиной N.<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgZut9yKxybbaCAr6uBvqRsp4-mvLiU2UsfbvEYFshoHpj8nUwg7hEhcl_cvOpP8oV-JpAaZUWW1dpAps2nxXcC-LPoZ_ZWIDzL-gXX_ltduUJ6qFg3w0_reFTYSWzz1MkxiUdDyghhbW4/s1600/gemv_bench_full.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgZut9yKxybbaCAr6uBvqRsp4-mvLiU2UsfbvEYFshoHpj8nUwg7hEhcl_cvOpP8oV-JpAaZUWW1dpAps2nxXcC-LPoZ_ZWIDzL-gXX_ltduUJ6qFg3w0_reFTYSWzz1MkxiUdDyghhbW4/s400/gemv_bench_full.png" width="400" /></a></div><div style="text-align: left;"><br />
</div><span class="Apple-style-span" style="color: black;"></span><br />
<span class="Apple-style-span" style="color: black;"></span><br />
<span class="Apple-style-span" style="color: black;"></span><br />
<span class="Apple-style-span" style="color: black;"></span><br />
<span class="Apple-style-span" style="color: black;"><div class="separator" style="clear: both; text-align: left;">На графике показана зависимость времени единичного вычисления от размености N. на больших размерностях GSLL дает существенное отставание. Причина этого неожиданного факта не совсем понятна. Более того, полгода назад на похожем тесте для больших размерностей GSLL шла рядом с сишным кодом, а вот для малых давала из рук вон плохие результаты. Вероятно, это связано с тем, что автор GSLL (Liam Healy) недавно <a href="http://www.mail-archive.com/gsll-devel@common-lisp.net/msg00093.html">перекроил</a> все матричное api для нее.</div><div class="separator" style="clear: both; text-align: left;"><br />
</div><div class="separator" style="clear: both; text-align: left;">Интересно посмотреть, что там вблизи нуля, где все линии сливаются в одну.</div><div class="separator" style="clear: both; text-align: left;"><br />
</div><br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgLJ70m0JvuRUjH0UMaz9c9aByWjBMLH05Y-rvSSHXjJ8yBCusdRN7qlsRmDBszGcZ2heEd77276z2gz78jTZa6cG5-xQb82kEnKLb9cwlA4pySzhAEuXeYcHo3G4a-PfJ6ssQK7XFYxO4/s1600/gemv_bench_10.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgLJ70m0JvuRUjH0UMaz9c9aByWjBMLH05Y-rvSSHXjJ8yBCusdRN7qlsRmDBszGcZ2heEd77276z2gz78jTZa6cG5-xQb82kEnKLb9cwlA4pySzhAEuXeYcHo3G4a-PfJ6ssQK7XFYxO4/s400/gemv_bench_10.png" width="400" /></a><br />
<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: left;">Тут не очень интересно, поэтому чуть увеличим размерность:</div><div class="separator" style="clear: both; text-align: left;"><br />
</div><br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgl4uXCrW9vjwmBKsAJJGP7SHysQF8OIfFgKRTHMEu8zMNtaeF05FB8LJYL-24MIAzcME68ZyZ1Y4z3-_dNloJFbG8OoxGcRiOS1iCnWqVO_Xp6seqTyM5z7sUM5vi-AzoaV3Pyamu9dtE/s1600/gemv_bench_50.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgl4uXCrW9vjwmBKsAJJGP7SHysQF8OIfFgKRTHMEu8zMNtaeF05FB8LJYL-24MIAzcME68ZyZ1Y4z3-_dNloJFbG8OoxGcRiOS1iCnWqVO_Xp6seqTyM5z7sUM5vi-AzoaV3Pyamu9dtE/s400/gemv_bench_50.png" width="400" /></a><br />
<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: left;"><br />
</div><div class="separator" style="clear: both; text-align: left;">Так все более-менее ясно.</div><div class="separator" style="clear: both; text-align: left;"><br />
</div><div class="separator" style="clear: both; text-align: left;">Теперь умножение матрицы на матрицу. Простоты ради все матрицы квадратные, с одинаковой размерностью.</div><div class="separator" style="clear: both; text-align: left;"><br />
</div><div class="separator" style="clear: both; text-align: left;"><br />
</div><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjsPGnjE8bKWlJ6InUF3hRDPgFBhN_44G_ttQ-mGfV5wIwhYR5lKicRBQJude3cUXTx42Tvcai9pVDX8zdyUcIncjlTk7Jd2f6PgjQXxZNIFP5998_f57KYUtW3WcUAagIe5dkLXsETOHc/s1600/gemm_bench_full.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjsPGnjE8bKWlJ6InUF3hRDPgFBhN_44G_ttQ-mGfV5wIwhYR5lKicRBQJude3cUXTx42Tvcai9pVDX8zdyUcIncjlTk7Jd2f6PgjQXxZNIFP5998_f57KYUtW3WcUAagIe5dkLXsETOHc/s400/gemm_bench_full.png" width="400" /></a><br />
<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: left;">Начиная с N=200 GSLL резко уходит уходит в отрыв, sb-math продолжает преследовать gcc :)</div><div class="separator" style="clear: both; text-align: left;"><br />
</div><div class="separator" style="clear: both; text-align: left;">Напоследок посмотрим поближе на результаты для малых размерностей:</div><div class="separator" style="clear: both; text-align: left;"><br />
</div><div class="separator" style="clear: both; text-align: left;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjAgmrZuMM8BqYkGQYH_3Cn2UcbV5dOXesRDa_IxFaTQ-FyN2H5tDZFlxs4cF5QMP_kUzQ2tq-aTGUUxhU2Kk4TwGDqEjtaJl7lOZs0uOU7YzLuFgKHNnrvyNXnvPgJ57DVMlvQAa24FcI/s1600/gemm_bench_10.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjAgmrZuMM8BqYkGQYH_3Cn2UcbV5dOXesRDa_IxFaTQ-FyN2H5tDZFlxs4cF5QMP_kUzQ2tq-aTGUUxhU2Kk4TwGDqEjtaJl7lOZs0uOU7YzLuFgKHNnrvyNXnvPgJ57DVMlvQAa24FcI/s400/gemm_bench_10.png" width="400" /></a></div><div class="separator" style="clear: both; text-align: left;"><br />
</div><div class="separator" style="clear: both; text-align: left;">Подводя итог, можно сказать, что sb-math смотрится достаточно неплохо даже на фоне gcc, хотя на матрицах малых размерностей относительное отставание от сишного кода велико. Но там еще есть возможности для оптимизации, и это вселяет надежду :)</div><div class="separator" style="clear: both; text-align: left;"><br />
</div><div class="separator" style="clear: both; text-align: left;">GSLL ведет себя достаточно странно, причем это поведение стабильно воспроизводится. Тем не менее, с новым foreign array api там все стало существенно лучше.</div><div class="separator" style="clear: both; text-align: left;"><br />
</div><div class="separator" style="clear: both; text-align: left;">Ну а сишный код - что с него взять? Накладных расходов на подготовку параметров там нет, но нет и гибкости и удобства, которые дает lisp.</div><div class="separator" style="clear: both; text-align: left;"><br />
</div><div class="separator" style="clear: both; text-align: left;">Ну и это самое. В отличие от GSLL sb-math не привязана к какой-то одной библиотеке CBLAS. Подключение ее к функциям из ATLAS дает существенный рост производительности по сравнению с GSLL. Тем не менее, я не стал включать в бенчмарк тесты на атласе, потому что целью было посмотреть оверхед на вызов функций. Да и не совсем честно это, что sb-math будет обгонять сишный код.</div><div class="separator" style="clear: both; text-align: left;"><br />
</div><div class="separator" style="clear: both; text-align: left;">Ну вы поняли :)</div><div class="separator" style="clear: both; text-align: left;"><br />
</div><div class="separator" style="clear: both; text-align: left;">UPD: В связи с глобальной переписью кода этот бенчмарк стал неактуальным. Оверхед на малых размерностях стал еще меньше.</div></span>allchemisthttp://www.blogger.com/profile/17364609418296639508noreply@blogger.com2tag:blogger.com,1999:blog-1354148132398418075.post-33738645424420894422010-09-11T05:52:00.000-07:002010-09-11T05:52:11.826-07:00Идеологически правильный оконный менеджерПрисоединился к недавнему флешмобу и заменил свой оконный менеджер для X11 на StumpWM. Настроил управление в духе fluxbox, конфиг на <a href="http://github.com/allchemist/dotfiles/blob/master/.stumpwmrc">github</a>, если кому вдруг интересно.<br />
StumpWM запускается в виде образа sbcl, поэтому для работы в sbcl нет смысла запускать новый процесс, если можно приконнектиться к старому.<br />
<br />
В моем случае окончание файла xinitrc выглядит так:<br />
<br />
<span class="Apple-style-span" style="color: blue;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">stumpwm &</span></span><br />
<span class="Apple-style-span" style="color: blue;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">exec emacs</span></span><br />
<br />
В конфиге stumpwm запускается swank, а в емаксе, в свою очередь, выполняется<br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-style-span" style="color: blue;">(slime-connect "127.0.0.1" 4005 'utf-8-unix)</span></span><br />
<br />
В итоге, сразу после загрузки иксов открывается емакс с уже запущенным slime. Удобно.<br />
<br />
<br />
<div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;">Но пост не об этом, на самом деле, а об одном забавном моменте.</div><div><br />
</div><div>StumpWM имеет тенденцию иногда падать, особенно, когда sbcl, в котором он работает, кто-то загрузил на 100%. И вот, значит, он упал, окошки не переключаются, хоткеи не работают и т.д., но X-сервер исправно пашет, и последнее активное окно по-прежнему доступно. Перезапускать иксы не хочется, особенно, когда открыто много окон.</div><br />
<div><br />
</div><div>Решение найдено!</div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-style-span" style="color: blue;">Alt-Ctrl-F2 </span></span># переключаемся в консоль</div><div><span class="Apple-style-span" style="color: blue;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">killall stumpwm </span></span># убиваем повисший процесс</div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-style-span" style="color: blue;">stumpwm </span></span># запускаем новый</div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><span class="Apple-style-span" style="color: blue;">Alt-Ctrl-F7 </span></span># возвращаемся в иксы</div><div><br />
</div><div>Все окна целы, несохраненные данные не потеряны. Не знаю, может быть, это вполне естественно, но меня порадовало :)</div><div><br />
</div>allchemisthttp://www.blogger.com/profile/17364609418296639508noreply@blogger.com1tag:blogger.com,1999:blog-1354148132398418075.post-43501046643270925312010-08-30T13:37:00.000-07:002010-09-03T13:37:42.405-07:00интерфейс к gnuplotРешил написать лисповый интерфейс к отличной рисовалке графиков gnuplot. Отчасти потому что существующие интерфейсы в печальном состоянии, отчасти из-за своей страсти к велосипедостроению.<br />
<br />
Выложил одну из версий на <a href="http://github.com/allchemist/gplt">github</a>. Приведу небольшой обзор возможностей.<br />
<br />
<pre>;; запускаем gnuplot
<span class="Apple-style-span" style="color: blue;">(gplt-start)</span>
;; далее передаем ему команды
<span class="Apple-style-span" style="color: blue;">#G(plot (/ (sin x)))</span>
;; смотрим, что получилось
<span class="Apple-style-span" style="color: blue;">(gplt-display)</span>
;; убиваем процесс
<span class="Apple-style-span" style="color: blue;">(gplt-stop)</span></pre><br />
После вызова gplt-display появилось обычное окошко gnuplot:<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgbUVmBVOBZV8aV8Q5HNU-DgVVxOMbM30F6oBIg1J6SJ1O9gSfJBy-LYIkTEpkqvRv0PK2BSaahGC6TjKYiV1D4nW915DZ2lwkJOPDizAdTv5bdAd3tHB2uj-abG-FJeqzv-hK1f2nLOO0/s1600/gplt.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgbUVmBVOBZV8aV8Q5HNU-DgVVxOMbM30F6oBIg1J6SJ1O9gSfJBy-LYIkTEpkqvRv0PK2BSaahGC6TjKYiV1D4nW915DZ2lwkJOPDizAdTv5bdAd3tHB2uj-abG-FJeqzv-hK1f2nLOO0/s400/gplt.png" width="400" /></a></div><br />
<div style="text-align: left;">#G() - это макрос чтения, соответствующий вызову (gplt-exec '(plot (/ (sin x)))). здесь могут быть любые команды, которые поймет сам gnuplot. s-выражение преобразуется в строку по следующим правилам.</div><div style="text-align: left;"><span class="Apple-style-span" style="font-family: inherit;"><br />
</span></div><div style="text-align: left;"></div><ul><li>Если выражение начинается с plot или splot, то следующий элемент выражения считается функцией либо файлом с данными. Функция задается обычным s-выражением и преобразуется в инфиксную форму, понятную gnuplot.</li>
<li>Интервалы задаются словом range. (range 0 1) преобразуется в [0:1]</li>
<li>Перечисления задаются словом enum. (enum 10 10) преобразуется в 10,10</li>
<li>Остальные ключевые слова передаются без изменений</li>
</ul><div>Таким образом, мы можем написать следующее:</div><div><br />
</div><pre><span class="Apple-style-span" style="color: blue;">(gplt-restart)
(map nil #'gplt-exec
'((unset key)
(set xrange (range 0 2))
(set yrange (range 2 5))
(set isosamples (enum 30 30))
(splot (sin (* x y)) with pm3d)))
(gplt-display)</span>
</pre><br />
<div>Это будет соответствовать следующим командам, набранным в самом интерпретаторе gnuplot:</div><br />
<pre><span class="Apple-style-span" style="color: blue;">unset key
set xrange [0:2]
set yrange [2:5]
set isosamples 30,30
splot sin(x*y) with pm3d
</span></pre><br />
<div>В результате получим такую картинку.<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjlGFkyB5cWxTqy0b4PKbZsK8suzDIQp-FM_w4GssiAgb3DmQeQDUAw1P_If5lEjdwypsafdvGJk2MWGiNMKcArms4Xj0sBOjRDTPqYUT4zrKs82ySIe3jUFLZPDZ8B3j-vcARasAjlhfw/s1600/gplt.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjlGFkyB5cWxTqy0b4PKbZsK8suzDIQp-FM_w4GssiAgb3DmQeQDUAw1P_If5lEjdwypsafdvGJk2MWGiNMKcArms4Xj0sBOjRDTPqYUT4zrKs82ySIe3jUFLZPDZ8B3j-vcARasAjlhfw/s400/gplt.png" width="400" /></a></div>Неплохо, но наверняка можно лучше. Поэтому буду рад услышать критику и предложения, и в особенности примеры команд gnuplot, которые нельзя передать с помощью текущего парсера.</div>allchemisthttp://www.blogger.com/profile/17364609418296639508noreply@blogger.com2tag:blogger.com,1999:blog-1354148132398418075.post-79955990918848443612010-08-15T11:44:00.000-07:002010-08-15T11:44:35.685-07:00Бредогенератор запущенТут буду помещать разные вещи, связанные с языком Common Lisp, которые могут быть интересны сообществу.<br />
<br />
Бредогенератор, от винта!allchemisthttp://www.blogger.com/profile/17364609418296639508noreply@blogger.com1