[解決済み】なぜJava Streamsはワンスオフなのですか？

質問

C#の IEnumerable 実行パイプラインは何度でも実行できますが、Javaではストリームは一度だけ「反復」できます。

ターミナル・オペレーションを呼び出すと、ストリームが閉じられ、使用できなくなります。 この「機能」は、多くのパワーを奪ってしまうのです。

その理由を想像すると ではなく 技術的なことです。この奇妙な制限の背景には、どのような設計上の配慮があったのでしょうか。

編集部：私が言っていることを実証するために、C#でのクイックソートの次の実装を考えてみましょう。

IEnumerable<int> QuickSort(IEnumerable<int> ints)
{
  if (!ints.Any()) {
    return Enumerable.Empty<int>();
  }

  int pivot = ints.First();

  IEnumerable<int> lt = ints.Where(i => i < pivot);
  IEnumerable<int> gt = ints.Where(i => i > pivot);

  return QuickSort(lt).Concat(new int[] { pivot }).Concat(QuickSort(gt));
}

さて、私はこれがクイックソートの優れた実装であると主張しているわけではありません。しかし、ラムダ式とストリーム操作の組み合わせの表現力を示す素晴らしい例です。

そして、これはJavaではできないのです！（笑 ストリームが空かどうかを問うことさえ、それを使用不能にすることなくできません。

どうすれば解決するの？

Streams APIの初期の設計から、設計の根拠を明らかにするような思い出があります。

2012年当時、私たちはラムダを言語に追加していました。そして、ラムダを使ってプログラムされた、並列処理を容易にするコレクション指向の、あるいはバルクデータ（quot; bulk data"）操作群を欲していました。この時点では、演算を連鎖させるという考え方は確立されていました。また、中間処理に結果を保存することも考えていませんでした。

私たちが決定しなければならない主な問題は、チェーン内のオブジェクトがAPI上でどのように見えるか、そしてそれらがどのようにデータソースにフックされるかということでした。データソースはコレクションであることが多いのですが、ファイルやネットワークからのデータ、あるいは乱数発生器のようなその場で生成されるデータもサポートしたいと考えました。

設計にあたっては、既存の作品から多くの影響を受けています。中でも特に影響を受けたのは、Googleの グアバ とScalaのコレクション・ライブラリです。(もしGuavaからの影響に驚く人がいたら、次のことに注意してください。 ケビン・ブーリオン には、Guavaのリード開発者が参加していました。 JSR-335 ラムダ 専門家グループ) Scalaのコレクションについては、Martin Odersky氏のこの講演が特に興味深いものでした。 Scala コレクションの将来性: 変更可能から持続性、並列性へ . (スタンフォード EE380, 2011年6月1日.)

当時のプロトタイプのデザインは、以下のようなものでした。 Iterable . おなじみの操作 filter , map などは拡張（デフォルト）メソッドで Iterable . そのうちの1つを呼び出すと、チェーンにオペレーションが追加され、別の Iterable . のような末端の操作は count を呼び出すと iterator() をソースまで連鎖させ、各ステージのIteratorの中で操作を実装していた。

これらはIterableなので iterator() メソッドを複数回実行します。するとどうなるでしょうか？

ソースがコレクションであれば、ほとんど問題なく動作します。コレクションはIterableであり、各呼び出しは iterator() は、他のアクティブなインスタンスとは独立した個別の Iterator インスタンスを生成し、それぞれが独立してコレクションを走査します。素晴らしい。

では、ファイルから行を読み込むようなワンショットのソースであればどうでしょうか？最初の Iterator はすべての値を取得し、2 番目以降の Iterator は空であるべきかもしれません。あるいは、値はイテレータの間でインターリーブされるべきかもしれません。あるいは、各イテレータはすべて同じ値を取得すべきかもしれません。では、2つのイテレータがあり、一方が他方より先に進んでしまった場合はどうでしょう？誰かが、2番目のイテレータの値を読み込むまでバッファリングする必要があります。さらに悪いことに、1つのイテレータですべての値を読み込んで、その中で では 2番目のイテレータを取得します。このとき、値はどこから来るのでしょうか？すべての値がバッファリングされる必要があるのでしょうか？ 念のため 誰かが2つ目のイテレータを使いたいのでしょうか？

明らかに、ワンショットのソースに対して複数のイテレータを許可すると、多くの疑問が生じます。私たちは、それらに対する良い答えを持っていませんでした。を呼び出すとどうなるのか、一貫した予測可能な動作が欲しかったのです。 iterator() を2回行いました。そのため、複数回のトラバースを禁止し、パイプラインを一発で終了させる方向に持っていったのです。

また、このような問題にぶつかっている人がいることも確認しました。JDKでは、ほとんどのIterableはコレクションまたはコレクションに似たオブジェクトであり、複数のトラバーサルを許可しています。これはどこにも明記されていませんが、Iterable が複数のトラバースを可能にするという不文律の期待があるようです。注目すべき例外は、NIO ディレクトリストリーム インターフェイスです。その仕様には、次のような興味深い警告が含まれています。

DirectoryStreamはIterableを拡張していますが、1つのIteratorしかサポートしていないため、汎用のIterableではありません。2つ目以降のIteratorを取得するためにIteratorメソッドを起動するとIllegalStateExceptionがスローされます。

[原文のまま太字]

これは、一度しか使えないかもしれない新しいIterableを大量に作りたくないほど、異常で不快に思えたのです。そのため、Iterableの使用から遠ざかっていました。

この頃 ブルース・エッケルの記事 その中に、彼がScalaで経験したあるトラブルについて書かれているものがありました。彼はこんなコードを書いていました。

// Scala
val lines = fromString(data).getLines
val registrants = lines.map(Registrant)
registrants.foreach(println)
registrants.foreach(println)

かなりわかりやすいですね。これはテキスト行を解析して Registrant オブジェクトを生成し、それを2回出力します。ただし、実際には1回しか出力されません。それは、彼が registrants はコレクションですが、実際はイテレータです。2回目の foreach は空のイテレータに遭遇し、そこからすべての値を使い果たしたので、何も表示されません。

このような経験から、多重探索を試みた場合に結果が明確に予測できることが非常に重要であると確信しました。また、遅延パイプラインのような構造と、データを格納する実際のコレクションを区別することの重要性も浮き彫りになりました。このことが、遅延パイプライン操作を新しいStreamインタフェースに分離し、Collectionsに対する直接のイーガー、ミュータティブ操作のみを維持する原動力となりました。 Brian Goetzは次のように説明しています。 その根拠は？

コレクションベースのパイプラインでは多重巡回を認め、コレクションベースでないパイプラインでは認めないというのはどうでしょうか。矛盾していますが、賢明な方法だと思います。ネットワークから値を読み込む場合。 もちろん もう一回なぞることはできない。もし、複数回トラバースしたい場合は、明示的にコレクションに取り込む必要があります。

しかし、コレクションベースのパイプラインから複数のトラバースを許可することを検討してみましょう。例えば、こんなことをしたとしましょう。

Iterable<?> it = source.filter(...).map(...).filter(...).map(...);
it.into(dest1);
it.into(dest2);

(その into の操作は、現在ではスペル collect(toList()) .)

sourceがコレクションである場合、最初の into() の呼び出しは、ソースに戻るイテレータのチェーンを作成し、パイプライン操作を実行し、その結果をデスティネーションに送信します。2回目の into() は、別のイテレータのチェーンを作成し、パイプライン操作を実行します。 再び . これは明らかに間違ってはいませんが、各要素に対してすべてのフィルタリングとマップ操作を2回目に実行する効果があります。多くのプログラマーは、この動作に驚いたことでしょう。

前述したように、私たちはGuavaの開発者と話をしていました。彼らが持っているクールなもののひとつに アイデアの墓場 を決定した機能を記述しています。 ない その理由も含めて。遅延コレクションのアイデアはとてもクールなものに聞こえますが、それについては以下のように言っています。を考えてみましょう。 List.filter() を返す操作です。 List :

ここでの最大の懸念は、あまりにも多くの操作が高価な線形時間の命題になることです。コレクションやイテラブルではなく、リストをフィルタリングしてリストを取り出したい場合は ImmutableList.copyOf(Iterables.filter(list, predicate)) これは、何をするのか、そしてそれがどれだけ高価なものなのかを前もって示しているのです。

具体的な例を挙げると、以下のようなコストはどうでしょうか。 get(0) または size() をリストで使用することはできますか？のようなよく使われるクラスは ArrayList ということで、O(1)である。しかし、遅延フィルタリングされたリストに対してこれらの処理を呼び出すと、バックリスト上でフィルタを実行しなければならず、突然これらの処理がO(n)になってしまいます。さらに悪いことに、この演算は すべての の操作になります。

これは、私たちには、次のように思えました。 あまりに 怠慢です。いくつかの操作をセットアップして、実際に実行するのは "Go"するまで延期するのは一つの方法です。再計算が大量に発生する可能性があることを隠すように設定するのは、また別の話です。

非線形または "no-reuse"ストリームを認めないことを提案する際に。 ポール・サンド を説明した。 潜在的な結果 また、並列実行が事態をさらに厄介にするとも述べています。最後に、副作用のあるパイプライン操作は、その操作が予期せず複数回、あるいは少なくともプログラマの予想とは異なる回数実行された場合、困難で不明瞭なバグにつながることを付け加えます。(しかし、Javaプログラマは副作用のあるラムダ式は書きませんよね？どうなんだろう？）

これが、Java 8 Streams APIがワンショットのトラバースを可能にし、厳密に線形（分岐のない）パイプラインを必要とする設計であることの基本的な根拠となります。これは、複数の異なるストリームソースにまたがって一貫した動作を提供し、遅延操作とイーガー操作を明確に分離し、わかりやすい実行モデルを提供するものです。

についてですが IEnumerable 私はC#と.NETの専門家ではないので、もし間違った結論を出したら、（優しく）訂正していただけると幸いです。しかし、どうやら IEnumerable は、複数のトラバーサルが異なるソースで異なる動作をすることを許可し、また、ネストされた IEnumerable を実行すると、かなりの再計算が必要になる可能性があります。システムによってトレードオフが異なることは理解できますが、Java 8 Streams APIの設計では、この2つの特性を避けるように努めました。

OPが提示したクイックソートの例は、興味深く、不可解で、申し訳ないが、少々ぞっとするものだ。呼び出し QuickSort は IEnumerable を返し IEnumerable したがって、実際には最後の IEnumerable がトラバースされます。しかし、この呼び出しで行われるのは、以下のような木構造です。 IEnumerables これは、クイックソートが行うであろうパーティショニングを、実際には行わずに反映させたものです。(ソースにN個の要素がある場合、ツリーの幅は最大でN個、深さはlg(N)階層になります。

私はC#や.NETの専門家ではありませんが、このような場合、例えば、ピボットの選択には ints.First() 見た目以上にコストがかかります。もちろん、最初のレベルでは、O(1)です。しかし、木の奥深く、右端にあるパーティションを考えてみよう。このパーティションの最初の要素を計算するために、ソース全体をトラバースする必要があり、これはO(N)の処理です。しかし、上のパーティションは遅延パーティションなので、再計算が必要で、O(lg N)の比較が必要になります。つまり、ピボットの選択はO(N lg N)操作となり、これはソート全体と同じぐらい高価です。

しかし、実際にソートを行うのは、返された IEnumerable . 標準的なクイックソートのアルゴリズムでは、各レベルのパーティショニングでパーティションの数が2倍になります。各パーティションは半分のサイズしかないので、各レベルはO(N)の複雑さのままです。パーティションの木はO(lg N)の高さなので、全体の作業はO(N lg N)となります。

遅延IEnumerablesのツリーでは、ツリーの一番下にN個のパーティションが存在します。各パーティションを計算するには、N個の要素を走査する必要があり、それぞれは木の上方でlg(N)回の比較を必要とします。ツリーの底にあるすべてのパーティションを計算するためには、O(N^2 lg N)回の比較が必要です。

(これって正しいの？信じられません。誰か調べてください)

いずれにせよ、確かにカッコイイですね IEnumerable は、この方法で複雑な計算構造を構築することができます。しかし、もし私が考えるほど計算量が増えるのであれば、この方法でプログラミングすることは、よほど注意深くなければ避けるべきことのように思えます。