Spliterator для неизменного связанного списка

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, это сильно замедлит вас.

Не существует действительно эффективного способа разделения связанного списка (менее чем за линейное время), если только вы не создадите собственную реализацию связанного списка, которая содержит некоторую дополнительную информацию.

Изменить: Ой, подождите - вы только реализовать Iterable, Это довольно ограниченно, вы должны придумать алгоритм, который имеет только один проход. Это означает, что само расщепление вообще не будет параллельным, так что вы могли бы также усилить свой параллелизм в другом месте процесса.