20

大規模なコレクションの非破壊的な操作が関数型プログラミングでどのように実装されているかを理解しようとしています。変更されていないものも含め、すべての要素がメモリ内で複製される完全に新しいコレクションを作成する必要なく、単一の要素を変更または削除する方法。(元のコレクションがガベージ コレクションされたとしても、そのようなコレクションのメモリ フットプリントと一般的なパフォーマンスはひどいものになると思います。)

これは私が今までに得た距離です：

insertF# を使用して、変更されていない要素をすべて複製することなく、リストを 2 つの部分に分割し、間に新しい要素を導入する関数を考え出しました。

// return a list without its first n elements:
// (helper function)
let rec skip list n =
    if n = 0 then
        list
    else
        match list with
        | []    -> []
        | x::xs -> skip xs (n-1)

// return only the first n elements of a list:
// (helper function)
let rec take list n =
    if n = 0 then
        []
    else
        match list with
        | []    -> []
        | x::xs -> x::(take xs (n-1))

// insert a value into a list at the specified zero-based position:
let insert list position value =
    (take list position) @ [value] @ (skip list position)

次に、.NET を使用して、元のリストのオブジェクトが新しいリストで「リサイクル」されているかどうかを確認しましたObject.ReferenceEquals。

open System

let (===) x y =
    Object.ReferenceEquals(x, y)

let x = Some(42)
let L = [Some(0); x; Some(43)]
let M = Some(1) |> insert L 1

次の 3 つの式はすべて に評価されtrue、 によって参照される値がリストおよびのx両方で再利用されることを示します。メモリ内にこの値のコピーが 1 つしかないこと:LM

L.[1] === x
M.[2] === x
L.[1] === M.[2]

私の質問：

関数型プログラミング言語は通常、値を新しいメモリの場所に複製するのではなく、値を再利用しますか?それとも、F# の動作で幸運だったのでしょうか? 前者を仮定すると、関数型プログラミングでコレクションのメモリ効率の高い編集をどのように実装できるのでしょうか?

(ちなみに、私はChris Okasaki の著書Purely Functional datastructuresについては知っていますが、まだ十分に読む時間がありませんでした。)

4

5 に答える 5

28

大規模なコレクションの非破壊的な操作が関数型プログラミングでどのように実装されているかを理解しようとしています。変更されていないものも含め、すべての要素がメモリ内で複製される完全に新しいコレクションを作成する必要なく、単一の要素を変更または削除する方法。

このページには、F# のデータ構造の説明と実装がいくつか含まれています。それらのほとんどは、岡崎のPurely Functional Data Structuresから来ていますが、AVL ツリーは本に記載されていないため、私自身の実装です。

さて、変更されていないノードの再利用について質問されたので、単純な二分木を見てみましょう。

type 'a tree =
    | Node of 'a tree * 'a * 'a tree
    | Nil

let rec insert v = function
    | Node(l, x, r) as node ->
        if v < x then Node(insert v l, x, r)    // reuses x and r
        elif v > x then Node(l, x, insert v r)  // reuses x and l
        else node
    | Nil -> Node(Nil, v, Nil)

一部のノードを再利用していることに注意してください。このツリーから始めるとしましょう:

ツリーにを挿入するeと、まったく新しいツリーが得られ、ノードの一部は元のツリーを指しています。

上記のツリーへの参照がない場合、.NET はライブ参照のないノード、特におよびノードxsをガベージ コレクションします。dgf

挿入したノードのパスに沿ったノードのみを変更したことに注意してください。これは、リストを含むほとんどの不変データ構造で非常に一般的です。したがって、作成するノードの数は、データ構造に挿入するためにトラバースする必要があるノードの数とまったく同じです。

関数型プログラミング言語は通常、値を新しいメモリの場所に複製するのではなく、値を再利用しますか?それとも、F# の動作で幸運だったのでしょうか? 前者を仮定すると、関数型プログラミングでコレクションのメモリ効率の高い編集をどのように実装できるのでしょうか?

はい。

ただし、リストに対する重要な操作のほとんどは O(n) 時間を必要とするため、リストはあまり優れたデータ構造ではありません。

バランスのとれた二分木は O(log n) 個の挿入をサポートします。つまり、挿入ごとに O(log n) 個のコピーを作成します。log 2 (10^15) は ~= 50 であるため、これらの特定のデータ構造のオーバーヘッドは非常に小さいです。挿入/削除後にすべてのオブジェクトのすべてのコピーを保持しても、メモリ使用量は O(n log n) の割合で増加します-私の意見では非常に合理的です。

于 2010-01-03T03:56:50.387 に答える
12

変更されていないものも含め、すべての要素がメモリ内で複製される完全に新しいコレクションを作成することなく、単一の要素を変更または削除する方法。

これが機能するのは、コレクションの種類に関係なく、要素へのポインターが要素自体とは別に格納されるためです。(例外: 一部のコンパイラは最適化する場合もありますが、彼らは何をしているのかを知っています。) したがって、たとえば、最初の要素だけが異なり、テールを共有する 2 つのリストを作成できます。

