6

これは、不変のリンク リストの古典的な実装です。

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()効率的な並列化をサポートするために実装する方法は?

4

2 に答える 2

3

推定サイズ ( のデフォルトの実装) さえ報告できないスプリッテレータは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()端末操作などで)、並列ストリーム操作で順序が無視される場合があります。

于 2015-08-17T08:10:36.610 に答える
1

インターリーブで何らかのアルゴリズムを使用する場合があります。たとえば、要素をカウントし、整数除算後の剰余を使用します。これにより、並列反復のために要素が分割される可能性があります。

リストをintervalに分割するために、 iterator が構築される前に 1 回反復することもできますが、それは stream の目的にanyMatch反します。

いくつかの追加情報を持つリンク リストの独自の実装を作成しない限り、リンク リストを (線形時間よりも短い時間で) 分割する本当に効率的な方法はありません。

編集：ちょっと待ってください-実装するだけIterableです。これは非常に制限的です。パスが 1 つしかないアルゴリズムを考え出す必要があります。つまり、分割自体はまったく並列ではないため、プロセスの他の場所で並列処理を強制することもできます。

于 2015-08-17T07:49:47.167 に答える