2

次の要点のコードは、 Courseraの Martin Odersky の「Scala での関数型プログラミングの原則」コースの講義からほぼそのまま引用されています。

https://gist.github.com/aisrael/7019350

unionこの問題は、 in classの定義内の 38 行目で発生しますNonEmpty。

def union(other: IntSet): IntSet =
  // The following expression doesn't behave associatively
  ((left union right) union other) incl elem

指定された式 では((left union right) union other)、largeSet.union(Empty)100 個以上の要素を持つセットを完了するのに非常に時間がかかります。

その式が に変更される(left union (right union other))と、ユニオン操作は比較的瞬時に終了します。

追加: これは、ランダムな要素を持つ大きなセット/ツリーでも、式 ((left ∪ right) ∪ other) が永遠にかかる可能性があることを示す更新されたワークシートですが、(left ∪ (right ∪ other)) は即座に終了します。

https://gist.github.com/aisrael/7020867

4

2 に答える 2

5

あなたの質問への答えは、リレーショナル データベースと、その賢明な選択に大きく関係しています。データベースがテーブルを「結合」する場合、スマート コントローラー システムは、「テーブル A の大きさは? A & B を最初に結合するか、ユーザーが次のように記述したときに A & C を結合する方が理にかなっていますか?」などについていくつかの決定を下します。 

 A Join B Join C

とにかく、コードを手で書いているときと同じ動作を期待することはできません。括弧を使用して、必要な順序を正確に指定しているためです。これらの賢明な決定は、自動的に行われることはありません。（理論的には可能ですが、それがOracle、Teradata、mySqlが存在する理由です）

とてつもなく大きな例を考えてみましょう:

Set A  - 1 Billion Records
Set B  - 500 Million Records
Set C   -  10 Records

議論のために、結合演算子は、結合される 2 つのセットの最も小さなものによって O(N) レコードを取ると仮定します。これは合理的です。各キーは、ハッシュされた検索として他のキーで検索できます。

A & B ランタイム = O(N) ランタイム = 500 ミリオン (クラスは、ルックアップに 2 つのうち小さい方を使用するのに十分スマートであると仮定しましょう)

それで

(A & B) & C 

Results in:

O(N) 500 million +  O(N) 10  = 500,000,010 comparisons

10 億のレコードと 5 億のレコードを最初に、内側の括弧ごとに比較することを余儀なくされたという事実を再び指摘すると、さらに 10 を引き込みます。

しかし、これを考慮してください：

A & (B & C)

さて、驚くべきことが起こります：

(B & C) runtime O(N) = 10 record comparisons (each of the 10 C records is checked against B for existence)
then
A & (result) = O(N) = 10

Total = 20 comparisons

(B & C) が完了すると、10 億に対して 10 のレコードをバンプするだけで済みます。

どちらの例でもまったく同じ結果が得られます。1 つは O(N) = 20 ランタイム、もう 1 つは 500,000,010 です。

要約すると、この問題は、データベース設計に入る複雑な考え方と、そのソフトウェアで発生するスマートな最適化の一部をほんの少しだけ示しています。これらのことは、そのようにコーディングしたり、ある種のライブラリを使用したりしない限り、プログラミング言語で常に自動的に発生するとは限りません。たとえば、いくつかのセットを取り、ユニオンの順序をインテリジェントに決定する関数を作成できます。しかし、他のセット操作を混在させる必要がある場合、問題は信じられないほど複雑になります。これが役立つことを願っています。

于 2013-10-17T06:30:05.143 に答える
2

結合性はパフォーマンスに関するものではありません。2 つの式は結合性によって同等である可能性がありますが、実際に計算するのは一方が他方よりもはるかに難しい場合があります。

(23  * (14/2))  * (1/7)

と同じです

23  * ((14/2)  * (1/7))

しかし、2つを評価するのが私だったら、2番目のものですぐに答え（23）に到達しますが、最初のものだけで作業するように強制すると、時間がかかります.

于 2013-10-17T05:50:07.393 に答える