Interesting Tasks

Java, Scala, .NET, Lisp, Python, IDE's, Hibernate, MATLAB, Mathematica, Physics & Other

воскресенье, 17 мая 2015 г.

Liquibase для начальной инициализации базы данных

Допустим стоит задача инициализации структуры реляционной базы данных и заливки в нее неких первоначальных данных. Плюс хотим поддерживать несколько типов баз, скажем для тестов нужна база в памяти H2 а для продакшена что-то более серьезное (типа Oracle / PostgreSQL / MySQL etc). Решая данную задачу в лоб, можно под кажду базу написать отдельно скрипты инициализации ее структуры и команды загрузки данных. Решение простое, но не красивое, потому что в большинстве своем эти скрипты будут себя дублировать примерно полностью, за исключением небольших различий в синтаксисе для разных баз.

Эту задачу можно красиво решить с помощью тулзы Liquibase. И вот каким образом. Вкратце - она позволяет описывать структуру базы в неком своем формате xml. Потом этот xml транслируется в инструкции для выбранной базы, причем поддерживаются множество
реляционных баз (возможно все?). Причем изменения описываются в виде ченжсетов (changeset) и ликвибейз ведет учет уже примененных ченджсетов. Таким образом, можно
в процессе разработки дописывать новые ченжсеты (скажем по 1 на задачу) и ликвибейз сам будет применять только новые на ваших тестовых энвах, без нужды не пересоздавая базу.

Это все теория, а теперь перейдем к практике. Допустим у нас есть типичное Maven, Spring приложение. Несколько связанных таблиц и начальные данные для этих таблиц.

Добавляем зависимость на ликвибейз.

<dependency>
   <groupId>org.liquibase</groupId>
   <artifactId>liquibase-core</artifactId>
   <version>3.3.3</version>
</dependency>

Проверьте только и возьмете самую последнюю версию.

Добавляем бин ликвибейза в спринговый контекст:

<bean id="liquibase" class="liquibase.integration.spring.SpringLiquibase">
   <property name="dataSource" ref="dataSource" />
   <property name="changeLog" value="classpath:liquibase/db.changelog-master.xml" />
</bean>

В файле db.changelog-master.xml:
<?xml version="1.0" encoding="UTF-8"?>
<databaseChangeLog
        xmlns="http://www.liquibase.org/xml/ns/dbchangelog"
        xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
        xsi:schemaLocation="http://www.liquibase.org/xml/ns/dbchangelog
                      http://www.liquibase.org/xml/ns/dbchangelog/dbchangelog-3.1.xsd">

    <include file="liquibase/init.xml"/>
</databaseChangeLog>
В файле init.xml:

<?xml version="1.0" encoding="UTF-8"?>
<databaseChangeLog
        xmlns="http://www.liquibase.org/xml/ns/dbchangelog"
        xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
        xsi:schemaLocation="http://www.liquibase.org/xml/ns/dbchangelog
                      http://www.liquibase.org/xml/ns/dbchangelog/dbchangelog-3.1.xsd">

    <changeSet id="Create/Update tables" author="brunneng" runOnChange="true">

        <!-- Drop tables if exists -->
        <sql splitStatements="true">
            DROP TABLE IF EXISTS "Region" CASCADE;
            DROP TABLE IF EXISTS "City" CASCADE;
        </sql>

        <!-- Create tables -->
        <createTable tableName="Region">
            <column name="nID" type="int">
                <constraints primaryKey="true" nullable="false"/>
            </column>
            <column name="sName" type="varchar(50)">
                <constraints nullable="false"/>
            </column>
        </createTable>
        <addAutoIncrement columnName="nID" tableName="Region" columnDataType="int" incrementBy="1" startWith="1000"/>

        <createTable tableName="City">
            <column name="nID" type="int">
                <constraints primaryKey="true" nullable="false"/>
            </column>
            <column name="sName" type="varchar(50)">
                <constraints nullable="false"/>
            </column>
            <column name="nID_Region" type="int">
                <constraints nullable="false"
                             foreignKeyName="FK_Region_City"
                             referencedTableName="Region" referencedColumnNames="nID" deleteCascade="true"/>
            </column>
        </createTable>
        <addAutoIncrement columnName="nID" tableName="City" columnDataType="int" incrementBy="1" startWith="1000"/>
      
        <!-- Loading of Data -->
        <loadData encoding="UTF-8" file="data/Region.csv" tableName="Region" separator=";">
            <column name="nID" type="NUMERIC"/>
            <column name="sName" type="STRING"/>
        </loadData>
        <loadData encoding="UTF-8" file="data/City.csv" tableName="City" separator=";">
            <column name="nID" type="NUMERIC"/>
            <column name="sName" type="STRING"/>
            <column name="nID_Region" type="NUMERIC"/>
        </loadData>       
    </changeSet>


</databaseChangeLog>
В файле Region.csv:

nID;sName
1;Дніпропетровська
2;Львівська
3;Івано-Франківська
4;Миколаївська
5;Київська
6;Херсонська

И в файле City.csv:

nID;sName;nID_Region
1;Дніпропетровськ;1
2;Кривий Ріг;1
3;Львів;2
4;Івано-Франківськ;3
5;Калуш;3
6;Київ;5
7;Херсон;6

Все эти файлы пакуются вместе с приложением и должны быть доступны как ресурсы в classpath по своим относительным путям.

