This is a classic implementation of an immutable linked list:
public abstract class List<A> implements Iterable<A> {
private static final List NIL = new Nil();
public abstract A head();
public abstract List<A> tail();
public List<A> cons(A a) { return new Cons<>(a, this); }
public static <A> List<A> nil() { return NIL; }
@Override
public Iterator<A> iterator() {
return new Iterator<A>() {
private List<A> list = List.this;
@Override
public boolean hasNext() {
return list != NIL;
}
@Override
public A next() {
A n = list.head();
list = list.tail();
return n;
}
};
}
public Stream<A> stream() {
return StreamSupport.stream(spliterator(), false);
}
public Stream<A> parallelStream() {
return StreamSupport.stream(spliterator(), true);
}
}
class Nil extends List {
@Override public Object head() { throw new NoSuchElementException(); }
@Override public List tail() { throw new NoSuchElementException(); }
}
class Cons<A> extends List<A> {
private final A head;
private final List<A> tail;
Cons(A head, List<A> tail) {
this.head = head;
this.tail = tail;
}
@Override public A head() { return head; }
@Override public List<A> tail() { return tail; }
}
The default implementation of spliterator()
does not support efficient parallelizing:
List<Integer> list = List.<Integer> nil().cons(3).cons(2).cons(1);
list.parallelStream().forEach(i -> {
System.out.println(i);
try {
Thread.sleep(1000);
} catch (Exception e) {
e.printStackTrace();
}
});
This will print 1, 2, 3
sequentially.
How to implement spliterator()
to support efficient parallelizing?
The spliterators which cannot report even the estimated size (which is default implementation for
Iterable
) are poorly split by parallel pipeline. You can fix this issue if you track the size of theList
. In your case it's not very hard to track the exact size:After that parallelization would work better. Note that it's still poor man parallelization, because you cannot quickly jump to the middle of the list, but in many cases it will provide a reasonable speed-up.
Also note that it's better to explicitly specify the
Spliterator.ORDERED
characteristic. Otherwise the order may be ignored in parallel stream operations even if it's explicitly requested (for example, byforEachOrdered()
terminal operation).