2

その性質が整っているので、それpriorityQueueは完璧だと理解しています。Array

OCaml のリストに PriorityQueue (ヒープ) を実装する必要がありますか?

でそれを行う場合List、そのことを削除して、すべてのステップで新しいリストを作成するin-place方法を考えなければなりません. every timeだから、それが価値があるかどうか疑問に思っています。

実は、私はこれについてもっと深い考えを持っています。

そのため、多くのfundamentalアルゴリズム/データ構造が発明されましたin-place(invented多くのインプレースを に変換できることを理解しているため、使用しますnot-in-place)。

ただし、物FLはお勧めしませんmutable。さらなる質問の 1 つは、 と をどのように選択するかということです。in-place / mutableimmutableまたはOCamlでは、いつ と の間listで選択する必要がありarrayますか?

例えば、上記のpriorityqueue場合、priorityqueueOCaml でa を書くように言われたらarray、より自然で簡単なリストを選ぶべきでしょうか、それとも不変であるためにリストを選ぶべきでしょうか?

4

3 に答える 3

3

不変データを使用すると、モジュール性と信頼性において驚くべき利点が得られます。本質的に、他のモジュールによる変更によってデータが破損することは不可能になります。モジュールは、他のモジュールや、誰がデータを「所有」しているかについて心配する必要がなくなりました。もはやそれを行う必要がなくなるまで、これがどれほど面倒なことであるかはわかりません。もう 1 つの予想外の利点は、コードが数学関数のように機能するため、コードの動作を推論するのがはるかに簡単になることです。私は実際にこれらの両方を経験しており、これが私を FP 信者にしました。コストは一般的に驚くほど控えめで、小さな定数係数か、余分なlog nのいずれかです。

不変データのもう 1 つの利点は永続性です。つまり、余分な作業をせずにデータの履歴状態を維持できるということです。(不変の環境で元に戻す操作を実装するのは興味深いことです。)

そうは言っても、私は可変データを使用することがあります。

メタコメントとして、OCaml で不変データのみを使用することに時間を費やすことをお勧めします。他に何もないとしても、最初は非常に興味深いパズルになります。いくつかの直接的な経験の後、特定のケースでトレードオフがどこにあるのかを判断できるようになります。したがって、不変の優先度キューを実装することをお勧めします (または、他の人がどのようにそれを行ったかを読んでください)。

于 2013-03-01T18:19:43.347 に答える
2

バッテリーには効率的な機能ヒープがあります: http://ocaml-batteries-team.github.com/batteries-included/hdoc2/BatHeap.html find_min は O(1) で、他のすべてのヒープ操作は log(n) です。

実装は、岡崎で説明されている標準的な二項ヒープだと思います。こちらをご覧ください: https://github.com/ocaml-batteries-team/batteries-included/blob/master/src/batHeap.ml

ただし、破壊的な操作でヒープを引き続き主張する場合は、コアには .NET から引き裂かれた実装があると思います。あなたはよく見る必要があります。

さらに重要なことは、Jeffrey の意見に同意し、まず関数型データ構造に慣れ、絶対に必要な場合にのみ命令型データ構造を使用することを提案することです。これは以前にも提案されたことがあると思いますが、この種の情報の最良の情報源は、岡崎の純粋関数型データ構造の本です。あまりお勧めできません。

于 2013-03-01T19:19:42.877 に答える
2

バイナリ ヒープ (おそらく考えているプラ​​イオリティ キューの実装) は通常、動的配列 (一部の言語では「ベクトル」と呼ばれます)、つまり要素を追加または要素を削除できる配列に実装されます。arrayサイズが固定されているため、適切ではありません。サイズは作成時に固定されます。最初に の上に動的配列構造をarray実装してから、その上にバイナリ ヒープを実装することができます。

プライオリティ キューのもう 1 つのオプションは、自己均衡二分探索木を使用することです。OCaml 標準ライブラリには、自己均衡型二分探索木を使用したいくつかのデータ構造が既にありSet、Mapそれらは不変で機能的なデータ構造として実装されています。自己均衡バイナリ検索ツリーは、ほとんどの操作でバイナリ ヒープと同じ時間の複雑さを提供します (最小要素を削除して要素を追加します。両方の構造で O(log n) です)。最小要素 (バイナリ ヒープの場合は O(1)、ツリーの場合は O(log n)) をピークにするのは効率的ではありませんが、通常はそれ自体では使用されません。使用に関する問題の 1 つSetは、要素の重複が許可されないことです。理想的には「マルチセット」が必要ですが、OCaml の標準ライブラリにはありません。要素の重複を気にしない場合は、

これに使用することはお勧めしませんlist。

于 2013-03-01T22:43:43.090 に答える