Как можно сразу заметить, ликвибейз позволяет загружать данные из csv файлов, что согласитесь, намного удобнее чем писать insert-ы вручную.
А теперь как это работает... Тут объявлен 1 ченжсет в котором делаются 3 вещи:

1. Удаляются все таблицы если они существуют
2. Создаются все таблицы
3. Заливаются данные

Теперь, если мы впервые запустим наше приложение, то ликвибейз сразу определит какие ченсеты не были применены (пока ни одного) и применит наш только что объявленный ченсет. При повторном запуске приложения на той же базе, если в определении ченсета ничего не менялось, то ликвибейз не будет ничего делать. Если же что либо изменилось, а именно:

- добавилась новая таблица
- изменилось определение существующей таблицы
- изменились данные в csv файлах

То для этого у нас была выставлен параметр: runOnChange="true", а значит ликвибейз перезапустит наш ченсет и вся база переинициализируется.

Единственная небольшая проблема тут - это удаление таблицы, если она существует. К сожалению у ликвибейза нету инстукции (более подходящее название для того что у них называется change) для этого. А то, что есть dropTable упадет с исключением при попытке удалить не существующую таблицу. Поэтому была использована инструкция sql в котором можно выполнить любой sql какой вам захочется. В нашем случае синтаксис удаления таблицы если она существует совпал для H2 и PostgreSQL - повезло. Но если у вас не совпадет, то у инструкции sql можно задать параметр dbms - для какой базы этот sql, и создать 2 блока sql для разных баз с разными значениями этого параметра.

воскресенье, 14 декабря 2014 г.

Warlight AI Challenge

Думаю самое время открыть немного подробностей про устройство бота GreenTea, написанного для Warligh AI Challenge. Но вначале немного об самой игре Warlight и конкурсе.

Об игре

Warlight - бесплатная стратегическая онлайн игра подобная Risk-у. Появилась если не ошибаюсь около 2010 года, постоянно развивается и уже обросла мощным сообществом игроков.


Это карта Small Earth, Вообще же карт существует огромное множество и энтузиасты постоянно создают новые. По сути карта - это связный граф. Он побит на подмножества (чаще всего не пересекающиеся) называемые бонусами. Например на карте выше можно видеть такие бонусы как Южная Америка (2), Африка (3), Европа (5), Азия (7), Северная Америка (5), Австралия (2). Цифры в скобках - величина бонуса, об этом дальше. Игра начинается с того что каждому из игроков предлагается выбрать начальные регионы для себя. В отличие от шахмат, где игроки ходят по очереди, тут ходы делаются одновременно. Обычно в игре людей на ход отводится по 5 минут, хотя настройки времени могут быть любые.  Итак, после выбора начальных регионов, каждый игрок подтверждает свой выбор, движек игры разруливает коллизии (тут не буду вдаваться в детали как) и начинается игра. Конечная цель - уничтожить противника. Каждый ход у игрока есть величина прироста, обычно начальный прирост 5. Прирост - это кол-во армий, которые можно поставить на любых своих регионах. И нужно поставить обязательно все - перенести на следующий ход часть не разрешается. С каждого своего региона можно сделать ход армиями на смежный регион. Все движения армиями логически можно разделить на такие категории:
1. Развитие. После захвата бонуса (владения всеми его регионами) прирост игрока увеличивается на величину бонуса. Поэтому захват бонусов это первостепенная цель в начале игры.
2. Защита. Если бонус захвачен, то его нужно защитить, иначе враг может пробить один из регионов, и тогда мы бонус потерям. Также имеет смысл защищать свой регион если он мешает противнику захватить бонус.
3. Атака. Атака может быть направлена как на уничтожение противника так и на подрыв его бонусов. И то и другое приближает к победе.

Пример игры на карте Turkey. Тут баталия в самом разгаре и пока неясно кто выиграет:


В течении хода можно сделать много движений армиями. Каждое движение будет совершаться в том порядке, в котором они были заказаны.
При заказе движения армиями мы выбираем регион с которого двигаться, целевой смежный регион и кол-во армий. При воспроизведении ходов успех движения армиями зависит от того сколько армий двигалось, и сколько армий было в целевом регионе. Например, если двигалось 5 армий а в целевом нейтральном регионе было только 2 армии, то шанс захватить целевой регион близок к 100%. Если же в атаке было 50 армий, а в защите стояло тоже 50 вражеских армий, то шанс захвата 0%, кроме того атакующие еще и потеряют больше, потому что защищающиеся всегда имеют небольшое преимущество в бою. Вообще же в игре много рандома, однако настройки каждой игры можно гибко конфигурировать, вплоть до полного исключения всех случайных факторов.

На этом можно пока остановиться.  Игра очень глубокая и всяких деталей и ньюансов в ней слишком много для этой заметки.

О конкурсе

Задача соревнования - написать бота который будет играть в Warligh. Призы - хорошие :)
€ 1024 - 1 место
€ 512 - 2 место
€ 256 - 3 место
...
€ 8 - 8 место

Взаимодействие с движком осуществляется через стандартный input / output. Поэтому язык написания бота может быть любой. Разработчики конкурса откликаются и добавляют новые - если их просят.

На ход бот может использовать не более 2 секунд.

Ограничения по времени проведения конкурса можно сказать нет. Первая часть соревнования длилась около полу года, если не больше. Кому то это не понравится, а по мне так в самый раз. Т.к. можно не спешить и постепенно улучшать бота доводя его до совершенства. Пару месяцев конкурс был в состоянии беты, потом еще несколько месяцев люди активно улучшали своих ботов борясь за вершину ладдера. Потом в какой то момент разработчики объявили дату, когда будет проведен финальный турнир на выявление победителя, и распределения мест для получения призов.

