Маппинг объектов с помощью 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-ом.

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

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. Другие возможности разрешения конфликтов для пересекающихся правил.

Scala vs Java performance test

Скала подкупает своей лаконичностью и выразительностью, особенно по части алгоритмов над коллекциями. В стандартной библиотеке скалы можно встретить к тому же списку List - тучу всяких методов. Второй момент, который может шокировать новичка в скале - это разнообразие классов/интерфейсов/примесей (trait, надеюсь правильно перевел) для коллекций. Там и изменяемые коллекции, и не изменяемые, и так называемые билдеры, которые строят коллекцию наиболее эффективным образом. Но данная статья не об этом. Глядя на сие богатство закралось подозрение, что не может быть все так хорошо. Все эти функциональные примочки типа лямбд, неявных преобразователей, частичных функций, не могут обойтись бесплатно и возможно дадут проседание по производительности по сравнению с чистой джавой. Для проверки этой гипотезы накидал небольшой проект.

Подготовка

В качестве IDE для проекта взял бесплатные IDEA Community edition + Scala plugin.

Scala версии 2.10.0.

Java версии 1.7.0_09-b05.

Scala plugin позволяет создать проект для Scala, в котором, что мне понравилось, можно свободно мешать scala c java классами. Скорее всего это фича самой скалы, но мне, как новичку это в диковинку. Код скалы перед исполнением компилируется в java байткод, сохраняется в виде .class файлов  и выполняется на джаве, так что проседания по перфомансу, связанного с интерпретацией кода скалы в рантайме быть не должно.

Структура проекта

Была идея организовать проект таким образом, что-бы минимизировать усилия добавления нового кусочка кода, нуждающегося в проверке производительности. Базовый интерфейс для всех таких кусочков кода ITestCode (java).

package com.greentea.performance.test;

public interface ITestCode {
   String getName();
   void init();
   void run();
   Object getResult();
   void clean();
}

getName() выводит на экран имя теста. init() вызывается один раз для инициализации теста. run() может вызываться сколько угодно раз, и в конце необходимо вызвать clean() - задача которой освободить ресурсы, занимаемые тестовым кусочком кода. getResult() должен возвращать некий результат теста, например коллекцию которая изменялась. Это делается для того чтобы оптимизатор случайно не посчитал что раз результат нигде не используется, то код, его формирующий, можно вырезать. Движок тестирования вызывает этот метод 1 раз перед вызовом clean() для каждого теста, берет хешкод у объекта аккумулирует сумму всех хешкодов в одной переменной, и потом по окончании всех тестов эта сумма выводится на консоль.

Для итеративного запуска кусочка кода был написан класс IteratedTestCode (scala):

package com.greentea.performance.test


/**
 * User: goodg_000
 * Date: 17.02.13
 * Time: 13:13
 */
class IteratedTestCode(testCode : ITestCode, iterationsCount : Int) extends ITestCode {
  def warmUpIterationsCount = 20000
  def getName: String = testCode.getName + " [x" + iterationsCount + "]"

  def init() {
    testCode.init()
  }

  def warmUp() {
    var i = 0
    while (i < warmUpIterationsCount) {
      testCode.run()
      i += 1
    }
  }

  def run() {
    var i = 0
    while (i < iterationsCount) {
      testCode.run()
      i += 1
    }
  }

  def getResult: AnyRef = testCode.getResult

  def clean() {
    testCode.clean()
  }
}

Метод warmUp() используется движком тестирования что-бы прогнать код теста 20000 итераций перед замером времени. Это делается для того чтобы JIT догадался сделать все необходимые оптимизации.

Ну и собственно код запускающий тесты, и подсчитывающий время CodeBenchmark (scala):

package com.greentea.performance.test

import java.util

class CodeBenchmark {
  val tests = new util.ArrayList[ITestCode]()

  def addIteratedTest(testCode : ITestCode, iterationsCount : Int) {
    tests.add(new IteratedTestCode(testCode, iterationsCount))
  }

  def addTest(testCode : ITestCode) {
    tests.add(testCode)
  }

  def runTests() {
    var resultsHashSum = 0L
    val i = tests.iterator()
    while (i.hasNext) {
      val testCode = i.next()
      testCode.init()

      if (testCode.isInstanceOf[IteratedTestCode]) {
        testCode.asInstanceOf[IteratedTestCode].warmUp()
      }

      val start = System.currentTimeMillis()
      testCode.run()
      val end = System.currentTimeMillis()
      resultsHashSum += testCode.getResult.hashCode()
      printf("%70s: %s ms\n", testCode.getName, (end - start))

      testCode.clean()
      System.gc()
    }
    println(resultsHashSum)
  }
}

Тесты

С кодом тестов можно ознакомится на гитхабе.  Я постарался в основном проверить то, чем приходится часто пользоваться мне (не считая group).
Тесты располагаются в соответствующих пэкеджах, сгрупированные по тематике:
iteration - тестирование скорости итерирования по коллекции.
add - тестирование операции добавления в коллекции.
filter - фильтрация элементов коллекции по критерию.
group - группировка элементов коллекции в мапу по ключу, который генерируется из значения.
min - поиск минимального элемента в коллекции.
sum - суммирование элементов коллекции.

