Java Stream minimum with known bound

Question

I have a Stream of Lists of which I want to get the entry with the least elements. I could of course do something like

Stream<List<T>> s = ...
s.min((e1, e2) -> e1.size() - e2.size());

But in a case like this, we know a lower bound for the minimum, since the size is non-negative. Meaning the moment a List of size 0 is found, we could actually stop, instead of running through the rest of the list too. Can this be achieved in a decent way with Java Streams?

I would imagine it looking something like this, giving a comparator and a function which tells us when the current minimum is a global one:

s.boundedMin(
    (e1, e2) -> e1.size() - e2.size(),
    e -> e.size() == 0
)

I can't think of a way to implement this.

Of course I could just use an Iterable and use a loop with break-statement to get this, I just wondered if streams could get me there too.

Edit: To make it a bit clearer. The Stream might or might not contain Lists of size 0. My issue is that min() will run through the whole stream, even if it already found a list of size 0 (which is already as small as it can ever get). So, what I'm looking for is an implementation of min which does not need to scan through the whole stream, by providing a lower bound for the minimum.

Edit2: An equivalent iterative solution without streams would be

List<List<T>> s = ...
List<T> min = null;
for (List<T> l : s) {
        if (min == null || min.size() > l.size())
            min = l;
        if (min.size() == 0) {
            break;
        }
}

[This](https://stackoverflow.com/questions/20746429/limit-a-stream-by-a-predicate) might help. — Andrew S, Sep 10 '19 at 14:19
Your question is not clear. Can you please elaborate it a bit more. Please provide your iterative solution so at least that gives us some impression on what you need to achive. — Ravindra Ranwala, Sep 10 '19 at 14:21
My first though was s.takeWhile(Predicate.not(Collection::isEmpty)).min(Comparator.comparing(Collection::size)); . Unfortunately it will not work, because 'takeWhile' method is not inclusive. — Viktor, Sep 10 '19 at 14:35
@RavindraRanwala I edited my question, I hope it's clearer now. — leyren, Sep 10 '19 at 14:44
the problem is that you want a short-circuiting _conditional_ exit; streams were not made for this. are you forced to use a `Stream>`? there are at least two issues here : 1) your Lists might not have a trivial `size` 2) the stream might be lazily computed - making your requirement entirely valid; but again _only_ if you are stuck with a `Stream>`, otherwise you already know what to do... — Eugene, Sep 10 '19 at 15:07
@Eugene No I am not forced to use Streams in this scenario. I was initially using streams, and then thought of ways to improve performance. Replacing this with the looped approach gave me a speedup of factor 3. But I was still curious whether or not this is possible to achieve using Streams. A lazily computed stream would be a valid usecase for such a requirement, but another one I could think of would be a scenario where you just want a close enough approximation of the minimum. — leyren, Sep 10 '19 at 15:21
a close enough approximation to the minimum would be a job for `ceilingEntry` or the like... — Eugene, Sep 10 '19 at 15:43
(Aside)If I am not mistaken, the iterative solution and the one with the stream are not the same. In one you are accessing the `List` with a minimum value of size and in another just the size. — Naman, Sep 10 '19 at 16:46
@Naman That was a mistake of my side when hastily adding the iterative solution, you're right of course. Edited it. — leyren, Sep 10 '19 at 17:07

Eugene · Accepted Answer · 2019-09-10T15:51:18.413

Just for the fun of it:

static <T> int size(Stream<List<T>> st) {

    class MinHolder implements Consumer<List<T>> {

        private int min = Integer.MAX_VALUE;

        public void accept(List<T> l) {
            if (min > l.size()) {
                min = l.size();
            }
        }
    }

    MinHolder holder = new MinHolder();
    Spliterator<List<T>> sp = st.spliterator();

    int elements = 0;
    for (; sp.tryAdvance(holder) && holder.min > 0; ++elements) {

    }

    System.out.printf("took %s elements to find the min%n", elements);
    return holder.min;
}

And a few test cases:

public static void main(String[] args) {
    Stream<List<Integer>> st = Stream.of(List.of());
    System.out.println(size(st));

    st = Stream.empty();
    System.out.println(size(st));

    st = Stream.of(List.of(), List.of(1), List.of(1, 2), List.of(1, 2, 3));
    System.out.println(size(st));
}

If you are not forced to use a Stream<List<T>> then don't; this conditional breaking is not something Streams were designed for and would be considered an abuse by many.

Java Stream minimum with known bound

1 Answers1