Комбинации значений
От: 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, то ключ клонируется в два (или более) покрывая все значения.
Re[3]: Комбинации значений
От: koandrew Канада http://thingselectronic.blogspot.ca/
Дата: 19.12.12 19:56
Оценка:
Здравствуйте, Blazkowicz, Вы писали:

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


FT>>Decision table?

B>За термин — спасибо. Но это сильно похоже на мой второй вариант. Не вижу как решается вопрос, когда некоторые условия сразу покрывают большой регион вариантов.

Дык можно сделать эту таблицу с указателями — тогда эти некоторые условия будут содержать указатель на один и тот же экземпляр данных...
... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>
[КУ] оккупировала армия.
Re[4]: Комбинации значений
От: Blazkowicz Россия  
Дата: 20.12.12 07:13
Оценка:
Здравствуйте, koandrew, Вы писали:

FT>>>Decision table?

B>>За термин — спасибо. Но это сильно похоже на мой второй вариант. Не вижу как решается вопрос, когда некоторые условия сразу покрывают большой регион вариантов.
K>Дык можно сделать эту таблицу с указателями — тогда эти некоторые условия будут содержать указатель на один и тот же экземпляр данных...
Я имел ввиду что-то вроде wildcards. Т.е. у меня сейчас 6 параметров. Это только с бинарными будет 64 варианта. А у меня один параметр принимает 6 значений. Это уже 196 вариантов. Причем результатов всего штук 10, поэтому все 196 комбинаций описывать нет смысла. Нужно местами использовать wildcards.
Решилось это довольно простым методом, но на Java, правда кучу дополнительного кода пришлось написать


        RuleKey baseKey = new RuleKey(
                p1,
                p2,
                p3,
                enum1,
                enum2,
                p4);
        ArrayList<RuleKey> keys;
        keys = new ArrayList<uleKey>();
        keys.add(baseKey);

        for (Param param : Param.values()) {
            if(param.value(baseKey) == Wildcard){
                //Copy iterator for safe update of original list
                for (RuleKey key : new ArrayList<RuleKey>(keys)) {
                    keys.remove(key);
                    keys.addAll(param.applyWildcard(key));//Здесь параметр, перебирает все возможные варианты своего значения и создаёт копии baseKey, со всеми возможными вариантами вместо wildcard
                }
            }
        }
        for (RuleKey key : keys) {
            decisionMap.put(key, rule);
        }
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.