How does Stream.max() handle equality?

Question

Although I suspect the answer to be "It's not specified"...

If there are multiple "greatest/lowest" elements in a Stream which the Comparator passed to the max or min methods considers equal (returns 0), is it specified somewhere which element will be found?

I did a bit a bit more research on reduction in general (as `max()` is explicitly a special case of reduction), and I suspect the question boils down to whether the "accumulator" is associative even if the comparator does not impose a total ordering. — Hulk, Apr 19 '16 at 08:27
@Tunaki I need to use the order that happens to be the encounter-order of the elements in stream as a secondary ordering, and I tried to find out whether I need to explicitly specify that (i.e. generate some kind of index and take it into account in my comparator). — Hulk, Apr 19 '16 at 08:31
@Hulk: The comparator based accumulator is always associative, regardless of whether it returns the first or second object in case of equality, that’s *not* the question. — Holger, Apr 19 '16 at 10:27
Interestingly `BinaryOperator.maxBy` and `Collectors.maxBy` do not specify what they do in case of equality either. — the8472, Apr 19 '16 at 11:06
@Holger Ah yes, you are absolutely correct. The associativity does not depend on which element is returned as long as it is consistently always the right or always the left one in case of equality. — Hulk, Apr 19 '16 at 11:55
@the8472: Neither does `Collections.max`, though all of them have an undocumented left-(aka “first encountered”)preference. Note that this differs from `Collections.binarySearch` which explicitly specifies to return an arbitrary element’s index in case of multiple equal elements. — Holger, Apr 19 '16 at 17:17
At the root of this is what does `equals` mean. Depending on your definition, it would or wouldn't matter which one of two equal items is selected. The definition used in the documentation of `Stream.distinct()` would say that it doesn't matter which is taken. — Hank D, Apr 19 '16 at 17:59
@HankD No, this is not about equality of elements in the sense of `equals` or `distinct` - the methods discussed here allow specifying a Comparator that defines an arbitrary ordering among elements. The elements do not necessarily have any notion of a natural ordering that is consitent with equals. For what it's worth, the elements in my stream do not even override `equals`, so equality is just reference equality. — Hulk, Apr 20 '16 at 05:11

score 9 · Accepted Answer · edited May 23 '17 at 12:16

9

It’s indeed hard to pull a definite statement from the documentation only. If we try to draw a conclusion from the general description of the “Reduction” process and similar hints of the documentation, it will always feel like we’re possibly doing too much interpretation.

However, there’s an explicit statement regarding this matter from Brian Goetz who’s quite an authority regarding the Stream API:

If the stream is ordered (such as the streams you get from an array or List), it returns the first element that is maximal in the event of multiple maximal elements; only if the stream is unordered is it allowed to pick an arbitrary element.

It’s a pity that such an explicit statement isn’t made right at the documentation of Stream.max, but at least it’s in line with our experience and knowledge of the implementation (those of us who looked at the source code). And not to forget, practical considerations, as it’s easy to say “pick any rather than first” via unordered().max(comparator) with the current state of affairs than saying “pick first rather than any” if max was allowed to pick an arbitrary element in the first place.

edited May 23 '17 at 12:16

Community

1
1

answered Apr 19 '16 at 10:44

Holger

285,553
42
434
765

2

I think the explicit statement is not worth too much because there are 3rd-party `Stream` implementations not controlled by the JDK developers. And if the javadocs do not constrain those implementations then they are free to handle this case however they want. – the8472 Apr 19 '16 at 11:16
2

@the8472: really? Name at least one… – Holger Apr 19 '16 at 11:20
2

@the8472: note that this statement isn’t standing in empty space. As already said in the answer, there *are* several aspects of the documentation allowing to draw such a conclusion; that explicit statement is just a good prove that we are not over-interpreting here. – Holger Apr 19 '16 at 11:31
3

Nothing defines whether the max() operation in each reduction step uses `>= 0` or `> 0` on the comparator result. So the specifications how ordered streams should behave and how reduction is performed gains us nothing as long as that basic property is not spcified. – the8472 Apr 19 '16 at 11:53

score 5 · Answer 2 · answered Apr 19 '16 at 08:39

After reading the source code, I think should be the first greatest element will be found according to the collection order. We can check out the source code of the Stream.max(Comparator<? super T> comparator), the implementation class is ReferencePipeline.max

    @Override
    public final Optional<P_OUT> max(Comparator<? super P_OUT> comparator) {
        return reduce(BinaryOperator.maxBy(comparator));
    }

that you can see, when you call the Stream.max, you mean call the Stream.reduce(BinaryOperator<P_OUT> accumulator)

And look at the source code of BinaryOperator.maxBy(comparator)

    public static <T> BinaryOperator<T> maxBy(Comparator<? super T> comparator) {
        Objects.requireNonNull(comparator);
        return (a, b) -> comparator.compare(a, b) >= 0 ? a : b;
    }

It's clear, when a equals b, it returns a. So when there are multiple "greatest/lowest" elements in a Stream, the "greatest/lowest" element should be the first "greatest/lowest" element according to the collection order

There is a example at blew, just for your reference.

        List<Student> list = Arrays.asList(new Student("s1", 1), new Student("s2", 5), new Student("s3", 3), new Student("s4", 5));
        // it should be student of 's2'
        list.stream().max(Comparator.comparing(Student::getScore));
        // it should be student of 's4'
        list.stream().reduce((a, b) -> Comparator.comparing(Student::getScore).compare(a, b) > 0 ? a : b);

This really depends on the orderding of the Stream. More info here http://stackoverflow.com/a/29218074/1743880 — Tunaki, Apr 19 '16 at 08:45
The source is informative, but not normative. You cannot rely on things unless they're part of the documentation. — the8472, Apr 19 '16 at 09:01

How does Stream.max() handle equality?

2 Answers2

Linked