29

私は現在、仕事の後の空き時間にCourseraでScalaコースを受講しており、関数型プログラミングを最終的に試してみています. 私は現在、いくつかのオブジェクトを含む 2 つのセットの結合を「計算」することになっている割り当てに取り組んでいます。私がここで質問しようとしていることはそれほど重要ではないので、意図的に詳細を省略しています。ただし、関連するのは、セットがバイナリ ツリーとして定義され、各ノードに要素と 2 つのサブツリーが含まれていることです。

そうです。講義の例unionは次のとおりです。

def union(other:BTSet) :BTSet = ((left union right) union other) incl element

質問 1:率直に言って、関連する FAQ や他のフォーラム スレッドを読んだ後でも、この機能がどのように、なぜ機能するのかまだ理解できません。ここでは、ヘッド ノードに要素を追加 (呼び出し) する以外に、ユニオンの実装で行われる "アクション" はまったくありませんincl。それ自体が何度も何度も呼び出されるだけです。どなたか解説いただけると助かります...

質問 2:コース フォーラムには、このソリューションはまったく効率的ではなく、十分ではないという多くの投稿が含まれています。そもそも仕組みがわからないので、なぜダメなのかよくわかりません。

割り当ての解決策についてネタバレを求めているわけではないことに注意してください。私は「成績のために仕事をする」ことをいとわないのですが、ここで何をすべきかがわかりません。このコースで提供される指示とガイダンスは、関数型プログラミングの癖に頭を悩ませるのに十分ではないと思います。したがって、正しいコーディング方法ではなく、正しく考える方法に対処するコメント/回答を歓迎します。

4

6 に答える 6

5

incl要素を既存のセットに挿入することを収集しますか? もしそうなら、それはすべての本当の仕事が起こっているところです。

ユニオンの定義は、いずれかの入力セットのすべてを含むセットです。バイナリ ツリーとして格納された 2 つのセットが与えられた場合、最初のセットと 2 番目のセットの分岐を結合すると、結果から欠落する可能性がある唯一の要素は、2 番目のツリーのルート ノードにある要素です。その要素を挿入すると、両方の入力セットの結合があります。

これは、両方のセットの各要素を空で始まる新しいセットに挿入する非常に非効率的な方法です。おそらく重複は によって破棄されるinclため、結果は 2 つの入力の結合になります。

当面はツリー構造を無視することが役立つかもしれません。本質的なアルゴリズムにとってはそれほど重要ではありません。抽象的な数学的集合があるとします。未知の要素を含む入力セットが与えられた場合、次の 2 つのことを行うことができます。

  • 要素を追加します (要素が既に存在する場合は何もしません)
  • セットが空でないかどうかを確認し、空である場合は、それを 1 つの要素と 2 つの互いに素なサブセットに分解します。

2 つのセット {1,2} と {2,3} の結合を取得するには、最初のセットを要素 1 とサブセット {} と {2} に分解することから始めます。同じプロセスを使用して {}、{2}、および {2,3} の結合を再帰的に取得し、結果に 1 を挿入します。

各ステップで、問題は 1 つの和集合操作から、より小さな入力に対する 2 つの和集合操作に削減されます。標準的な分割統治アルゴリズム。シングルトン セット {x} と空のセット {} の和集合に到達すると、和集合は自明に {x} になり、チェーンを上に戻されます。

ツリー構造は、ケース分析/小さなセットへの分解を可能にし、挿入をより効率的にするために使用されます。分解のために半分に分割されたリストや、一意性の徹底的なチェックによって挿入が行われたリストなど、他のデータ構造を使用して同じことを行うことができます。ユニオンを効率的に取得するには、もう少し賢いアルゴリズムが必要で、要素を格納するために使用される構造を利用します。

于 2013-04-25T14:54:44.053 に答える
3

したがって、上記のすべての回答に基づいて、本当の働き者はセット内のすべての要素を通過するためinclのものであり、再帰的な呼び出し方法であると思います。union

次のユニオンの実装を思いつきましたが、これはより良いですか?

def union(other:BTSet) :BTSet = right union (left union (other incl element))
于 2016-06-19T23:03:57.567 に答える
2 
  2
 / \  union  4
1   3

((1 union 3) union 4) incl 2
  ^^^^^^^^^......................................assume it works

(((E union E) union 3 incl 1) union 4) incl 2
   ^^^^^^^^^.....................................still E

(E union E) union 3 incl 1 = E union 3 incl 1 = 3 incl 1

次のサブツリーは1を含む3である必要があります 

(  3             ) 
(    \   union D ) incl 2
(      1         )


(((1 union E) union 4) incl 3) incl 2
   ^^^^^^^^^.......................................expand

(((( (E union E) union E) incl 1) union 4) incl 3) incl 2
      ^^^^^^^^^^^^^^^^^^^^^^^^^^..................still 1

((1 union 4) incl 3) incl 2
   ^^^^^^^^......................................continue

((((E union E) union 4) incl 1) incl 3) incl 2
   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^..........expand 1 union 4

((4 incl 1) incl 3) incl 2
  ^^^^^^^^^^^^^^^^^^^^^^^^^............Final union result

ありがとう@Rex Kerrがステップを引き出します。2 番目のステップを実際の実行時のステップに置き換えます。これにより、Scalaunion関数のより明確な説明が得られる可能性があります。

于 2014-05-12T18:42:11.397 に答える