В первой части наибольшим недостатком было то что все действие происходило только на 1 карте Small Earth (см.выше). Поэтому большинство топовых стратегий были заточены именно под эту карту.

О написании AI для Warlight

Кто участвовал в подобных конкурсах раньше знает, что ключ к победе это как можно более точное моделирование мира, и перебор на несколько ходов вперед внутри модели, чтобы найти продолжение улучшающее позицию в игре.

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

Это значит, что участник должен самостоятельно выявить аспекты игры которые наиболее важны, и сконцентрироваться на них. Возможно если и делать перебор то в ограниченном наборе действительно важных мест, чтобы в конечном итоге не зависнуть и уложиться в 2 секунды отведенного времени.

Бот GreenTea

Этот бот изначально писался не привязываясь к какой-то конкретной карте. Именно этим я думаю обусловлено только 2 место в финале и на ладдере. 1 место использует стратегию, вручную оптимизированную под карту Small Earth. У меня не было задачи выиграть любой ценой. Целью я для себя ставил написание универсально крепкого бота, который играет более менее адекватно, и не делает глупых ошибок которые бы никогда не совершил хороший игрок в Warlight.

Далее приведу список компонент и модулей из которых состоит бот и несколько слов по реализации каждого из них не вдаваясь сильно в подробности:

GameSimulator

На вход получает текущее состояние карты, и может симулировать ходы на этой карте, как это будет происходить в реальности (устраняя элемент случайности). Используется повсеместно, чтобы делать неглубокие прогнозы на несколько ходов вперед. Так же все ходы можно отматывать назад, возвращаясь к предыдущему состоянию.

AttackAnalyzer

Реализует расчеты для атак. Отвечает на вопросы такие как:
  • какая вероятность захватить регион с заданным кол-вом атакующих армий и заданным кол-вом защитников.
  • какие будут средние потери при атаке с обеих сторон.
  • что если повторить атаку N раз, принимая во внимание известные приросты атакующего и защищающегося - то в конечном итоге регион будет захвачен? И какие будут потери с обеих сторон?

ExpandAI

Занимается всем связанным с захватом бонусов:
  • вычисление какие бонусы следует захватывать в первую очередь.
  • из всех возможных способов захвата бонуса выбирает наиболее быстрый и оптимальный путь
  • вычисляет оптимальный способ захвата нескольких бонусов одновременно.

RegionPairAnalysis

Для выбранной пары: мой регион / смежный регион противника вычисляет, для заданного N, очки полезности действия: поставить N армий на этот регион и атаковать или защищаться. Тут учитывается множество факторов, основной из которых это стратегическая ценность региона. Так, если регион ценен, то, к примеру, имеет смысл поставить больше армий на его защиту. Данные из этого класса очень полезны в ситуации когда имеется большой фронт соприкосновения с регионами противника, и необходимо правильно расставить акценты, между огромным количеством возможных вариантов постановки армий и дальнейших действий.

StrategicScoresAnalyzer

Вначале идентифицирует так называемые стеки армий, у себя и у противника. Стек - это достаточно большое кол-во армий находящихся в одном регионе. Потом для найденных самых больших стеков, строит симуляции возможных ходов, на N (до 4) ходов вперед. Для каждого пути движения стеков полностью симулирует игру и дает оценку конечной позиции. Таким образом находятся оптимальные движения стеками, как для защиты своих бонусов, так и для атаки бонусов противника. Вообще это наиболее сложная и заоптимизированная часть бота. Если у нас к примеру 3 стека, и для каждого найдено 100 вариантов путей на 4 хода, то это уже 3 млн. вариантов перебора, что, очевидно, слишком много. Надо или уменьшать глубину или отсекать несущественные варианты.

ForecastGameEngine

Используется внутри StrategicScoreAnalyzer для симуляции игры с заданными маршрутами движения стеков и последующей оценкой позиции.

BattleAI

Сердце бота. Координирует все остальные модули. Но и сам делает много чего:
  • определение предположительного прироста у противника. Т.к. очень важно как можно точнее оценивать его силы.
  • определение какими бонусами владеет противник.
  • определение бонусов, которые безопасно захватывать на данном ходу.
  • движение остатков армий с регионов, которые не контактируют с противником.
  • накопление стека для последующего движения к противнику.

Warligh AI Challenge 2!

Наконец, после долгого перерыва,  Warligh AI Challenge 2 уже в стадии Beta,  На этот раз главная фишка в том, что карты генерируются случайно!



Не будет больше дурацких захаркодженых стратегий. Теперь всем придется писать бота по честному.. Вот и посмотрим насколько GreenTea универсален и хорош. Если кто-то желает побороться за 1е место, и бросить вызов GreenTea, то пожалуйста. Но даже не смотря на многие месяцы перед следующим финалом - это будет для вас чрезвычайно сложно.

воскресенье, 20 октября 2013 г.

Маппинг объектов с помощью java-object-merger

Вот уже 3 месяца как, работаю над библиотекой по маппингу/мержингу объектов для java. C самого начала она задумывалась как альтернатива и замена dozer'у для моего основного проекта на работе, т.к. дозер не устраивал по некоторым параметрам (об этом ниже). Но для начала, если вы не в курсе что такое мапперы объектов и чем они полезны, небольшой ликбез.

Для чего нужны мапперы объектов?

