6

Ocamlで可変変数のハッシュテーブルを使いたいのですがうまくいきません。

let link = Hashtbl.create 3;;
let a = ref [1;2];;
let b = ref [3;4];;
Hashtbl.add link a b;;

# Hashtbl.mem link a;;
- : bool = true

# a := 5::!a;;
- : unit = ()

# Hashtbl.mem link a;;
- : bool = false

それを機能させる方法はありますか?

4

2 に答える 2

8

独自のハッシュ関数と等式関数を提供できるファンクトリアルインターフェイスを使用できます。次に、値の変更不可能な部分のみに基づく関数を記述します。この例では、変更不可能な部分はありませんしたがって、テーブルで何を期待しているのかは特に明確ではありません。しかし、より現実的な例(私の経験では)では、使用できる変更不可能な部分があります。

変更できない部分がない場合は、ハッシュで使用するために特別に追加できます。たとえば、各値に任意の一意の整数を追加できます。

物理的同等性(==)に基づいてハッシュを実行することもできます。これには、参照(およびその他の可変値)の妥当な定義があります。ただし、物理的な平等は少し注意が必要なので、注意する必要があります。たとえば、値の物理アドレスをハッシュキーとして使用することはできません。アドレスは、ガベージコレクションのためにいつでも変更される可能性があります。

于 2012-04-23T15:22:52.903 に答える
5

たまたま同じ内容を持つ可能性のある可変変数は、メモリ内の異なる場所に格納されているため、区別することができます。それらは、物理的等価演算子 ( ) と比較できます==。しかし、OCaml は等価性よりも優れたものを提供しません。それは重要なハッシュ関数や参照の順序を提供しません。そのため、参照を格納するために構築できる唯一のデータ構造は、何らかの形式の連想リストであり、 $\Theta( n) ほとんどの用途で $ アクセス時間。

(下手くそなら、下にあるポインターを実際に取得できます。ただし、ポインターは足元を移動できます。それにもかかわらず、それを利用する方法はありますが、尋ねる必要がある場合は、使用しないでください。とにかく、そのために十分に必死ではありません。)

2 つの異なる参照の内容が異なる場合、参照を比較するのは簡単です。だからそうしよう!参照に一意の識別子を追加します。グローバル カウンターを保持し、参照を作成するたびに 1 ずつインクリメントし、データと共にカウンター値を保存します。これで、カウンター値によって参照にインデックスを付けることができます。

let counter = ref 0
let new_var x = incr counter; ref (!counter, x)
let var_value v = snd !v
let update_var v x = v := (fst !v, x)
let hash_var v = Hashtbl.hash (fst !v)

型の安全性と効率を向上させるには、カウンター値とアイテムを含むデータ構造を定義します。

let counter = ref 0
type counter = int
type 'a variable = {
    key : counter;
    mutable data : 'a;
}
let new_var x = incr counter; {key = !counter; data = x}
let hash_var v = Hashtbl.hash v.key

上記のコードをモジュールに配置して、counter型を抽象化できます。また、Hashtblfunctorial インターフェイスを使用してハッシュ テーブル モジュールを定義することもできます。よりクリーンでモジュール化された構造を使用して、変数とそれらのハッシュ テーブル構造を定義する別の方法を次に示します。

module Counter = (struct
  type t = int
  let counter = ref 0
  let next () = incr counter; !counter
  let value c = c
end : sig
  type t
  val next : unit -> t
  val value : t -> int
end)
module Variable = struct
  type 'a variable = {
      mutable data : 'a;
      key : Counter.t;
  }
  let make x = {key = Counter.next(); data = x}
  let update v x = v.data <- x
  let get v = v.data
  let equal v1 v2 = v1 == v2
  let hash v = Counter.value v.key
  let compare v1 v2 = Counter.value v2.key - Counter.value v1.key
end
module Make = functor(A : sig type t end) -> struct
  module M = struct
    type t = A.t Variable.variable
    include Variable
  end
  module Hashtbl = Hashtbl.Make(M)
  module Set = Set.Make(M)
  module Map = Map.Make(M)
end

Variablevariableはパラメトリックであり、標準ライブラリのデータ構造ファンクター ( Hashtbl.MakeSet.MakeMap.Make) は引数のない型コンストラクターに対してのみ定義されるため、中間モジュールが必要です。これは、ポリモーフィック インターフェイス (関連付けられた関数を含むが、データ構造は含まない) と、関連付けられたハッシュ テーブル (およびセットとマップ) 型を使用して、任意の数のモノモーフィック インスタンスを構築するためのファンクターの両方を公開するインターフェイスです。

module Variable : sig
  type 'a variable
  val make : 'a -> 'a variable
  val update : 'a variable -> 'a -> unit
  val get : 'a variable -> 'a
  val equal : 'a -> 'a -> bool
  val hash : 'a variable -> int
  val compare : 'a variable -> 'b variable -> int
end
module Make : functor(A : sig type t end) -> sig
  module M : sig
    type t = A.t variable.variable
    val make : A.t -> t
    val update : t -> A.t -> unit
    val get : t -> A.t
    val equal : t -> t -> bool
    val hash : t -> int
    val compare : t -> t -> int
  end
  module Hashtbl : Hashtbl.S with type key = M.t
  module Set : Set.S with type key = M.t
  module Map : Map.S with type key = M.t
end

プログラムが実行中に 2^30 を超える変数を生成する可能性があると予想される場合、intはそれをカットしないことに注意してください。2 int^60 ビット値、つまりInt64.t.

プログラムがマルチスレッド化されている場合、インクリメントとルックアップをアトミックにするために、カウンターをロックする必要があることに注意してください。

于 2012-04-24T00:24:49.757 に答える