let shared = ["two", "three", "four"]
let l      = "one" :: shared
let l'     = "1a"  :: shared

これら 2 つのリストにはshared共通部分があり、最初の要素が異なります。それほど明白ではないのは、各リストも、しばしば「コンス セル」と呼ばれる一意のペアで始まることです。

  • リストは、共有テールへのポインターとlポインターを含むペアで始まります。"one"

  • リストは、共有テールへのポインターとl'ポインターを含むペアで始まります。"1a"

宣言しただけで、 getの最初の要素を変更または削除しlたい場合は、次のようにします。l'

let l' = match l with
         | _ :: rest -> "1a" :: rest
         | []        ->  raise (Failure "cannot alter 1st elem of empty list")

一定のコストがあります:

  • lコンスセルを調べて、頭と尾に分割します。

  • "1a"テールを指す新しいコンス セルを割り当てます。

新しいコンスセルは list の値になりますl'。

大きなコレクションの途中でポイントのような変更を行う場合、通常、対数時間と空間を使用するある種のバランスの取れたツリーを使用します。より洗練されたデータ構造を使用する頻度は低くなります。

  • Gerard Huet のジッパーは、ほぼすべてのツリー状のデータ構造に対して定義でき、トラバースして一定のコストで点状の変更を行うために使用できます。ジッパーは分かりやすいです。

  • Paterson と Hinze のフィンガー ツリーは、シーケンスの非常に洗練された表現を提供します。これにより、要素を途中で効率的に変更できますが、理解するのは困難です。

于 2010-01-03T05:24:54.370 に答える
5

参照されるオブジェクトはコード内で同じですが、参照自体のストレージスペースがあり、リストの構造がtake. その結果、参照されるオブジェクトは同じで、テールは 2 つのリスト間で共有されますが、最初の部分の「セル」は複製されます。

私は関数型プログラミングの専門家ではありませんが、ルートから挿入された要素へのパスのみを再作成する必要があるため、ある種のツリーを使用すると、log(n) 要素のみを複製できる可能性があります。

于 2010-01-03T02:57:00.740 に答える
4

あなたの質問は主に不変データに関するものであり、関数型言語自体ではないように思えます。確かに、データは純粋に機能的なコードでは必然的に不変ですが (参照の透過性を参照)、どこでも絶対的な純粋性を強制する非おもちゃの言語は知りません (ただし、そのようなことが好きなら、Haskell が最も近いです)。

大まかに言えば、参照透過性とは、変数/式とそれが保持/評価する値の間に実質的な違いがないことを意味します。不変データの一部は (定義により) 決して変更されないため、その値で自明に識別でき、同じ値を持つ他のデータと区別なく動作する必要があります。

したがって、同じ値を持つ 2 つのデータ間で意味的な区別をしないことを選択した場合、意図的に重複値を作成する理由はありません。したがって、明らかな同等の場合 (たとえば、リストに何かを追加する、関数の引数として渡すなど)、不変性の保証が可能な言語は、一般に、あなたが言うように既存の参照を再利用します。

同様に、不変データ構造は、その構造の本質的な参照透過性を持っています (ただし、その内容ではありません)。含まれているすべての値も不変であると仮定すると、これは、構造の一部を新しい構造でも安全に再利用できることを意味します。たとえば、cons リストの末尾はしばしば再利用できます。あなたのコードでは、私はそれを期待します:

(skip 1 L) === (skip 2 M)

……それもまた然り。

ただし、再利用が常に可能であるとは限りません。たとえば、関数によって削除されたリストの最初の部分は、skip実際には再利用できません。同じ理由で、cons リストの末尾に何かを追加することは、null で終わる文字列を連結する際の問題と同様に、まったく新しいリストを再構築する必要があるため、コストのかかる操作です。

このような場合、素朴なアプローチは、心配していたひどいパフォーマンスの領域にすぐに入ります。多くの場合、基本的なアルゴリズムとデータ構造を大幅に再考して、それらを不変データにうまく適応させる必要があります。手法には、構造を階層化または階層化された部分に分割して変更を分離する、構造の一部を反転して頻繁に変更される部分に安価な更新を公開する、または元の構造を更新のコレクションと一緒に保存し、更新をその場でのみ元の構造と組み合わせることが含まれます。データがアクセスされたとき。

ここでは F# を使用しているため、C# にある程度慣れていることを前提としています。計り知れない Eric Lippert は、C# の不変データ構造に関する多数の投稿を行っています。いくつかの投稿の過程で、彼はとりわけ、スタック、バイナリ ツリー、および両端キューの (かなり効率的な) 不変の実装を示しています。すべての .NET プログラマーにとって楽しい読書です!

于 2010-01-03T04:20:17.030 に答える
0

関数型プログラミング言語の式のリダクション戦略に興味があるかもしれません。このテーマに関する優れた本は、Haskell の作成者の 1 人である Simon Peyton Jones によるThe Implementation of Functional Programming Languagesです。共通部分式の共有について説明しているため、特に次の章「ラムダ式のグラフ削減」を参照してください。お役に立てば幸いですが、残念ながらこれは遅延言語にのみ適用されます。

于 2010-01-03T04:08:44.417 に答える