Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What does the Java 8 Collector UNORDERED characteristic mean?

In official documentation you can read that:

UNORDERED Indicates that the collection operation does not commit to preserving the encounter order of input elements.

This is not too helpful without any examples.

My question is, what exactly does UNORDERED characteristic mean? Should I use it with reducing collectors like min or sum or is it only applicable to collection collectors?

In OpenJDK looks like reducing operations (min, sum, avg) have empty characteristics. I expected to find there at least CONCURRENT and UNORDERED.

like image 830
csharpfolk Avatar asked Oct 09 '16 09:10

csharpfolk


People also ask

What is the use of collector in Java 8?

A Collector is specified by four functions that work together to accumulate entries into a mutable result container, and optionally perform a final transform on the result. They are: creation of a new result container ( supplier() ) incorporating a new data element into a result container ( accumulator() )

How does Collector work in Java?

Collectors play an important role in Java 8 streams processing. They 'collect' the processed elements of the stream into a final representation. Invoking the collect() method on a Stream, with a Collector instance passed as a parameter ends that Stream's processing and returns back the final result.

What is Collectors toList in Java?

The toList() method of Collectors Class is a static (class) method. It returns a Collector Interface that gathers the input data onto a new list. This method never guarantees type, mutability, serializability, or thread-safety of the returned list but for more control toCollection(Supplier) method can be used.

What is characteristics method Java?

The characteristics() is a method of Java Interface Spliterator which is used to get a set of characteristics of this Spliterator and its elements.


2 Answers

In the absence of special pleading, stream operations must behave as if the elements are processed in the encounter order of the source. For some operations -- such as reduction with an associative operation -- one can obey this constraint and still get efficient parallel execution. For others, though, this constraint is very limiting. And, for some problems, this constraint isn't meaningful to the user. Consider the following stream pipeline:

people.stream()
      .collect(groupingBy(Person::getLastName, 
                          mapping(Person::getFirstName));

Is it important that the list of first names associated with "Smith" appear in the map in the order they appeared in the initial stream? For some problems, yes, for some no -- we don't want the stream library guessing for us. An unordered collector says that it's OK to insert the first names into the list in an order inconsistent with the order in which Smith-surnamed people appear in the input source. By relaxing this constraint, sometimes (not always), the stream library can give a more efficient execution.

For example, if you didn't care about this order preservation, you could execute it as:

people.parallelStream()
      .collect(groupingByConcurrent(Person::getLastName, 
                                    mapping(Person::getFirstName));

The concurrent collector is unordered, which permits the optimization of sharing an underlying ConcurrentMap, rather than having O(log n) map-merge steps. Relaxing the ordering constraint enables a real algorithmic advantage -- but we can't assume the constraint doesn't matter, we need for the user to tell us this. Using an UNORDERED collector is one way to tell the stream library that these optimizations are fair game.

like image 77
Brian Goetz Avatar answered Sep 22 '22 16:09

Brian Goetz


UNORDERED essentially means that the collector is both associative (required by the spec) and commutative (not required).

Associativity allows splitting the computation into subparts and then combining them into the full result, but requires the combining step to be strictly ordered. Examine this snippet from the docs:

 A a2 = supplier.get();
 accumulator.accept(a2, t1);
 A a3 = supplier.get();
 accumulator.accept(a3, t2);
 R r2 = finisher.apply(combiner.apply(a2, a3));  // result with splitting

In the last step, combiner.apply(a2, a3), the arguments must appear in exactly this order, which means that the entire computation pipeline must track the order and respect it in the end.

Another way of saying this is that the tree we get from recursive splitting must be ordered.

On the other hand, if the combining operation is commutative, we can combine any subpart with any other, in no particular order, and always obtain the same result. Clearly this leads to many optimization opportunities in both space and time dimensions.

It should be noted that there are UNORDERED collectors in the JDK which don't guarantee commutativity. The main category are the "higher-order" collectors which are composed with other downstream collectors, but they don't enforce the UNORDERED property on them.

like image 40
Marko Topolnik Avatar answered Sep 20 '22 16:09

Marko Topolnik