Для примера приведу куски кода для поиска минимума.

MinArrayListJava.java:

package com.greentea.performance.test.min;

import com.greentea.performance.test.ITestCode;

import java.util.ArrayList;
import java.util.List;

public class MinArrayListJava implements ITestCode {

   private List<String> list;
   private int elementsCount = 10;
   private String min;

   public MinArrayListJava(int elementsCount) {
      this.elementsCount = elementsCount;
   }

   public String getName() {
      return "Min of " + elementsCount + " elements of array list (Java)";
   }

   public void init() {
      list = new ArrayList<String>();
      for (int i = 0; i < elementsCount; ++i) {
         list.add("" + Math.pow(elementsCount - i, 2));
      }
   }

   public void run() {
      min = null;
      int lengthOfMin = Integer.MAX_VALUE;
      for (String val : list) {
         int len = val.length();
         if (min == null || len < lengthOfMin) {
            min = val;
            lengthOfMin = len;
         }
      }
   }

   public Object getResult() {
      return min;
   }

   public void clean() {
      list = null;
      min = null;
   }
}

MinByLinkedListScala.scala

package com.greentea.performance.test.min

import com.greentea.performance.test.ITestCode

class MinByLinkedListScala(elementsCount: Int) extends ITestCode {

  var list: List[String] = null
  var min: String = null

  def getName: String = "Min of " + elementsCount + " elements of linked list (list.minBy Scala)"

  def init() {
    list = (0 to elementsCount - 1).map(i => "" + Math.pow(elementsCount - i, 2)).toList
  }

  def run() {
    min = list.minBy(v => v.length)
  }

  def getResult: AnyRef = min

  def clean() {
    list = null
    min = null
  }
}

Как видим версия скалы намного короче! Но давайте посмотрим на производительность.

Результаты

(1)

                   Iteration array list of size 1000  (Java) [x200000]: 931 ms
                       Iteration array of size 1000  (Scala) [x200000]: 1040 ms
                  Iteration linked list of size 1000  (Java) [x200000]: 1118 ms
                  Iteration linked list of size 1000 (Scala) [x200000]: 1033 ms

(2)

                                                      Add to end of array list (Java) [x20000000]: 303 ms

                        Add to end of array buffer (Scala) [x20000000]: 234 ms

(3)

                         Add to end of list buffer (Scala) [x2000000]: 517 ms
                           Add to end of linked list (Java) [x2000000]: 155 ms

                         Append to end of linked list (Scala) [x10000]: 2008 ms

(4)

                        Add new Object() to hash set (Java) [x2000000]: 546 ms
                       Add new Object() to hash set (Scala) [x2000000]: 529 ms

(5)

   Select even numbers from array list of length 50 (Java) [x2000000]: 789 ms
   Select even numbers from linked list of length 50 (Java) [x2000000]: 902 ms
 Select even numbers from array of length 50 (Scala) [x2000000]: 1340 ms
         Select even numbers from list of length 50 (Scala) [x2000000]: 1072 ms      

(6)

                   Sum of 10 elements of array list (Java) [x20000000]: 408 ms
                       Sum of 10 elements of array (Scala) [x20000000]: 924 ms
                 Sum of 10 elements of linked list (Scala) [x20000000]: 804 ms
(7)
                   Sum of 10000 elements of array list (Java) [x20000]: 235 ms
                       Sum of 10000 elements of array (Scala) [x20000]: 2442 ms
                 Sum of 10000 elements of linked list (Scala) [x20000]: 1607 ms

(8)

                                                      Min of 100 elements of array list (Java) [x2000000]: 437 ms
      Min of 100 elements of linked list (list.minBy Scala) [x2000000]: 2645 ms
                 Min of 100 elements of linked list (Scala) [x2000000]: 967 ms
(9)
                   Min of 10000 elements of array list (Java) [x20000]: 811 ms
      Min of 10000 elements of linked list (list.minBy Scala) [x20000]: 2997 ms
                 Min of 10000 elements of linked list (Scala) [x20000]: 999 ms

(10)

   roups of 100 elements of array list by key func (Java) [x1000000]: 2975 ms
   Group of 100 elements of linked list by key func (Scala) [x1000000]: 3698 ms
(11)
    Groups of 10000 elements of array list by key func (Java) [x10000]: 2723 ms
   Group of 10000 elements of linked list by key func (Scala) [x10000]: 3378 ms

В скобочках [x20000000] указано количество запусков куска кода (метод run()). Сразу оговорюсь, что при повторном запуске результаты отличаются, но не очень сильно. Так что выводы будем делать глядя на текущие цифры.
Итак, о чем же можно сказать, глядя на эти результаты..

