Комбинации значений
От: Blazkowicz Россия  
Дата: 06.12.12 12:15
Оценка:
Приветствую!

Посоветуйте, пожалуйста, подход для реализации сложных условий с большим количеством вариантов.
Нужно реализовать метод. Что-то типа такого.
public Color findDefault(boolean dark, boolean saturated, boolean positive);

В реальности там не только булеан с двумя значениями, но и энумы по 3-4 значения. И параметров больше чем 3.
Производительность не критичная. Важно простота понимания и модификации.

Тривиальный подход if..else

if(dark){
    if(saturated){
        if(positive){
            return Color.C1;
        }else{
            return Color.C2;
        }
   }else{
        if(positive){
            return Color.C3;
        }else{
            return Color.C2;
        }
   }
}else{
    if(saturated){
        if(positive){
            return Color.C4;
        }else{
            return Color.C4;
        }
   }else{
        if(positive){
            return Color.C4;
        }else{
            return Color.C1;
        }
   }
}

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

//Инициализация
   map.put(new Key(0, 0, 0), Color.1);
   map.put(new Key(0, 0, 1), Color.2);
   map.put(new Key(0, 1, 0), Color.1);
   map.put(new Key(0, 1, 1), Color.4);
   map.put(new Key(1, 0, 0), Color.3);
   map.put(new Key(1, 0, 1), Color.3);
   map.put(new Key(1, 1, 0), Color.1);
   map.put(new Key(1, 1, 1), Color.3);

//Сам метод:
   map.get(new Key(dark, saturated, positive));

Смущает то что самих вариантов результата не так много. И существую пересечения. Таблицу с десятками комбинаций всё ещё не так легко поддерживать.
Теперь думаю над таким варинтом.


//Инициализация
   Color.1 = new Color("dark/*/positive");
   Color.2 = new Color("dark/saturate/positive");
   Color.3 = new Color("!dark/!saturate/*");
//Сам метод:
   for (Color c : colors){
      if(c.match(dark, saturate, positive)){
          return c;
      } 
   }

Смущает полный перебор (хотя и не критично). Ещё как-то малой кровью надо реализовать синтаксис шаблонов. Может через regexp сделать?

Какое существует общепринятое решение и по каким ключевым словам гуглить?

Спасибо.
Re: Комбинации значений
От: Аноним  
Дата: 06.12.12 12:31
Оценка:
Можно попытаться ввести пространство условий, ввести меру близости, расположить на нём исходные цвета, а потом по вектору на входе определять ближайший цвет. Условия в этом случае могут быть и не булевыми типами.
Re[2]: Комбинации значений
От: Аноним  
Дата: 06.12.12 12:45
Оценка:
Если всё-таки хочется остаться с булевыми условиями, то можно завести битовые маски условий и смотреть на их пересечение.
Re[2]: Комбинации значений
От: Blazkowicz Россия  
Дата: 06.12.12 12:51
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Можно попытаться ввести пространство условий, ввести меру близости, расположить на нём исходные цвета, а потом по вектору на входе определять ближайший цвет. Условия в этом случае могут быть и не булевыми типами.

Пространство дискретное. И там нет очевидного правила расположения результата.
Re[3]: Комбинации значений
От: Blazkowicz Россия  
Дата: 06.12.12 12:53
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Если всё-таки хочется остаться с булевыми условиями, то можно завести битовые маски условий и смотреть на их пересечение.

Значения двоичные для илюстрации. Некоторые параметры могут принимать больше значений. Маска это и есть 3й вариант. Осталось придумать как реализовать.
Re: Комбинации значений
От: FoolS.Top Армения  
Дата: 07.12.12 09:24
Оценка: 12 (1)
Здравствуйте, Blazkowicz, Вы писали:

B>Приветствую!


B> Посоветуйте, пожалуйста, подход для реализации сложных условий с большим количеством вариантов.

B>Нужно реализовать метод. Что-то типа такого.
B>
B>public Color findDefault(boolean dark, boolean saturated, boolean positive);
B>

B>В реальности там не только булеан с двумя значениями, но и энумы по 3-4 значения. И параметров больше чем 3.
B>Производительность не критичная. Важно простота понимания и модификации.

B>Тривиальный подход if..else


B>
B>if(dark){
B>    if(saturated){
B>        if(positive){
B>            return Color.C1;
B>        }else{
B>            return Color.C2;
B>        }
B>   }else{
B>        if(positive){
B>            return Color.C3;
B>        }else{
B>            return Color.C2;
B>        }
B>   }
B>}else{
B>    if(saturated){
B>        if(positive){
B>            return Color.C4;
B>        }else{
B>            return Color.C4;
B>        }
B>   }else{
B>        if(positive){
B>            return Color.C4;
B>        }else{
B>            return Color.C1;
B>        }
B>   }
B>}
B>

