Java Streams: Find first for multiple filter predicates

29
June 18, 2022, at 01:30 AM

I have a Collection<Product> and a Collection<Predicate<Product>>. The Predicates are a simple combination of boolean flags. For example:

             | isNew | isSoldOut
--------------------------------
predicate 1: | false | false
predicate 2: | false | true
predicate 3: | true  | false
predicate 4: | true  | true

I want to find "one of every kind", though I'd like to find the first match for every Predicate within the products Collection.

Currently my code looks like this:

List<Product> products = getProducts();
List<Predicate<Product>> predicates = getPredicates();
List<Product> result = predicates.stream()
  .flatMap(predicate -> products.stream().filter(predicate).findFirst().stream())
  .collect(Collectors.toList());

But this of course will iterate of the products Collection multiple times, which is not desired, because in my case I have 100000 Products and 64 Predicates and it takes a long time.

In my special case the Predicates are mutually exclusive: If a Predicate returns true, then all other Predicates can be skipped for that particular Product. And because I use findFirst this Predicate then can be skipped for all other Products.

I was wondering if it is possible to iterate over the Product Collection instead, and check every Product only once against all the Predicates.

Answer 1

How about doing it the other way around? Streaming the products, and applying predicates on them.

List<Predicate<Product>> predicates = getPredicates();
List<Product> products = getProducts();
List<Product> filtered = products.stream().filter(product -> {
    Iterator<Predicate<Product>> iterator = predicates.iterator();
    while (iterator.hasNext()) {
        Predicate<Product> currentPredicate = iterator.next();
        if (currentPredicate.test(product)) {
             iterator.remove();
             return true;
        }
    }
    return false;
}).collect(Collectors.toList());

The downside is you have to be careful which collection you use for predicates, Iterator.remove is not always supported.

Edit: Looks like i wasn't reading carefully enough. I think getting one of each would be best with loop.

List<Product> products = getProducts();
List<Predicate<Product>> predicates = getPredicates();
List<Product> matchingProducts = new ArrayList<>(predicates.size());
for (Product product : products) {
    if (predicates.isEmpty()) {
        break;
    }
    for (int predicateIndex = 0; predicateIndex < predicates.size(); predicateIndex++) {
        Predicate<Product> predicate = predicates.get(predicateIndex);
        if (predicate.test(product)) {
            matchingProducts.add(product);
            predicates.remove(predicateIndex);
            break;
        }
    }
}

Actually managed to achieve it with a stream and takeWhile, you were correct, Benjamin.

List<Predicate<Product>> predicates = getPredicates();
List<Product> products = getProducts();
List<Product> matches = products.stream()
        .takeWhile(product -> !predicates.isEmpty())
        .filter(product -> {
            Iterator<Predicate<Product>> iterator = predicates.iterator();
            while (iterator.hasNext()) {
                if (iterator.next().test(product)) {
                    iterator.remove();
                    return true;
                }
            }
            return false;
        })
        .collect(Collectors.toList());

Just make sure takeWhile is before filter, otherwise last matching element gets skipped.

Answer 2

Your current solution will iterate over the collection many times, but as findFirst is a short-circuiting operator, it will stop as soon as it finds a match. Have you bench-marked it to make sure it is not good enough?

An alternative is to use a stateful filter (see the top answer to this post):

public static Predicate<Product> matchAndDiscard(final List<Predicate<Product>> predicates) {
  final Set<Predicate<Product>> remaining = new HashSet<>(predicates);
  return product -> {
    final var match = remaining.stream().filter(pred -> pred.test(product)).findFirst();
    match.ifPresent(remaining::remove);
    return match.isPresent();
  };
}

much like @Chaosfire's approach, but with the state contained within the filter function. If you believe that all predicates will be matched by at least one product, you can also save some time by limiting the stream to the number of predicates, like so:

final var predicates = getPredicates()
final var result = getProducts().stream()
    .filter(matchAndDiscard(predicates))
    .limit(predicates.size())
    .toList()

In your current solution, you would traverse the products "horisontally":

       --> products
pred1: ffffffffffffft
pred2: fffft
pred3: ffffffffffffffft
pred4: ft
etc.

The alternative will instead do a "vertical" traversal:

           products
pred1: | ffffffffffffft
pred2: | fffft
pred3: v ffff fffffffffft
pred4:   ft

so it is not obvious that one would be much faster than the other, it depends on the particular configuration.

Answer 3

If I understand correctly, you're looking for something like:

List<Product> results = products.stream()
                        .filter(prod -> predicates.stream()
                                        .anyMatch(pred -> pred.test(prod)))
                        .collect(Collectors.toList());
Rent Charter Buses Company
READ ALSO
what is the impact on Kafka topic partitions log when consumed using multiple Consumer groups?

what is the impact on Kafka topic partitions log when consumed using multiple Consumer groups?

My question is more related to performance rather than how they consume data in consumer groupsWe know that kafka create single PARTITION LOG on filesystem, which is accessed by all consumer group's consumer on that partition

48
how can I use the principle in memory cache?

how can I use the principle in memory cache?

1)I currently have to issue a kinit jumreg@JEMRUGCOM and enter a password to get a ticket

52
How to call manually Response.Listener in Android?

How to call manually Response.Listener in Android?

I have the following method that runs some web services commands in Android

41
JavaScript Error Element is null: while interacting ShadownDom element

JavaScript Error Element is null: while interacting ShadownDom element

I am writing code in Javascript to automate the website https://wwwfashionette

66