Как динамически выполнять фильтрацию в Java 8?

Ответ 1

Интересная проблема. Здесь происходит несколько вещей. Без сомнения, это может быть разрешено менее чем на половину страницы Haskell или Lisp, но это Java, поэтому здесь мы идем....

Одна проблема заключается в том, что у нас есть переменное количество фильтров, тогда как большинство примеров, которые были показаны, иллюстрируют фиксированные конвейеры.

Другая проблема заключается в том, что некоторые из фильтров OP являются чувствительными к контексту, например, "50% на определенный порядок". Это невозможно сделать с помощью простой конструкции filter(predicate) в потоке.

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

Предположим, что действующие значения являются экземплярами Widget, который является POJO, который имеет некоторые очевидные коэффициенты:

class Widget {
    String name() { ... }
    int length() { ... }
    double weight() { ... }

    // constructors, fields, toString(), etc.
}

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

List<Predicate<Widget>> allPredicates = Arrays.asList(
    w -> w.length() >= 10,
    w -> w.weight() > 40.0,
    w -> w.name().compareTo("c") > 0);

Учитывая этот список, мы можем переставить их (возможно, не полезно, поскольку они независимы от порядка) или выберите любое подмножество, которое мы хотим. Скажем, мы просто хотим применить их все. Как применить переменное число предикатов к потоку? Существует метод Predicate.and(), который принимает два предиката и объединяет их с помощью логического и возвращает один предикат. Таким образом, мы могли бы взять первый предикат и написать цикл, который объединяет его с последовательными предикатами, чтобы создать один предикат, который является составным и всех из них:

Predicate<Widget> compositePredicate = allPredicates.get(0);
for (int i = 1; i < allPredicates.size(); i++) {
    compositePredicate = compositePredicate.and(allPredicates.get(i));
}

Это работает, но он терпит неудачу, если список пуст, и поскольку мы сейчас выполняем функциональное программирование, мутация переменной в цикле является declassé. Но вот! Это сокращение! Мы можем уменьшить все предикаты над оператором и получить единый композитный предикат, например:

Predicate<Widget> compositePredicate =
    allPredicates.stream()
                 .reduce(w -> true, Predicate::and);

(Кредит: я узнал эту технику из @venkat_s. Если у вас когда-нибудь появится шанс, обратитесь к нему на конференцию..)

Обратите внимание на использование w -> true в качестве значения идентичности сокращения. (Это также можно использовать в качестве начального значения compositePredicate для цикла, который исправит случай списка нулевой длины.)

Теперь, когда у нас есть наш составной предикат, мы можем написать короткий конвейер, который просто применяет составной предикат к виджетам:

widgetList.stream()
          .filter(compositePredicate)
          .forEach(System.out::println);

Контекстно-зависимые фильтры

Теперь рассмотрим то, что я называю "чувствительным к контексту" фильтром, который представлен примером, например, "50% в определенном порядке", скажем, 50% самых популярных виджетов. "Контекстно-чувствительный" не самый лучший термин для этого, но это то, что у меня есть на данный момент, и оно несколько очерчено тем, что оно относительно количества элементов в потоке до этой точки.

Как мы будем реализовывать что-то подобное с помощью потоков? Если кто-то не придумает что-то действительно умное, я думаю, что мы должны сначала собрать элементы где-нибудь (скажем, в списке), прежде чем мы сможем испустить первый элемент на выходе. Это похоже на sorted() в конвейере, который не может определить, который является первым элементом для вывода, пока он не прочитает каждый отдельный элемент ввода и не отсортировал их.

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

List<Widget> temp =
    list.stream()
        .sorted(comparing(Widget::weight).reversed())
        .collect(toList());
temp.stream()
    .limit((long)(temp.size() * 0.5))
    .forEach(System.out::println);

Это не сложно, но это немного громоздко, поскольку мы должны собирать элементы в список и назначать его переменной, чтобы использовать размер списка в 50% вычислении.

Это ограничивает, однако, то, что это "статическое" представление такого типа фильтрации. Как бы мы связали это с потоком с переменным числом элементов (другими фильтрами или критериями), как это было с предикатами?

Важное замечание состоит в том, что этот код выполняет свою фактическую работу между потреблением потока и испусканием потока. У середины есть коллекционер, но если вы привяжете поток к его фронту и соедините его с конца, никто не станет мудрее. Фактически, стандартные операции конвейера потока, такие как map и filter, принимают поток в качестве входных данных и испускают поток в качестве вывода. Поэтому мы можем сами написать такую ​​функцию:

Stream<Widget> top50PercentByWeight(Stream<Widget> stream) {
    List<Widget> temp =
        stream.sorted(comparing(Widget::weight).reversed())
              .collect(toList());
    return temp.stream()
               .limit((long)(temp.size() * 0.5));
}

