Фильтрация по таблицам истинности
Представьте себе класс Person с логическим флагом, указывающим, является ли человек работоспособным - по умолчанию установлено значение false.
public class Person{
boolean employable = false;
...
}
Теперь представьте, что у вас есть некоторые внешние логические методы, которые действуют на объекты Person. Например, рассмотрим статические логические методы в служебном классе.
public class PersonUtil{
public static boolean ofWorkingAge(Person p){
if(p.getAge() > 16) return true;
return false;
}
...
}
Булевы статические методы по сути аналогичны булевозначным функциям, то есть предикатам.
Мы можем построить таблицу истинности 2^(# предикатов)-by-# из предикатов. Например, учитывая три предиката: ofWorkingAge, ofGoodCharacter, isQualified, мы можем построить следующую таблицу истинности 8 на 3:
T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F
Теперь мы хотим нанимать людей с желаемыми качествами. Позвольте + указывать, что мы хотим считать кого-то работоспособным (т.е. установить флаг их трудоспособности в true) и - наоборот.
T T T | +
T T F | +
T F T | +
T F F | -
F T T | +
F T F | -
F F T | -
F F F | -
Теперь представьте себе коллекцию объектов Person. Для каждого человека мы корректируем его флаг трудоустройства в соответствии с тремя предикатами. Мы также обновляем счетчик (это заставляет нас использовать всю таблицу истинности, а не только положительные значения), так что, учитывая 1000 человек, мы хотим получить что-то вроде:
T T T | + 100
T T F | + 200
T F T | + 50
T F F | - 450
F T T | + 50
F T F | - 50
F F T | - 50
F F F | - 50
Предположительно, это можно рассматривать как фильтрацию по таблицам истинности. Установка флагов занятости и обновление счетчиков - довольно надуманный пример, но вы можете легко увидеть, как вместо этого мы можем захотеть устанавливать и обновлять гораздо более сложные вещи.
ВОПРОС
Есть ли способ элегантно сделать это? Я могу придумать два решения:
Неуклюжее решение
Имейте гигантскую руку, закодированную, если еще, если, еще цепь.
if(ofWorkingAge && ofGoodCharacter && isQualified){
c1++;
p.setEmployable(true)
}
else if(ofWorkingAge && ofGoodCharacter && !isQualified){
c2++;
p.setEmployable(true)
}
...
else if(!ofWorkingAge && !ofGoodCharacter && isQualified){
c7++;
}
else{
c8++;
}
Это просто плохо.
Чуть умнее решение
Передавать предикаты (возможно, в массиве) и набор предложений в метод. Пусть метод генерирует соответствующую таблицу истинности. Цикл по людям, установить их возможности трудоустройства и вернуть массив подсчетов.
Я вижу, как все можно сделать с помощью функциональных интерфейсов. Этот SO ответ потенциально актуален. Вы можете изменить PrintCommand на IsQualified и передать callCommand Person вместо строки. Но это также кажется немного неуклюжим, потому что тогда нам потребуется новый файл интерфейса для каждого предиката, который мы придумаем.
Есть ли другой способ Java 8-иш сделать это?
3 ответа
Давайте начнем со списка предикатов, которые у вас есть:
List<Predicate<Person>> predicates = Arrays.<Predicate<Person>> asList(
PersonUtil::ofWorkingAge, PersonUtil::ofGoodCharacter,
PersonUtil::isQualified);
Чтобы отследить, какой предикат является истинным или ложным, давайте прикрепим к ним имена, создавая NamedPredicate учебный класс:
public static class NamedPredicate<T> implements Predicate<T> {
final Predicate<T> predicate;
final String name;
public NamedPredicate(Predicate<T> predicate, String name) {
this.predicate = predicate;
this.name = name;
}
@Override
public String toString() {
return name;
}
@Override
public boolean test(T t) {
return predicate.test(t);
}
}
(можно прикрепить BitSet или что-то вроде этого для эффективности, но String имена тоже в порядке).
Теперь нам нужно сгенерировать таблицу истинности, которая представляет собой новый список предикатов с такими именами, как "T T F" и может применять данную комбинацию исходных предикатов, отрицание или нет. Это может быть легко сгенерировано с помощью некоторого волшебства функционального программирования:
Supplier<Stream<NamedPredicate<Person>>> truthTable
= predicates.stream() // start with plain predicates
.<Supplier<Stream<NamedPredicate<Person>>>>map(
// generate a supplier which creates a stream of
// true-predicate and false-predicate
p -> () -> Stream.of(
new NamedPredicate<>(p, "T"),
new NamedPredicate<>(p.negate(), "F")))
.reduce(
// reduce each pair of suppliers to the single supplier
// which produces a Cartesian product stream
(s1, s2) -> () -> s1.get().flatMap(np1 -> s2.get()
.map(np2 -> new NamedPredicate<>(np1.and(np2), np1+" "+np2))))
// no input predicates? Fine, produce empty stream then
.orElse(Stream::empty);
как truthTable это Supplier<Stream>Вы можете использовать его столько раз, сколько захотите. Также обратите внимание, что все NamedPredicate объекты генерируются на лету по требованию, мы их нигде не храним. Давайте попробуем использовать этого поставщика:
truthTable.get().forEach(System.out::println);
Выход:
T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F
Теперь вы можете классифицировать persons сбор по таблице истинности, например, следующим образом:
Map<String,List<Person>> map = truthTable.get().collect(
Collectors.toMap(np -> np.toString(), // Key is string like "T T F"
// Value is the list of persons for which given combination is true
np -> persons.stream().filter(np).collect(Collectors.toList()),
// Merge function: actually should never happen;
// you may throw assertion error here instead
(a, b) -> a,
// Use LinkedHashMap to preserve an order
LinkedHashMap::new));
Теперь вы можете легко получить счет:
map.forEach((k, v) -> System.out.println(k+" | "+v.size()));
Чтобы обновить employable В поле нам нужно знать, как указана нужная таблица истинности. Пусть это будет коллекция строк правды, как это:
Collection<String> desired = Arrays.asList("T T T", "T T F", "T F T", "F T T");
В этом случае вы можете использовать ранее сгенерированную карту:
desired.stream()
.flatMap(k -> map.get(k).stream())
.forEach(person -> person.setEmployable(true));
По сути, значение истинности является одним битом, и вы всегда можете использовать целочисленное значение из n битов для кодирования значения n истинности. Затем интерпретация целочисленного значения как числа позволяет связать значения с комбинацией значений истинности с помощью линейной таблицы.
Так что используя int закодированный индекс значения / таблицы истинности, общий класс таблицы истинности может выглядеть следующим образом:
public class TruthTable<O,V> {
final List<? extends Predicate<? super O>> predicates;
final ArrayList<V> values;
@SafeVarargs
public TruthTable(Predicate<? super O>... predicates) {
int size=predicates.length;
if(size==0 || size>31) throw new UnsupportedOperationException();
this.predicates=Arrays.stream(predicates)
.map(Objects::requireNonNull).collect(Collectors.toList());
values=new ArrayList<>(Collections.nCopies(1<<size, null));
}
public V get(O testable) {
return values.get(index(testable, predicates));
}
public V get(boolean... constant) {
if(constant.length!=predicates.size())
throw new IllegalArgumentException();
return values.get(index(constant));
}
public V set(V value, boolean... constant) {
if(constant.length!=predicates.size())
throw new IllegalArgumentException();
return values.set(index(constant), value);
}
public static <T> int index(T object, List<? extends Predicate<? super T>> p) {
int size=p.size();
if(size==0 || size>31) throw new UnsupportedOperationException();
return IntStream.range(0, size).map(i->p.get(i).test(object)? 1<<i: 0)
.reduce((a,b) -> a|b).getAsInt();
}
public static <T> int index(boolean... values) {
int size=values.length;
if(size==0 || size>31) throw new UnsupportedOperationException();
return IntStream.range(0, size).map(i->values[i]? 1<<i: 0)
.reduce((a,b) -> a|b).getAsInt();
}
}
Ключевым моментом является расчет int Индекс из истинных ценностей. Есть две версии. Во-первых, рассчитайте из явных логических значений для инициализации таблицы или запроса ее состояния, во-вторых, для фактического тестового объекта и списка применимых предикатов. Обратите внимание, что эти два метода включены в public static методы, чтобы их можно было использовать для альтернативных типов таблиц, например, для массива примитивных значений. Единственное, что нужно сделать, это создать линейное хранилище для 2ⁿ значения, когда у вас есть n предикатов, например new int[1<<n] а затем с помощью этих index методы определения записи для доступа для заданных значений или фактического кандидата на тестирование.
Экземпляры родового TruthTable можно использовать следующим образом:
TruthTable<Person,Integer> scoreTable=new TruthTable<>(
PersonUtil::ofWorkingAge, PersonUtil::ofGoodCharacter, PersonUtil::isQualified);
scoreTable.set(+100, true, true, true);
scoreTable.set(+200, true, true, false);
scoreTable.set(+50, true, false, true);
scoreTable.set(-450, true, false, false);
scoreTable.set(+50, false, true, true);
scoreTable.set(-50, false, true, false);
scoreTable.set(-50, false, false, true);
scoreTable.set(-50, false, false, false);
Person p = …
int score = scoreTable.get(p);
Я не уверен, что это то, что вы ищете, но вы можете использовать побитовые операторы для ваших переменных..
if(ofWorkingAge && ofGoodCharacter && isQualified){
c1++;
p.setEmployable(true)
}
может стать
int combined = 0b00000000;
combined |= ofWorkingAge ? 0b00000100 : 0b00000000;
combined |= ofGoodCharacter ? 0b00000010 : 0b00000000;
combined |= isQualified ? 0b00000001 : 0b00000000;
switch (combined){
case 0b00000111:
c1++;
p.setEmployable(true)
break;
case 0b00000110:
// etc
где последние биты представляют ofWorkingAge/ofGoodCharacter/isQualified.