17

Hash-consingは、指定されたオブジェクトのコピーを 1 つだけメモリに保持することで構成されます。つまり、2 つのオブジェクトが意味的に等しい (同じ内容) 場合、それらは物理的に等しい (メモリ内の同じ場所) 必要があります。この手法は通常、グローバル ハッシュ セットを保持し、ハッシュ セット内のオブジェクトと等しくない場合にのみ新しいオブジェクトを作成することによって実装されます。

追加の要件は、ハッシュ テーブル以外から参照されていない場合、ハッシュ テーブル内のオブジェクトが収集可能であることです。別の言い方をすれば、ハッシュ テーブルには弱参照を含める必要があります。

この問題は、一定の時間を確保する必要があるため、さらに複雑になります。したがって、浅く、ハッシュし、等価テストを行います。したがって、オブジェクトには、新しいオブジェクトがテーブルに追加されると増加する一意の識別子があります。

ノードの浅い要約を提供するタプルであり（デフォルトのハッシュと等価テストに適しています） 、オブジェクトSystem.Collections.Generic.Dictionary<key, node>である whereを使用する実用的な実装があります。唯一の問題は、がノードへの強い参照を保持することです!keynodeDictionary

Dictionaryto を使用することもできますがWeakReference、ダングリング参照を指すキーを解放することはできません。

使用を支持する人もSystem.Runtime.CompilerServices.ConditionalWeakTableいますが、このクラスは逆のようです。キーが収集されると値が解放されますが、値が収集されるとキーを解放する必要があります。

使用してみることができSystem.Runtime.CompilerServices.ConditionalWeakTable<node, node>ますが、カスタムハッシュと等価テストが必要になります...そして、デフォルトのハッシュ関数を使用する代わりに、仮想メソッドを使用しないConditionalWeakTableように文書化されています。GetHashCode()

したがって、私の質問:Dictionary値への弱い参照を保持し、参照がぶら下がったときにキーを解放するのと同等のものはありますか?

4

1 に答える 1

3

CWT が hash-consing 問題を解決しないのは正しいです。なぜなら、それは疑問を投げかけているからです - そのキーは参照の等価性を前提としています。ただし、CWT はキーや値を保持しないことに注意してください。ここに小さなテストがあります：

open System.Collections.Generic
open System.Runtime.CompilerServices

let big () =
    ref (Array.zeroCreate (1024 * 1024) : byte [])

let test1 () =
    let d = Dictionary(HashIdentity.Reference)
    for i in 1 .. 10000 do
        stdout.WriteLine(i)
        let big = big ()
        d.Add(big, big)
    d

let test2 () =
    let d = ConditionalWeakTable()
    for i in 1 .. 10000 do
        stdout.WriteLine(i)
        let big = big ()
        d.Add(big, big)
    d

私のマシンでtest1は、メモリが不足してtest2成功します。これは、CWT がキーと値を保持していない場合にのみ発生するようです。

ハッシュコンシングについては、Artem がコメントで提案していることをお勧めします。これが複雑すぎると思われる場合は、次のように、ユーザーに制御を与えることも非常に理にかなっています。

let f = MyFactory() // a dictionary with weak reference values hidden inside
f.Create(..) : MyObject // MyObject has no constructors of its own
f.Cleanup() // explicitly cleans up entries for collected keys

そうすれば、スレッド化を導入したり、GC の内部がどのように機能するかを調べたり、何か魔法をかけたりする必要はありません。ライブラリのユーザーは、テーブル全体を収集するファクトリ オブジェクトをクリーンアップするか、単に「忘れる」のが適切な場所を決定できます。

于 2013-03-27T16:06:34.413 に答える