Аналогичным примером может быть поиск кратчайших трех виджетов:

Stream<Widget> shortestThree(Stream<Widget> stream) {
    return stream.sorted(comparing(Widget::length))
                 .limit(3);
}

Теперь мы можем написать что-то, что объединяет эти фильтры состояния с обычными потоковыми операциями:

shortestThree(
    top50PercentByWeight(
        widgetList.stream()
                  .filter(w -> w.length() >= 10)))
.forEach(System.out::println);

Это работает, но отчасти отвратительно, потому что он читает "наизнанку" и обратно. Источник потока widgetList, который передается и фильтруется через обычный предикат. Теперь, обращаясь назад, применяется верхний 50% -ный фильтр, затем применяется фильтр кратчайшего-трех, и, наконец, в конце применяется операция потока forEach. Это работает, но довольно запутанно читать. И это все еще статично. Нам очень хочется, чтобы мы включили эти новые фильтры в структуру данных, которые мы можем манипулировать, например, для запуска всех перестановок, как в исходном вопросе.

Ключевое понимание на этом этапе состоит в том, что эти новые виды фильтров - это действительно просто функции, и у нас есть функциональные типы интерфейса в Java, которые позволяют нам представлять функции как объекты, манипулировать ими, хранить их в структурах данных, составлять их, и т.д. Тип функционального интерфейса, который принимает аргумент некоторого типа и возвращает значение того же типа, - UnaryOperator. Аргумент и тип возврата в этом случае Stream<Widget>. Если бы мы взяли ссылки на методы, такие как this::shortestThree или this::top50PercentByWeight, типы результирующих объектов были бы

UnaryOperator<Stream<Widget>>

Если бы мы помещали их в список, тип этого списка был бы

List<UnaryOperator<Stream<Widget>>>

Тьфу! Три уровня вложенных дженериков для меня слишком много. (Но Алексей Шипилев однажды показал мне код, в котором использовались четыре уровня вложенных дженериков.) Решение для слишком большого количества дженериков - это определение нашего собственного типа. Позвольте назвать одну из наших новых вещей Критерием. Оказывается, мало что нужно сделать, если наш новый тип функционального интерфейса будет связан с UnaryOperator, поэтому наше определение может быть просто:

@FunctionalInterface
public interface Criterion {
    Stream<Widget> apply(Stream<Widget> s);
}

Теперь мы можем создать список таких критериев:

List<Criterion> criteria = Arrays.asList(
    this::shortestThree,
    this::lengthGreaterThan20
);

(Мы выясним, как использовать этот список ниже.) Это шаг вперед, так как теперь мы можем динамически манипулировать списком, но он все же несколько ограничивает. Во-первых, его нельзя комбинировать с обычными предикатами. Во-вторых, здесь есть много закодированных значений, таких как кратчайшие три: как насчет двух или четырех? Как насчет другого критерия, чем длина? Нам действительно нужна функция, которая создает для нас объекты Criterion. Это легко с лямбдами.

Это создает критерий, который выбирает верхние N виджетов, заданных компаратором:

Criterion topN(Comparator<Widget> cmp, long n) {
    return stream -> stream.sorted(cmp).limit(n);
}

Это создает критерий, который выбирает верхний процентный процент виджетов, заданный компаратором:

Criterion topPercent(Comparator<Widget> cmp, double pct) {
    return stream -> {
        List<Widget> temp =
            stream.sorted(cmp).collect(toList());
        return temp.stream()
                   .limit((long)(temp.size() * pct));
    };
}

И это создает критерий из обычного предиката:

Criterion fromPredicate(Predicate<Widget> pred) {
    return stream -> stream.filter(pred);
}

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

List<Criterion> criteria = Arrays.asList(
    fromPredicate(w -> w.length() > 10),                    // longer than 10
    topN(comparing(Widget::length), 4L),                    // longest 4
    topPercent(comparing(Widget::weight).reversed(), 0.50)  // heaviest 50%
);

Как только у нас есть список объектов Criterion, нам нужно выяснить способ применить их все. Еще раз, мы можем использовать нашего друга reduce, чтобы объединить все их в один объект Criterion:

Criterion allCriteria =
    criteria.stream()
            .reduce(c -> c, (c1, c2) -> (s -> c2.apply(c1.apply(s))));

Тождественная функция c -> c понятна, но второй arg немного сложнее. Учитывая поток s, мы сначала применяем Criterion c1, затем Criterion c2, и это обернуто в лямбда, которая принимает два объекта Criterion c1 и c2 и возвращает лямбду, которая применяет состав c1 и c2 к потоку и возвращает результат поток.

