純粋に機能的なデータ構造の利点は何ですか？

StackOverflow https://stackoverflow.com/questions/4399837

質問

データ構造には多数のテキストがあり、データ構造コードのライブラリがあります。純粋に機能的なデータ構造が推論しやすいことを理解しています。ただし、必須の対応物で実用的なコード（機能的プログラミング言語を使用するかどうか）で純粋に機能的なデータ構造を使用するという現実世界の利点を理解するのに苦労しています。純粋に機能的なデータ構造に有利な現実世界のケースを提供できますか？

私が使用しているように、ラインに沿った例 data_structure_name の Programming_language やる 応用 それができるからです 特定の_thing.

ありがとう。

PS：純粋に機能的なデータ構造によって私が意味することは、永続的なデータ構造と同じではありません。永続的なデータ構造は、変更されないデータ構造です??一方、純粋に機能的なデータ構造は、純粋に動作するデータ構造です。

役に立ちましたか？

解決

純粋に機能的な（別名持続性または不変）データ構造により、いくつかの利点が得られます。

  • あなたはそれらをロックする必要はありません、それは非常に改善されます 並行性.
  • 構造を共有できます メモリの使用量を削減します. 。たとえば、Haskellのリスト[1、2、3、4]やJavaのような命令言語を考慮してください。 Haskellで新しいリストを作成するには、新しいものを作成するだけです cons （価値のペアとリファレンスからネクストエレメント）、それを前のリストに接続します。 Javaでは、前のものを損傷しないように完全に新しいリストを作成する必要があります。
  • 永続的なデータ構造を作成できます 怠惰.
  • また、機能スタイルを使用する場合、 時間と一連の操作を考えないでください, 、そして、あなたのプログラムをもっと作りましょう 宣言.
  • 事実、データ構造が不変であるため、さらに推測することができます。 言語の能力を拡張します. 。例えば、 Clojure 不一致の事実を使用して、各オブジェクトにHashCode（）メソッドの実装を正しく提供するため、すべてのオブジェクトをマップ内のキーとして使用できます。
  • 不変のデータと機能スタイルを使用すると、自由に使用することもできます メモ化.

一般的には、より多くの利点がありますが、それは現実の世界をモデル化するもう1つの方法です。 これ また、SICPの他の章では、不変の構造、その利点、および短所を備えたプログラミングのより正確な見解を提供します。

他のヒント

共有メモリの安全性に加えて、ほとんどの純粋な機能データ構造もあなたに与えます 持続性, 、そして実際には無料で。たとえば、私が持っているとしましょう set OCAMLで、私はそれにいくつかの新しい値を追加したいです私はこれを行うことができます：

module CharSet = Set.Make(Char)
let a = List.fold_right CharSet.add ['a';'b';'c';'d'] CharSet.empty in
let b = List.fold_right CharSet.add ['e';'f';'g';'h'] a in
...

a 残っています 変更されていない 新しい文字を追加した後（広告のみが含まれています）、 b AHが含まれ、彼らは同じメモリの一部を共有します（ set AVLツリーであり、ツリーの形状が変化するため、メモリが共有されるメモリの量を伝えるのはちょっと注意が必要です。私はこれを続けて、私が木に行ったすべての変更を追跡し、以前の状態に戻ることができるようにします。

これがからの素晴らしい図です 純粋に機能的なウィキペディアの記事 それは文字「E」をバイナリツリーに挿入する結果を示しています xs:

alt text

Erlangプログラムは、純粋に機能的なデータ構造をほぼ排他的に使用しており、複数のコアにほぼシームレスにスケーリングすることで大きな利点を享受します。共有データ（主にバイナリとビット文字列）が変更されることはないため、そのようなデータをロックする必要はありません。

F＃のこの小さなスニペットを取ります：

let numbers = [1; 2; 3; 4; 5]

100％確実に、それは整数1〜5の不変のリストであると言うことができます。そのリストへの参照を渡して、リストが変更されたことを心配する必要はありません。それが私がそれを使用するのに十分な理由です。

純粋に機能的なデータ構造には、次の利点があります。

  • 永続性：古いバージョンは、変更できないという知識の中で安全に再利用できます。

  • 共有：データ構造の多くのバージョンは、控えめなメモリ要件のみで同時に保持できます。

  • スレッドの安全性：すべての突然変異は、怠zyなサンクの内側（ある場合）内に隠されているため、言語の実装によって処理されます。

  • シンプルさ：状態の変更を追跡する必要がないと、特に並行性のコンテキストでは、純粋に機能的なデータ構造がより簡単に使用できます。

  • 増分：純粋に機能的なデータ構造は、多くの小さな部品で構成されているため、レイテンシが低いことにつながる漸進的なガベージコレクションに最適です。

私はこれが事実であるとは思わないので、純粋に機能的なデータ構造の利点として並列性をリストしていないことに注意してください。効率的なマルチコア並列性には、キャッシュを活用し、メインメモリへの共有アクセスにボトルネックを避け、純粋に機能的なデータ構造には、せいぜい、この点で未知の特性があります。したがって、純粋に機能的なデータ構造を使用する多くのプログラムは、マルチコアに並列化された場合、キャッシュミスにすべての時間を費やし、共有メモリ経路を競合するため、十分にスケーリングしません。

純粋に機能的なデータ構造によって私が意味することは、永続的なデータ構造と同じではありません。

ここには混乱があります。純粋に機能的なデータ構造のコンテキストでは、永続性は、まだ有効であるという知識で安全なデータ構造の以前のバージョンを参照する能力を指すために使用される用語です。これは純粋に機能的であることの自然な結果であるため、持続性はすべての純粋に機能的なデータ構造に固有の特性です。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top