Простой ответ: чтобы копировать данные автоматически из одного объекта в другой. Но тогда вы можете спросить: зачем нужно это копирование? Можно усомниться, что это нужно очень часто. Значит следует дать более развернутый ответ.
В мире энтерпрайз приложений принято бить внутреннюю структуру на слои: слой доступа к базе, бизнес и представление/веб сервиса. В слое доступа к базе как правило обитают объекты мапящиеся на таблицы в базе. Условимся называть их DTO (от Data transfer object). По хорошему, они только переносят данные из таблиц и не содержат бизнес логики. На слое представления/веб сервисов, находятся объекты, доставляющие данные клиенту (браузер / клиенты веб сервисов). Назовем их VO (от View object). VO могут требовать только часть тех данных, которые есть в DTO, или же агрегировать данные из нескольких DTO. Они могут дополнительно заниматься локализацией или преобразованием данных в удобный для представления вид. Так что передавать DTO сразу на представление не совсем правильно. Так же иногда в бизнес слое выделяют бизнес объекты BO (Business object). Они являются обертками над DTO и содержат бизнес логику работы с ними: сохранение, модифицирование, бизнес операции. На фоне этого возникает задача по переносу данных между объектами из разных слоев. Скажем, замапить часть данных из DTO на VO. Или из VO на BO и потом сохранить то что получилось.

Если решать задачу в лоб, то получается примерно такой “тупой” код:


...
employeeVO.setPositionName(employee.getPositionName());
employeeVO.setPerson(new PersonVO());
PersionVO personVO = employeeVO.getPerson();
PersonDTD person = employee.getPerson();
personVO.setFirstName(person.getFirstName());
personVO.setMiddleName(person.getMiddleName());
personVO.setLastName(person.getLastName());
...

Знакомо? :) Если да, то могу вас обрадовать. Для этой проблемы уже придумали решение.

Мапперы объектов

Придуманы конечно-же не мной. Реализаций на java много. Вы можете ознакомится, к примеру тут.
Вкратце, задача маппера — скопировать все свойства одного объекта в другой, а так же проделать все то же рекурсивно для всех чайлдовых объектов, по ходу делая необходимые преобразование типов, если это требуется.
Мапперы из списка выше — все разные, более или менее примитивные. Самый мощный пожалуй dozer, с ним я работал около 2 лет, и некоторые вещи в нем перестали устраивать. А вялый темп дальнейшей разработки дозера побудили написать свой “велосипед” (да, я знакомился с другими мапперами — для наших требовний они еще хуже).

Чем плох дозер

  • Бедная поддержка конфигурирования через аннотации (есть только @Mapping).
  • Невозможно мапить из нескольких полей в одно (к примеру собрать полное имя из имени, фамилии и отчества).
  • Проблемы с маппингом генерик свойств. Если в родительском абстрактном классе есть геттер возвращающий генерик тип T, где , а в чайлде T определен, то при маппинге чайлда будет учитываться только спецификация типа T. Будто бы он IEntity, а не тот, которым он определен в чайлдовом классе…
  • Классы свойств хранятся как строки во внутреннем кэше дозера, и чтобы получить класс, используется специальный класс лоадер. Проблемы с этим возникают в osgi окружении, когда dozer находится в одном бандле, а нужный класс бина в другом, не доступным из первого. Проблему мы побороли хоть и стандартным способом — подсунув нужный класс лоадер, но сама реализация: хранить класс в виде строки — выглядит странно. Возможно это для того чтобы не создавать perm gen space мемори ликов. Но все равно не очень понятно.
  • Если что-то вдруг не мапится, то разобраться в этом очень сложно. Если вы будете дебажить дозер, то поймете почему. Там какое-то… просто сумасшедшее нагромождение ООП паттернов — все запутанно и не явно. Впрочем, это только на мой вкус.

Какими качествами должен обладать маппер?

  1. Широкая поддержка конфигурации через аннотации.
  2. Полная поддержка генериков.
  3. Чистый, понятный код, который сможет подебажить любой не рискуя сломать мозг.
  4. По умолчанию, без каких либо дополнительных настроек, должно мапить так, как этого скорее всего будет ожидать разработчик.
  5. Должна быть возможность тонкой настройки (не хуже чем у дозера).

Реализация

Перед началом разработки был соблазн написать библиотеку на scala. Т.к. уже был положительный опыт ее использования.

Преимущества:

  • Код маппера будет не тривиальный, а отличные выразительные возможности скалы позволят писать меньше кода с большим колличеством смысла в каждой строчке. Т.е. именно мне это будет проще.

Недостатки:

  • Библиотека задумывалась для маппинга именно между java beans, для скала объектов она подходить не будет. Что получится весьма странно - библиотека на скале, а испльзуется только в джаве. Или придется добавлять поддержку скала объектов, а это дополнительная работа.
  • Если вдруг пользователю библиотеки нужно будет ее подебажить, то это будет сложновато..
  • Раньше у меня были какие то сложности с компиляцией скала кода мавеном в котором были java классы (а это понодобится при тестировании).

Недостатков видимо больше, и победила java. Причем поначалу начал писать java 7, но потом выяснилось что библиоетку не получится использовать в нашем проекте, в котором java 6. Пришось сделать downgrade кода на java 6.

Почему merger а не mapper?

