不可变链表的分割器

Question

这是一个经典的不可变链表实现:

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; }
}

spliterator()的默认实现不支持高效并行化:

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();
    }
});

这将按顺序打印1, 2, 3。

如何实现spliterator()以支持高效并行化?

Answer 1

拆分器甚至不能报告估计的大小(这是Iterable的默认实现)，并行管道拆分效果很差。如果跟踪List的大小，可以解决此问题。在您的情况下，跟踪确切的大小并不难:

public abstract class List<A> implements Iterable<A> {
    ...
    public abstract long size();
    @Override
    public Spliterator<A> spliterator() {
        return Spliterators.spliterator(iterator(), size(), Spliterator.ORDERED);
    }
}
class Nil extends List {
    ...
    public long size() {
        return 0;
    }
}
class Cons<A> extends List<A> {
    ...
    private final long size;
    Cons(A head, List<A> tail) {
        this.head = head;
        this.tail = tail;
        this.size = tail.size()+1;
    }
    ...
    @Override
    public long size() {
        return size;
    }
}

在此之后，并行化将更好地工作。请注意，这仍然是较差的并行化，因为您不能快速跳到列表的中间，但在许多情况下，它将提供合理的加速。

还要注意，最好显式地指定Spliterator.ORDERED特性。否则，即使显式请求(例如，通过forEachOrdered()终端操作)，该顺序也可能在并行流操作中被忽略。

Answer 2

您可能会使用一些与交错的算法-例如，计算元素并在整数除法后使用余数。这样可以拆分元素以进行并行迭代。

你也可以在构造迭代器之前迭代一次，将列表分割成区间，但这会违背流的目的——例如，如果你在anyMatch中使用它，它会使你慢很多。

没有真正有效的方法来拆分链表(在小于线性时间内)，除非您创建了自己的链表实现，并且具有一些额外的信息。

Edit:哦，等等-你只实现Iterable。这是相当有限的，你必须想出一个只有一次通过的算法。这意味着，拆分本身根本就不是并行的，所以您不妨在进程的其他地方执行并行性。