B>Такой код плохо читается и ещё хуже модифицируется.
B>Переделал на таблицу (значения не соответствуют, просто иллюстрация)

B>
B>//Инициализация
B>   map.put(new Key(0, 0, 0), Color.1);
B>   map.put(new Key(0, 0, 1), Color.2);
B>   map.put(new Key(0, 1, 0), Color.1);
B>   map.put(new Key(0, 1, 1), Color.4);
B>   map.put(new Key(1, 0, 0), Color.3);
B>   map.put(new Key(1, 0, 1), Color.3);
B>   map.put(new Key(1, 1, 0), Color.1);
B>   map.put(new Key(1, 1, 1), Color.3);

B>//Сам метод:
B>   map.get(new Key(dark, saturated, positive));
B>

B>Смущает то что самих вариантов результата не так много. И существую пересечения. Таблицу с десятками комбинаций всё ещё не так легко поддерживать.
B>Теперь думаю над таким варинтом.


B>
B>//Инициализация
B>   Color.1 = new Color("dark/*/positive");
B>   Color.2 = new Color("dark/saturate/positive");
B>   Color.3 = new Color("!dark/!saturate/*");
B>//Сам метод:
B>   for (Color c : colors){
B>      if(c.match(dark, saturate, positive)){
B>          return c;
B>      } 
B>   }
B>

B>Смущает полный перебор (хотя и не критично). Ещё как-то малой кровью надо реализовать синтаксис шаблонов. Может через regexp сделать?

B>Какое существует общепринятое решение и по каким ключевым словам гуглить?


B>Спасибо.


Decision table?
Feierlich, misterioso
Re[2]: Комбинации значений
От: Blazkowicz Россия  
Дата: 07.12.12 09:32
Оценка:
Здравствуйте, FoolS.Top, Вы писали:

FT>Decision table?

За термин — спасибо. Но это сильно похоже на мой второй вариант. Не вижу как решается вопрос, когда некоторые условия сразу покрывают большой регион вариантов.
Re: Комбинации значений
От: . Великобритания  
Дата: 07.12.12 15:00
Оценка:
Здравствуйте, Blazkowicz, Вы писали:

Ещё вариант — объединение этого:

B>
B>//Инициализация
B>   map.put(new Key(0, 0, 0), Color.1);
...
B>

B>Смущает то что самих вариантов результата не так много. И существую пересечения. Таблицу с десятками комбинаций всё ещё не так легко поддерживать.