java-object-merger отличает от других мапперов одна особенность. Основополагающая идея была в том, чтобы дать возможность создавать снимки объектов (Snapshot) на некоторый момент времени, и потом, сравнивая их, находить различия (Diff) подобно тому, как находим diff между двумя текстами. Причем должна быть возможность просмотра снапшотов и диффов в понятном для человека текстовом виде. Так, чтобы раз взглянув на дифф сразу стали ясны все отличия, а так же как будет изменен целевой объект после применения диффа. Таким образом добиваемся полной прозрачности процесса. Никакой магии и черных ящиков! Создание снапшотов открывает еще один интересный сценарий. Можно сделать снапшот объекта, потом как-то изменив его, сделать новый снапшот — проверить что изменилось, и, при желании, откатить изменения. Кстати дифф можно обойти специальным visitor-ом, и пометить только те изменения, которые хочется применить, а остальные проигнорировать.
Так что можно сказать, что merger — это нечто большее чем просто mapper.

Использование

Программа “Hello world” выглядит примерно так:


import net.sf.brunneng.jom.IMergingContext;
import net.sf.brunneng.jom.MergingContext;

public class Main {

   public static class A1 {
      private String field1;

      public String getField1() {
         return field1;
      }

      public void setField1(String field1) {
         this.field1 = field1;
      }
   }

   public static class A2 {
      private String field1;

      public A2(String field1) {
         this.field1 = field1;
      }

      public String getField1() {
         return field1;
      }
   }

   public static void main(String[] args) {
      IMergingContext context = new MergingContext();
      A2 a2 = new A2("Hello world!");
      A1 a1 = context.map(a2, A1.class);
      System.out.println(a1.getField1());
   }
}

Во-первых, видим, что для маппинга необходимо, чтобы у свойства был геттер на обоих объектах. Это нужно для сравнения значений. И сеттер у целевого объекта, чтобы записывать новое значение. Сами свойства должны именоваться одинаково.

Посмотрим же как реализован метод map. Это поможет понять многие вещи о библиотеке.


   @Override
   public <T> T map(Object source, Class<T> destinationClass) {
      Snapshot sourceSnapshot = createSnapshot(source);

      Snapshot destSnapshot = null;
      if (sourceSnapshot.getRoot().getType().equals(DataNodeType.BEAN)) {
         Object identifier = ((BeanDataNode)sourceSnapshot.getRoot()).getIdentifier();
         if (identifier != null) {
            destSnapshot = createSnapshot(destinationClass, identifier);
         }
      }
      if (destSnapshot == null) {
         destSnapshot = createSnapshot(destinationClass);
      }

      Diff diff = destSnapshot.findDiffFrom(sourceSnapshot);
      diff.apply();
      return (T)destSnapshot.getRoot().getObject();
   }

Если исходный снапшот это бин, и если у него есть identifier, тогда пытаемся найти целевой бин для класса destinationClass используя IBeanFinder-ы [тут createSnapshot(destinationClass, identifier);]. Мы такие не регистрировали, да и identifier-а нет, значит идем дальше. В противном случает бин создается используя подходящий IObjectCreator [тут createSnapshot(destinationClass)]. Мы таких тоже не регистрировали, однако в стандартной поставке имеется создатель объектов конструктором по умолчанию — он и используется. Далее у целевого снапшота берется дифф от снапшота источника и применяется к целевому объекту. Все.

Кстати, дифф, для этого простого случая, будет выглядеть так:

MODIFY { dest object : Main$A1@28a38b58 src object : Main$A2@76f8d6a6 ADD { dest property : String field1 = null src property : String field1 = "Hello world!" } }

Основные аннотации:

  • @Mapping — задает путь к полю для маппинга на другом конце ассоциации (например “employee.person.firstName”). Может быть указано на классе целевого объекта или объекта источника.
  • @Skip — поле не попадает в снапшот, не сравнивается и не мапится.
  • @Identifier — помечает поле которое считаеся идентификатором бина. Таким образом при сравнении коллекций мы будем знать какой объект с каким должен сравниваться. А именно будут сравниваться объекты с совпадающими идентификаторами. Так же, если в процессе применения диффа возникнет потребность создать бин, и при этом известен идентификатор, то будет попытка вначале найти этот бин при помощи зарегистрированных IBeanFinder-ов. Так, реализация IBeanFInder может искать бины к примеру в базе данных.
  • @MapFromMany — то же самое что и @Mapping только указывается на классе целевого объекта и позволяет указать массив свойств на объекте источнике которые будут мапится на поле в целевом объекте.
  • @Converter — позволяет задать на свойстве класс наследник PropertyConverter. — он выполнит преобразование между свойствами. Конвертер свойств обязателен при маппинге нескольких полей на одно, т.к. он как раз и должен будет собрать все значения из источника воедино и сформировать из них одно значение.
  • @OnPropertyChange, @OnBeanMappingStarted, @OnBeanMappingFinished — позволяют пометить методы прослушивающие соответствующие эвенты в жизненном цикле маппинга, которые происходят в данном бине.
  • И другие.

Конфигурация маппинга без аннотаций
Иногда, сущности на обоих слоях генерируются автоматически. Например модель генерируется по xml конфигам хибернета, а вьюшки - по wsdl. Как по мне то извращение, но все же. Для такого случая аннотацию просто негде поставить, и в версии 0.8.1 была добавлена возможность ручной конфигурации маппинга, например:

context.forBeansOfClass(PersonView.class).property("firstName").mappedTo("name.firstName");