Теперь, когда мы составили все критерии, мы можем применить его к потоку виджетов:

allCriteria.apply(widgetList.stream())
           .forEach(System.out::println);

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

Гуру функционального программирования, вероятно, говорят: "Он просто изобрел...!" что, вероятно, верно. Я уверен, что это, вероятно, уже было изобретено где-то уже, но оно было новым для Java, потому что до лямбда просто не было возможности писать код Java, который использует эти методы.

Обновление 2014-04-07

Я очистил и разместил полный пример кода в основе.

Ответ 2

Мы могли бы добавить счетчик с картой, чтобы мы знали, сколько элементов у нас есть после фильтров. Я создал вспомогательный класс, который имеет метод, который подсчитывает и возвращает тот же переданный объект:

class DoNothingButCount<T> {
    AtomicInteger i;
    public DoNothingButCount() {
        i = new AtomicInteger(0);
    }
    public T pass(T p) {
        i.incrementAndGet();
        return p;
    }
}

public void runDemo() {
    List<Person>persons = create(100);
    DoNothingButCount<Person> counter = new DoNothingButCount<>();

    persons.stream().filter(u -> u.size > 12).filter(u -> u.weitght > 12).
            map((p) -> counter.pass(p)).
            sorted((p1, p2) -> p1.age - p2.age).
            collect(Collectors.toList()).stream().
            limit((int) (counter.i.intValue() * 0.5)).
            sorted((p1, p2) -> p2.length - p1.length).
            limit((int) (counter.i.intValue() * 0.5 * 0.2)).forEach((p) -> System.out.println(p));
}

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

Я мог бы сделать это несколько иначе, используя функцию для моего сопоставленного класса:

class DoNothingButCount<T > implements Function<T, T> {
    AtomicInteger i;
    public DoNothingButCount() {
        i = new AtomicInteger(0);
    }
    public T apply(T p) {
        i.incrementAndGet();
        return p;
    }
}

Единственное, что изменится в потоке:

            map((p) -> counter.pass(p)).

станет:

            map(counter).

Мой полный тестовый класс, включающий два примера:

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.Function;
import java.util.stream.Collectors;

public class Demo2 {
    Random r = new Random();
    class Person {
        public int size, weitght,length, age;
        public Person(int s, int w, int l, int a){
            this.size = s;
            this.weitght = w;
            this.length = l;
            this.age = a;
        }
        public String toString() {
            return "P: "+this.size+", "+this.weitght+", "+this.length+", "+this.age+".";
        }
    }

    public List<Person>create(int size) {
        List<Person>persons = new ArrayList<>();
        while(persons.size()<size) {
            persons.add(new Person(r.nextInt(10)+10, r.nextInt(10)+10, r.nextInt(10)+10,r.nextInt(20)+14));
        }
        return persons;
    }

    class DoNothingButCount<T> {
        AtomicInteger i;
        public DoNothingButCount() {
            i = new AtomicInteger(0);
        }
        public T pass(T p) {
            i.incrementAndGet();
            return p;
        }
    }

    class PDoNothingButCount<T > implements Function<T, T> {
        AtomicInteger i;
        public PDoNothingButCount() {
            i = new AtomicInteger(0);
        }
        public T apply(T p) {
            i.incrementAndGet();
            return p;
        }
    }

    public void runDemo() {
        List<Person>persons = create(100);
        PDoNothingButCount<Person> counter = new PDoNothingButCount<>();

        persons.stream().filter(u -> u.size > 12).filter(u -> u.weitght > 12).
                map(counter).
                sorted((p1, p2) -> p1.age - p2.age).
                collect(Collectors.toList()).stream().
                limit((int) (counter.i.intValue() * 0.5)).
                sorted((p1, p2) -> p2.length - p1.length).
                limit((int) (counter.i.intValue() * 0.5 * 0.2)).forEach((p) -> System.out.println(p));
    }

    public void runDemo2() {
        List<Person>persons = create(100);
        DoNothingButCount<Person> counter = new DoNothingButCount<>();

        persons.stream().filter(u -> u.size > 12).filter(u -> u.weitght > 12).
                map((p) -> counter.pass(p)).
                sorted((p1, p2) -> p1.age - p2.age).
                collect(Collectors.toList()).stream().
                limit((int) (counter.i.intValue() * 0.5)).
                sorted((p1, p2) -> p2.length - p1.length).
                limit((int) (counter.i.intValue() * 0.5 * 0.2)).forEach((p) -> System.out.println(p));
    }

    public static void main(String str[]) {
        Demo2 demo = new Demo2();
        System.out.println("Demo 2:");
        demo.runDemo2();
        System.out.println("Demo 1:");
        demo.runDemo();

    }
}