1) Тест на скорость итераций, с вызовом System.currentTimeMillis(); внутри каждой итерации (чтоб компилятор не вырезал код как ничего не делающий). Показывает что скорости итераций по linked list и array list примерно равны между собой в обоих языках. На это можно опереться последующих тестах в том смысле, что будет корректно сравнивать к примеру суммирование элементов array list с суммированием элементов в linked list - т.к. скорости итераций должны быть примерно равны.

2) скаловский mutable.ArrayBuffer работает даже быстрее чем ArrayList! Почему - сказать трудно, но внутри он работает по схожему принципу что и ArrayList.

3) со связными списками хуже - джавовский LinkedList работает быстрее чем ListBuffer. А вот mutable.LinkedList - ом для добавления в конец вообще нельзя пользоваться, т.к. он при этом, если не ошибаюсь, проходит от начала до конца списка.

4) Добавление в hash set - скорость одинакова.

5) Тест связанный с выбором четных чисел из коллекции быстрее отрабатывает в джаве, причем выбор из array list быстрее в 2 раза чем в скале выбор из array.

6) Суммирование 10 элементов массива быстрее в джаве в 2 раза .

7) Суммированием 10000 элементов намного быстрее в джаве! С чем это связано, не очень понятно. Посмотрим код метода sum в скале:

def sum[B >: A](implicit num: Numeric[B]): B = foldLeft(num.zero)(num.plus)

Копнем глубже:

def foldLeft[B](z: B)(op: (B, A) => B): B = {
    var result = z
    this.seq foreach (x => result = op(result, x))
    result
  }

Черт его знает, есть подозрение что примитивная операция op не инлайнится. Но это лишь мои догадки..

8) Поиск минимума к сожалению, не смотря на всю красоту записи в скале (см выше) в 4-5 раз медленнее аналога на джаве. Интересно и тут разобраться чего так происходит. Посмотрим код скалы метода minBy:

 def minBy[B](f: A => B)(implicit cmp: Ordering[B]): A = {
    if (isEmpty)
      throw new UnsupportedOperationException("empty.minBy")

    reduceLeft((x, y) => if (cmp.lteq(f(x), f(y))) x else y)
  }

Посмотрим  глубже на reduceLeft:

  def reduceLeft[B >: A](op: (B, A) => B): B = {
    if (isEmpty)
      throw new UnsupportedOperationException("empty.reduceLeft")

    var first = true
    var acc: B = 0.asInstanceOf[B]

    for (x <- self) {
      if (first) {
        acc = x
        first = false
      }
      else acc = op(acc, x)
    }
    acc
  }

Видим, что в reduceLeft передается "лямбда в лямбде", и на каждой итерации эта конструкция дергается. При этом вложенная лямбда f вызывается 2 раза f(x), f(y). Первый вызов на самом деле избыточен, т.к. f(x) уже вычислялось на предыдущей итерации. Java код такой проблемой не страдает так как вычисления ключа сравнения сохраняется в lengthOfMin. И помимо лишнего  вычисления в джава коде намного меньше вызовов функции, что тоже сказывается на производительности. Scala код эквивалентный Java  коду для поиска минимума работает в 3 раза медленнее. В чем же дело? Деактивация jad -ом показывает интересную картину:

    public void run()
    {
        Object _tmp = null;
        ObjectRef min = new ObjectRef(null);
        IntRef minLen = new IntRef(0x7fffffff);
        list().foreach(new Serializable(min, minLen) {

            public final void apply(String v)
            {
                int len = (new StringOps(Predef$.MODULE$.augmentString(v))).size();
                if(len < minLen$1.elem)
                {
                    min$1.elem = v;
                    minLen$1.elem = len;
                }
            }

            public final volatile Object apply(Object v1)
            {
                apply((String)v1);
                return BoxedUnit.UNIT;
            }

            public static final long serialVersionUID = 0L;
            private final ObjectRef min$1;
            private final IntRef minLen$1;

            public 
            {
                this.min$1 = min$1;
                this.minLen$1 = minLen$1;
                super();
            }
        }
);

Настораживает строка int len = (new StringOps(Predef$.MODULE$.augmentString(v))).size();
Попробуем заменить size на length...
Min of 100 elements of linked list (Scala) [x2000000]: 495 ms
Намного лучше!
В декомпилированной версии стало int len = v.length();
Вот так бывает, из-за казалось бы мелочи, производительность режется в 2 раза.

9) Аналогичный тест на поиск минимума для 10000 элементов в джаве оказался медленнее в 2 раза чем для 10 элементов (в пересчете на 1 итерацию). С чем это связано - не понятно.


10-11) Группировка элементов чуть быстрее в джаве.

Вывод?

Насколько мы могли видеть, базовые операции с коллекциями Scala 2.10.0 выполняет не хуже а иногда и лучше джавы. Но когда дело доходит до алгоритмов, то притягательная лаконичность скалы может обернуться жесткими проседаниями по производительности. Кроме того, есть вероятность напороться на код, который выглядит безобидно (метод size()  в String), но разворачивается в какой то невменяемый громоздкий код. 

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