Через код можно сделать все то же, что и через аннотации. Кроме того, возможно совмещать конфигурирование через аннотации и через код. Единственное органичение этого, чтобы конфигурации не пересекались. Типа: для некого поля задан маппинг в аннотации и через код. Но, если через анноатции задан маппинг, а через код - класс конвертер для этого поля - то это нормально. Кстати предусмотрены 2 возможности ручного задания конфиругации: через сеттеры (будет удобно в spring конфигурации) и через билдеры (пример выше, будет удобнее из кода).

Преобразования типов

В IMergingContext можно регистрировать пользовательские преобразователи типов, из одного типа в другой (интерфейс TypeConverter). Стандартный набор преобразователей включает преобразования:

  • примитивных типов в обертки, и наоборот
  • преобразования дат
  • объектов в строку
  • энумы в энумы, и строки в энумы по имени константы энума

Категории объектов


Маппер разделяет все объекты на такие категории как:
  1. Объекты значения: примитивные типы, объекты в пакете java.lang, даты, массивы объектов значений. Список классов считающихся значениями можно расширять через IMergingConext.
  2. Коллекции — массивы, все наследующиеся от java.util.Collection.
  3. Мапы — все наследующиеся от java.util.Map.
  4. Бины — все остальные.
Кстати, внутри одной категории значения отлично сравниваются. Например для коллекций можно без проблем замапить список на массив, или массив на сэт.

Производительность

Честно говоря, пока писал библиотеку — о производительности особо не задумывался. Да и изначально в целях высокой производительности не было. Однако, решил замерять время маппинга N раз на один тестовый объект. Исходный код теста. Объект довольно сложный, с полями значениями, дочерними бинами, коллекциями и мапами. Для сравнения взял dozer последней на текущий момент версии 5.4.0. Ожидал, что дозер не оставит никаких шансов. Но получилось совсем наоборот! dozer замапил 5000 тестовых объектов за 32 секунды, а java-object-merger 50000 объектов за 8 секунд. Разница какая-то дикая — в 40 раз… Если вы хотите лично убедится в этом, то смотрите юнит тест MappingPerformanceTest. Раскомментируйте тест для дозера и dependency от дозера в pom.xml.

Применение

java-object-merger был опробован на текущем проекте с моей основной работы (osgi, spring, hibernate, сотни мапящихся классов). Чтобы заменить им дозер полностью ушло менее 1 дня. По ходу находились некоторые явные косяки, но, после исправления, все основные сценарии работали нормально.

Ленивые снапшоты

Одна из явных проблем, найденных во время прикручивания маппера к реальному проекту было то, что если делать снапшот на DTO у которой есть ленивые списки других сущностей, а те другие ссылаются на третьи и т.д, то за создание одного снапшота можно, ненароком, выкачать пол базы. Поэтому было решено сделать все свойства в снапшоте ленивыми по умолчанию. Это означает, что они не будут вытаскиваться из объектов до момента сравнения с соответствующим свойством при взятии диффа. Или пока явно не вызовем на снапшоте метод loadLazyProperties(). А при вытаскивании свойства происходит автоматическое достраивание снапшота — опять же с ленивыми свойствами, которые ждут пока их догрузят.

Чего не может dozer.

В версии 0.8.1 была добавлена возможность мапить с коллекции на поля, находящиеся в другой коллекции. Например c "books" на "authorToBooks.book", где authorToBooks это коллекция промежуточных объектов связывающих авторов с книгами. При маппинге объекты связки будут создаваться автоматичеки и в них будут инжектится объекты книг.

Заключение

Проект, с исходниками и документацией находится тут
Так же, послядняя версия доступна из центрального репозитория maven-а:
<dependency> <groupId>net.sf.brunneng.jom</groupId> <artifactId>java-object-merger</artifactId> <version>0.8.5.1</version> </dependency>

Вся основная функциональность библиотеки покрыта юнит тестами, так что можете не сомневаться в том, что каких-то глупых тривиальных ошибок вы в ней не увидите. Практически все классы и методы задокументированы javadoc-ом.
Качайте, пробуйте, пишите свои отзывы :). Обещаю оперативно реагировать и прислушиваться к вашим пожеланиям.

четверг, 27 июня 2013 г.

Fuzzy scala inference engine - fusie

Как-то вспомнилось, что делал в универе лабу по предмету "Системы исскуственного интеллекта" на тему - экспертная система. Настолько это было интересно тогда, что, помню, много души вложил в эту работу. И захотелось.. вспомнить былое, переписать ту лабу с java на scala, воспользовавшись преимуществами последнего.

Результатом примерно двухмесячной работы стал движек вывода правил (forward chaining) с поддержкой нечеткой логики, под названием fusie (Fuzzy Scala inference engine)  (код).

Библиотека выложена в центральный репозиторий maven-а:


<dependency>
   <groupId>net.sf.brunneng.fusie</groupId>
   <artifactId>fusie</artifactId>
</dependency>

Возможные применения

Вообще говоря, это универсальный инструмент для случая, если необходимо автоматизировать принятие решений на основании правил, составленных экспертами в некой предметной области.

Один из примеров: сфера выдачи малых кредитов. На вход подаются данные о человеке: его кредитная история, какие-то финансовые метрики важные для принятия решения. И каждый банк создает свой набор правил, который, используя эти данные, решает — выдавать кредит такому человеку или не выдавать. И если выдавать, то на какое время и с какими процентами. Это позволит банку — уменьшить кол-во персонала занимающегося рутинной работой. Заемщику — экономия времени.

Следует иметь в виду, что это не логический язык программирования, а инструмент решающий задачу вывода, не более. И тем не менее, за ним чувствуется большой потенциал.

