8

構造化された値を記述する Graphviz ファイルを取得しようとしています。これは診断目的であるため、グラフにメモリ内の実際の構造をできるだけ厳密に反映させたいと考えています。以下を使用して値を Graphviz 頂点にマップし、値に 2 つ以上のインバウンド参照がある場合に頂点を再利用できるようにします。

let same = (==)

module StateIdentity : Hashtbl.HashedType = struct
  type t = R.meta_t state
  let hash = Hashtbl.hash
  let equal = same
end

module StateHashtbl = Hashtbl.Make (StateIdentity)

のドキュメントは、いつHashtbl.hashでもいつでも使用するのに適していることを示唆していますが、ハッシュテーブルへのアクセスが可能な限り O(1) に近いことを確認したいので、(この場合は潜在的に大きい) オブジェクトをウォークしたくありませんルックアップごとにグラフ化します。StateIdentity.equal = (=)StateIdentity.equal = (==)Hashtbl.hash

Ocaml が参照を移動することは知っていますが、Ocaml で使用できる参照 ID の O(1) プロキシはありますか?

Ocaml の変更可能な変数の Hashtableに対する答えは、そうではないことを示唆しています。

これは診断コードであるため、状態にシリアル番号を付けるのは嫌いです。これにより発生するエラーは、他のバグを隠す可能性があります。

4

4 に答える 4

6

< ... >OCaml のオブジェクト型の意味で「オブジェクト」という言葉を使用しているOo.id場合、各インスタンスの一意の整数 ID を取得するために使用できます。それ以外の場合、「値のアイデンティティの一般的なプロキシはありますか」に対する答えは「いいえ」です。この場合、私のアドバイスは、 から始めてHashtbl.hash、ニーズに合っているかどうかを評価し、それ以外の場合は独自のハッシュ関数を設計することです。

で遊んでHashtbl.hash_param(ドキュメントを参照)、ハッシュ中の値のトラバーサルでノブを回すこともできます。Hashtbl コードは、同じハッシュ値のバケットにリンクされたリストを使用するため、多数のハッシュ競合があると、線形検索動作がトリガーされることに注意してください。競合バケットに二分探索木を使用する他の実装に移行する方がよい場合があります。ただし、より複雑な (そして「良いケース」ではパフォーマンスが低下する) ソリューションに移行する前に、状況を評価する必要があります。

于 2012-10-24T15:49:56.263 に答える
5

物理的等価性を使用してハッシュを行うのは非常に難しいことがわかりました。（あなたが言うように）物事はGCによって移動されるため、値のアドレスのようなものをハッシュキーとして使用することはできません。ハッシュキーを取得したら、値が変更可能である限り、物理的な等価性を使用して比較を行うことができるようです。値が可変でない場合、OCaml は (==) の意味についてあまり保証しません。実際には、等しい (=) である不変オブジェクトは、OCaml コンパイラまたはランタイムが望む場合 (またはその逆)、理論的には単一の物理オブジェクトにマージできます。

さまざまな可能性を検討するとき、一意の ID が必要な場合、通常はシーケンス番号を値に入れます。Gasche が言うようにOo.id、値が実際の OO スタイルのオブジェクトである場合に使用できます。

于 2012-10-24T15:59:54.827 に答える
4

他の人と同じように、私は一意のIDが行く方法だと思います。

一意のIDを安全に生成することは難しくありません。1つの解決策は、次のようにいわゆるプライベートレコードを使用することです。モジュールのユーザーがidフィールドをコピーできないようにします。

モジュールタイプIntf=
sig
  タイプt=private {
    id：int;
    foo：文字列;
  }

  val create_t：foo：string-> t
終わり

モジュールImpl：Intf =
構造体
  タイプt={
    id：int;
    foo：文字列;
  }

  create_id =
    n =ref0を
    楽しい（）->
      ！n = -1の場合、
        「一意のIDが不足しています」で失敗します
      そうしないと （
        incr n;
        ！n
      ）。

  create_t〜foo = {
    id = create_id（）;
    foo
  }
終わり
于 2012-10-24T17:02:13.037 に答える
4

醜いハックで申し訳ありませんが、私は少し前にそのようなものを作りました。

その秘訣は、テーブルに挿入した後に値がメモリに移動されないようにすることです。メモリ内の値を移動できる状況は 2 つあります。マイナー ヒープからメジャー ヒープへのコピーと、メジャー ヒープの圧縮です。つまり、テーブルに値を挿入するときは、メジャー ヒープにある必要があり、テーブルに対する 2 つの操作の間に圧縮が発生しないようにする必要があります。

値がマイナー ヒープにあることを確認するには、C 関数 is_young を使用します。そうである場合は、Gc.minor () を使用して値を強制的にメジャー ヒープに移行できます。

2 番目の問題については、圧縮を完全に無効にするか、圧縮でテーブルを再構築することができます。無効にするには、

Gc.set { Gc.get () with Gc.max_overhead = max_int }

圧縮が発生したことを検出するには、テーブルへの各アクセスで返された数値を比較します。

( Gc.quick_stat () ).Gc.compactions

テーブルにアクセスする前に、圧縮を無効にする必要があることに注意してください。圧縮を無効にする場合は、割り当てポリシーを変更して、ヒープの無制限の断片化を回避することも検討する必要があります。

Gc.set {(Gc.get ()) with Gc.allocation_policy = 1}

OCaml の古いバージョン (4.00 より前) で本当に醜いものが必要な場合は、コンパクションが値をメモリ内の同じ順序で保持するため、心配することなく物理アドレスに基づいてセットまたはマップを実装できます。

于 2012-10-24T21:00:43.220 に答える