и этого:
B>
B>   for (Color c : colors){
B>      if(c.match(dark, saturate, positive)){
B>


Т.е. задаются в списке объекты с признаками и потом в цикле (один раз, в static-блоке) строится map для ключей, типа индекс. Вдобавок можно какие-то проверки добавить, чтобы например, дубликатов не было или полное покрытие вариантов.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re: Комбинации значений
От: LaptevVV Россия  
Дата: 07.12.12 15:48
Оценка:
Здравствуйте, Blazkowicz, Вы писали:

B> Посоветуйте, пожалуйста, подход для реализации сложных условий с большим количеством вариантов.

B>Какое существует общепринятое решение и по каким ключевым словам гуглить?
Таблицы решений — однозначно!
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[2]: Комбинации значений
От: Blazkowicz Россия  
Дата: 07.12.12 15:50
Оценка:
Здравствуйте, LaptevVV, Вы писали:

LVV>Таблицы решений — однозначно!

Есть пример с масками\wildcards?
Re[3]: Комбинации значений
От: LaptevVV Россия  
Дата: 07.12.12 15:56
Оценка: 6 (1)
Здравствуйте, Blazkowicz, Вы писали:

B>Здравствуйте, LaptevVV, Вы писали:


LVV>>Таблицы решений — однозначно!

B>Есть пример с масками\wildcards?
У меня нет, но наверное есть в базовой книжке:
Хамби Э. Программирование таблиц решений.
Болтается в сети дежавю-файл.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re: Комбинации значений
От: AndrewVK Россия http://blogs.rsdn.org/avk
Дата: 07.12.12 21:08
Оценка:
Здравствуйте, Blazkowicz, Вы писали:

B>Какое существует общепринятое решение и по каким ключевым словам гуглить?


Правильное решение называется pattern matching, но это язык нужен соответствующий. Если такого языка нет, то да, либо набор условий, либо хештаблица.
... << RSDN@Home 1.2.0 alpha 5 rev. 66 on Windows 8 6.2.9200.0>>
AVK Blog
Re: Комбинации значений
От: BulatZiganshin  
Дата: 08.12.12 22:37
Оценка:
Здравствуйте, Blazkowicz, Вы писали:

B> Посоветуйте, пожалуйста, подход для реализации сложных условий с большим количеством вариантов.


1. регэкспы
2. битовые маски
3. функция/макрос с удобным api
Люди, я люблю вас! Будьте бдительны!!!
Re: Комбинации значений
От: Буравчик Россия  
Дата: 09.12.12 14:36
Оценка:
Здравствуйте, Blazkowicz, Вы писали:

B> Color.1 = new Color("dark/*/positive");

B> Color.2 = new Color("dark/saturate/positive");
B> Color.3 = new Color("!dark/!saturate/*");
B>Смущает полный перебор (хотя и не критично). Ещё как-то малой кровью надо реализовать синтаксис шаблонов. Может через regexp сделать?

Такой вариант вроде не предлагали:

Rule.Set("dark").Set("positive").Return(Color.1)
Rule.Set("dark").Set("sature").Set("positive").Return(Color.2)
Rule.NotSet("dark").NotSet("sature").Return(Color.3)


Реализовать не сложно, читать — средне. Из плюсов — можно легко расширять, добавлять комбинаторы, в т.ч. использовать лямбды.

B>Какое существует общепринятое решение и по каким ключевым словам гуглить?


И добавлю очевидное: это типичный пример создания DSL. От того, насколько он будет сложен и насколько часто используется нужно решить будет он внешним (тогда придется писать парсер, но зато можно создать идеальнй язык) или внутренним (язык будет немного корявым, зато легко реализовать и легко интегрировать в систему).
... << RSDN@Home (RF) 1.2.0 alpha 5 rev. 17>>
Best regards, Буравчик
Re: Комбинации значений
От: McQwerty Россия  
Дата: 10.12.12 06:57
Оценка: +1
Здравствуйте, Blazkowicz, Вы писали:

B> Посоветуйте, пожалуйста, подход для реализации сложных условий с большим количеством вариантов.

B>Нужно реализовать метод. Что-то типа такого.
B>
B>public Color findDefault(boolean dark, boolean saturated, boolean positive);
B>

B>В реальности там не только булеан с двумя значениями, но и энумы по 3-4 значения. И параметров больше чем 3.
B>Производительность не критичная. Важно простота понимания и модификации.

B>Тривиальный подход if..else


B>
B>if(dark){
B>    if(saturated){
B>        if(positive){
B>            return Color.C1;
B>        }else{
B>            return Color.C2;
B>        }
B>   }else{
B>        if(positive){
B>            return Color.C3;
...
B>

B>Смущает полный перебор (хотя и не критично). Ещё как-то малой кровью надо реализовать синтаксис шаблонов. Может через regexp сделать?
B>Какое существует общепринятое решение и по каким ключевым словам гуглить?
Я в таких случаях поступаю примерно так:
// Пример: 5 условий по 2, 2, 3, 5 и 1 бит. Итого 13 бит. Всего 8192 вариантов
const unsigned value =
    ((cond1 & 0x000003)) |
    ((cond2 & 0x000003) << 2) |
    ((cond3 & 0x000007) << 4) |
    ((cond4 & 0x00001F) << 7) |
    ((cond5 & 0x000001) << 12)
;
switch (value)
{
case 0x0000: case 0x0001: case 0x0002: return 1;
case 0x0003: case 0x0004: return 2;
case 0x0005: case 0x0006: case 0x0007: return 3;
// и ещё 8183 кейсов
}

На 7К вариантов я такого не делал. Но на 2048 — было дело. Текст строил кодом.

Ассемблерный код для 8192 вариантов (с default-веткой):
; 812  :     switch (value)
; 813  :     {

    cmp    eax, 8192                ; 00002000H
    ja    $L88942
    jmp    DWORD PTR $L105644[eax*4]
$L88943:

; 814  : case 0: return 0;
; 815  : case 1: return 1;

    mov    eax, 1

; 9008 :     }
; 9009 : } // test

    ret    0
$L88944:

; 816  : case 2: return 2;

    mov    eax, 2

; 9008 :     }
; 9009 : } // test

    ret    0
$L88945:

; 817  : case 3: return 3;

    mov    eax, 3

; 9008 :     }
; 9009 : } // test

    ret    0
Re: Комбинации значений
От: Baudolino  
Дата: 10.12.12 07:28
Оценка: 12 (1)
DSL и паттерн "Спецификация". Пример (допилить на свой вкус):
public class Person {
}

public interface Specification<T> {
    boolean matches(T instance);
    
}