Место данного движка среди себе подобных

Существует множество хороших движков вывода и экспертных систем для jvm. Приведу свой маленький обзор некоторых из них (не претендующий, впрочем, на полноту и достоверность, только мои первые впечатления при беглом знакомстве).
Drools - Взрослый, хорошо конфигурируемый опен сорс движок, использующий forward chaining. Синтаксис определения правил можно посмотреть здесь.
d3web - Достаточно взрослая платформа для построения экспертных систем. Имеет собственное вики, для редактирования правил, вопросов, построения форм для принятия входных даннных, юнит тестирования. Несложный язык определения правил.
jColibry - как я понял, эта библиотека предназначенная для интерактивного поиска данных из большого числа вариантов.
InfoSapient - движок вывода, использующий backward chaining, с поддержкой нечеткой логики. Позвляет использовать человекоподобный язык описания правил. Но имеет, на мой взгляд, несколько существенных недостатков, описанных тут (page 19-20):
 "By current design, the rule base currently cannot access external data. This means during the consultation session, the ‘client’ must supply the goal to be solved, and all supporting information as well.*" "The rule syntax does not permit calculations, i.e. if ((a + b) is greater than m) then x; or executing external programs, scripts, or methods on external objects.* In other words, the client must execute any other external object, or script, based on the results from the consultation session."
Jena - позволяет представлять данные в стандартном RDF формате (семантическая сеть), и потом пытается извлекать интересующие данные используя специальный язык запросов SPARQL.
mandarax - компилятор правил. Недостаток в том, что он статичен - каждый набор правил должен был скомпилирован как джава код, и это нельзя сделать динамически.
И другие.

Как видим все движки очень разные: некоторые используют forward некоторые backward chaining, некоторые владеют нечеткой логикой некоторые нет. Одни имеют простой синтаксис определения правил — у других он сложный и т.д. В fusie я попытался совместить возможности четкого и нечеткого вывода, простоту определения правил и гибкую конфигурацию. Именно Scala (а не java) была изначально выбрана потому, что на ней можно писать в функциональном стиле, что позволит побороть предполагаемую сложность алгоритмов, которые предстояло написать. Тем не менее, движок собирается как maven артефакт, после чего его можно подрубить к любому maven проекту на java (с дополнительной зависимостью на scala-library), и все будет работать.

Общая схема понятий движка и их взаимоотношений между собой


Как видим правила работают с переменными (не обьектами) поэтому данный движкек не соответствует JSR-94.

Killer feature

Введем понятие "пересекающиеся правила". Это такие правила, которые дают заключения об одной и той же переменной. Например
 
when
   a > 300
then
   b = 5

when
   a < 400
then
   b = 10

  В данном случае если 'a' принимает значение между 300 и 400, то выполняется оба правила и система для дальнейшего вывода должна решить по какому пути идти, т.к 'b' не может быть одновременно 5 и 10. Вообще говоря, существует несколько способов как разрулить конфликтную ситуацию:
  1. Выбирать первое/последнее правило
  2. Задавать где-то приоритет правила
  3. Выбирать правило с более сложным условием (хотя в данном случае условия имеют одну сложность), исходя из предположения что более простое условие определяет общий случай, а более сложное — частные случаи.
Стратегии разрешения конфликта в Drools.
Текущая реализация (и такого я нигде не встречал) идет по другому пути.
4) Считать что оба правила равноценны и 0.5 вероятности что выполняется первое и 0.5 что второе (или в общем случае 1/N вероятности, если пересекающихся правил N). Далее вывод разделяется на части, и продолжается в отдельности для каждой из ветвей вплоть до нахождение искомой переменной. Впоследствии считается суммарная вероятность для каждого возможного значения искомой переменной по всем ветвям вывода. Если учесть, что правила могут причудливым образом зависить друг от друга по используемым переменным в предусловиях, что заключения могут содержать присваивания к разным переменным (так, что возможны группы пересекающихся правил, типа X пересекается с Y по переменной a, Y пересекается с Z по переменной b) то простое словесное описание идеи выливается в не очень простую реализацию. Главная цель которая была достигнута — корректное вычисление вероятностей значений принимаемых искомой переменной. Таким образом движок хорошо справляется с базой возможно противоречивых правил, которые пересекаются:
  1. Ненамеренно, если правила были составлены разными экспертами и у каждого свое мнение.
  2. Намеренно, если одна и та же переменная может быть вычислена разными способами, например:
    when
      graphicCardType == "Top"
    then
      graphicCard = "Nvidia super card"
    
    when
      graphicCardType == "Top"
    then
      graphicCard = "Radeon super card"
    
    
    
    В данном примере советник по выбору видеокарты может посоветовать как карту от Nvidia так и карту от Radeon с равной вероятностью.
Таким образом поддерживается элемент нечеткости в выводе.

Язык определения проблемы

Структура определения проблемы:
  1. Задаются пользовательские переменные — те, которые будут запрашиваться в процессе вывода.
  2. Правила вывода, состоящие из предусловий, заключений и, по желанию, вероятности выполнения данного правила (от 0 до 1, по умолчанию 1).
  3. Цель — имя переменной, которую нужно найти.
Проблему можно определять полностью программно, однако гораздо удобнее делать это используя специальный (не xml) синтаксис, который был разработан с целью быть лаконичным и сходу понятным для человека с опытом программирования.
 Пример 1: Финансовый советник
 