public class FaceColorSpecBuilder {
    Specification<Person> is(Color color) { ... }
}
public class NameSpecBuilder {
    Specification<Person> like(String pattern) { ... }
    Specification<Person> is(String name) { ... }
}

public class DrinksDSL {
    protected FaceColorSpecBuilder faceColor;
    protected NameSpecBuilder name;
    
    private List<Rule<Person, Drink>> rules;

    public RuleBuilder when(Specification<Person> criteria) { ... }

    protected class RuleBuilder {
         public RuleBuilder(Specification<Person> criteria) { this.criteria = criteria; }
         public void select(Drink drink) {
              rules.add(new Rule(criteria, drink));
         }
    }
    public List<Drink> suggestFor(Person person) {
         List<Drink> result = ...
         for (Rule rule : rules) {
             if (rule.matches(person)) result.add(rule.value());
         }
         return result;
    }
}

public class Drinks extends DrinkDSL {

   public final static Drink BEER  = new Drink("Beer");
   public final static Drink MILK = new Drink("Milk");

  {
     when(faceColor.is(RED)).and(name.like("%ov").or(name.like("%in"))).select(BEER);
     when(age.inRange(inclusive(0), exclusive(16))).select(MILK);
  }

}
...
@Inject
Drinks drinks;
...
Person petya = new Person("Petya Putin", 16, RED);
List<Drink> drinks = drinks.suggestFor(petya);
assertEquals(BEER, petya);
Re[2]: Комбинации значений
От: Baudolino  
Дата: 10.12.12 07:34
Оценка:
Важное дополнение:
1. Этот код очень хорошо используется повторно, т.к. спецификации нужны, например, в юнит тестах или как DTO для передачи критериев в трехзвенке (вместо DetachedCriteria в Hibernate, который таскать на клиент просто тупо).
2. Этот код хорошо генерализуется, т.к. инфраструктура для одного внутреннего DSL может пригодиться и для другого.
3. Внутренности класса-хранилища правил можно менять в целях оптимизации — если правил много, можно придумать какой-нибудь сложный алгоритм, который не будет решать задачу перебором правил.
4. Спецификацию можно подправить таким образом, чтобы она возвращала не boolean, а int — и суммировать очки, вычисляя наиболее точно подходящее правило.
Re: Комбинации значений
От: Blazkowicz Россия  
Дата: 11.12.12 07:47
Оценка: 2 (1)
Пока оставил вариант #2 — Decision Table. Удалось всё покрыть двумя таблицами.
Первая с бóльшим количеством параметров. Но для некоторых частных случаев. Если такой не найден, то вторая таблица с меньшим количеством параметров, но покрывает все возможные варианты.
Это проще чем городить паттерн матчинг для всех возможных комбинаций.
С паттерн матчинг ещё нужно было бы тест написать, чтобы быть увереным, что все возможные варианты покрыты. Да и нужной библиотеки для Java пока не нашел.
Всем спасибо за варианты, идеи и термины!
Re[2]: Комбинации значений
От: AndrewVK Россия http://blogs.rsdn.org/avk
Дата: 11.12.12 12:04
Оценка:
Здравствуйте, Blazkowicz, Вы писали:

B>С паттерн матчинг ещё нужно было бы тест написать, чтобы быть увереным, что все возможные варианты покрыты.


С нормальным ПМ это проверяет компилятор.

B> Да и нужной библиотеки для Java пока не нашел.


Тут не библиотеку надо менять, а язык. В Скале есть.
... << RSDN@Home 1.2.0 alpha 5 rev. 66 on Windows 8 6.2.9200.0>>
AVK Blog
Re: Комбинации значений
От: Blazkowicz Россия  
Дата: 19.12.12 10:47
Оценка:
Здравствуйте, Blazkowicz, Вы писали:

B>
B>//Инициализация
B>   map.put(new Key(0, 0, 0), Color.1);
B>   map.put(new Key(0, 0, 1), Color.2);
B>   map.put(new Key(0, 1, 0), Color.1);
B>   map.put(new Key(0, 1, 1), Color.4);
B>   map.put(new Key(1, 0, 0), Color.3);
B>   map.put(new Key(1, 0, 1), Color.3);
B>   map.put(new Key(1, 1, 0), Color.1);
B>   map.put(new Key(1, 1, 1), Color.3);

B>//Сам метод:
B>   map.get(new Key(dark, saturated, positive));
B>

B>Смущает то что самих вариантов результата не так много. И существую пересечения. Таблицу с десятками комбинаций всё ещё не так легко поддерживать.
B>Теперь думаю над таким варинтом.
Оказываеться, wildcard не так сложно реализовать. Заменить конструктор на factory, которая анализирует значения. Если значение — wildcard, то ключ клонируется в два (или более) покрывая все значения.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.