int amountSaved <- "How many savings you have?"
int earnings <- "What is you year income?"
bool steady <- "Your year income is stable?"
int dependents = min: 0 <- "How many dependents you have?"

fact
   minincome = 15000 + (4000 * dependents)

fact
   minsavings = 5000 * dependents

when
   savingsAccount == "inadequate"
then
   investment = "savings"

when
   (savingsAccount == "adequate") && (income == "adequate")
then
   investment = "stocks"

when
   savingsAccount == "adequate"
   income == "inadequate"
then
   investment = "combination"

when
   amountSaved > minsavings
then
   savingsAccount = "adequate"

when
   amountSaved <= minsavings
then
   savingsAccount = "inadequate"

when
   steady
   earnings > minincome
then
   income = "adequate"

when
   steady
   earnings <= minincome
then
   income = "inadequate"

when
   !steady
then
   income = "inadequate"

find investment

Вначале идет блок определения переменных:
int amountSaved <- "How many savings you have?"
int earnings <- "What is you year income?"
bool steady <- "Your year income is stable?"
int dependents = min: 0 <- "How many dependents you have?"
Это те переменные, которые не выводятся, но используются в правилах. Вначале следует тип, потом имя переменной, потом, опционально валидация на возможные значения ( min: 0 — означает что недопустимо значение меньше 0) и, тоже опционально, после <-  вопрос пользователю при запросе данной переменной. Поддерживаются типы: bool, int, double, enum (он же string). В предусловиях и заключениях могут использоваться выражения любой сложности (самое сложное в примере minincome = 15000 + (4000 * dependents)), но это далеко не предел) Семантика арифметических операций такая же как в java. Поддерживаются неявные преобразования int к double где это нужно. По умолчанию поддерживается вызов функций из java.lang.Math, но можно регистрировать и свои функции.
 Правило вида
fact
   minincome = 15000 + (4000 * dependents)
 определяет факт.

Записи

when
   (savingsAccount == "adequate") && (income == "adequate")
then
   investment = "stocks"
 и

when
   savingsAccount == "adequate"
   income == "adequate"
then
   investment = "stocks"

эквивалентны, т.к. между строками в предусловии неявно стоит операция && (and). Кстати, проблему можно определять частично, например только правила без пользовательских переменных. А определения переменных добавлять программно. Также можно подсунуть свой datasource для вытаскивания пользовательских переменных. Возможности парсера:

  • Показываются синтаксические ошибки, строка и символ где не удалось распарсить.
  • Проверка смысловых ошибок, типа определения нескольких пользовательских переменных с одним именем, или определение присваивание пользовательской переменной в заключении.
  • Контроль типов: пользователь видит где произошла ошибка приведения типа.
  • Поддержка вызова перегруженных функций.
Парсер был реализован как наследник от scala.util.parsing.JavaTokenParsers. Могу лишь сказать, что писать его было одно удовольствие, при том, что опыт написания парсеров до этого у меня более чем скромный. Мощь этого инструмента заключается в том, что можно задавать шаблоны для парсинга и тут же маппинг результатов на сущности.

Нечеткие сравнения

Был реализован синтанксис задания нечеткого сравнения через функцию принадлежности. Например:

fact
  b = 2.5

when
  b~=linear(/\, 1.0, 2.5, 3.0)
then
  a=1

find a

Данная программа вернет что a = 1 с вероятностью 1.0. Давайте разберемся что произошло.
linear - имя функции - это линейная функция. /\ - форма функции, а 1.0, 2.5, 3.0 - точки аппроксимации. Таким образом считаем что на отрезке от 1.0 до 2.5 вероятность возрастает линейно от 0 до 1, от 2.5 до 3.0 убывает линейно от 1 до 0. В нашем случае b = 2.5, сделовательно в этой точке функция принадлежности выдаст 1. Если бы b = 1.75, то вероятность была бы соответственно 0.5. Это лишь самый простой пример, с помощью этой нотации можно строить и более сложные функции, с большим числом точек, а также вместо линейной функции использовать функцию poly - которая для аппроксимации строит полином в форме Лагранжа.

Быстродействие

Для оптимизации вывода использовались идеи из алгоритма Рете. Так что при срабатывании правила будет проверяться только зависимые от него правила (т.е. те, которые нуждаются в переменных, выводящихся в данном правиле).
Было написано 2 теста:
  1. Задача из 8000 правил, для вывода искомой переменной требует срабатывания всех правил последовательно с последнего по первое. Время вывода (без разогрева jvm) около 600 мс.
  2. Задача из 26 пересекающихся правил, для вывода искомой переменной строится огромное дерево c 2^14 = 16384 листьями. Время вывода (без разогрева jvm) около 770 мс.
На мой взгляд быстродействие довольно приличное, и движек готов работать с настоящими, большими наборами правил.

Тестирование

Тестированию было уделено особое внимание. Юнит тесты пишутся для парсинга правил (от простых конструкций до определения проблемы целиком), для проверки корректности вывода (от простых задач до сложных, с запутанными пересекающимися правилами).

Примеры

В пакете com.greentea.sie.examples есть несколько классов с живыми примерами определения правил для некоторых разных предметных областей: FinancialAdviser, ProgrammingLanguageAdviser, LoanarAdviser.

Дальнейшие направления

  1. Работа движка не должна быть черным ящиком. Необходимо усовершенствовать описание процесса вывода понятное пользователю.
  2. Другие возможности разрешения конфликтов для пересекающихся правил.

Постоянные читатели