Ocaml에서 변경 가능한 변수의 해시 테이블

Question

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 

작동 방식은 있습니까?

Answer 1

동일한 내용을 가지고있을 수있는 가변 변수는 메모리의 다른 위치에 저장되기 때문에 여전히 구분할 수 있습니다. 그들은 물리적 평등 운영자 (==)와 비교 될 수 있습니다. 그러나 OCaml은 평등보다 좋은 것을 제공하지 않으며, 해시 함수 나 참조에 대한 순서를 제공하지 않으므로 참조를 저장하기 위해 작성할 수있는 유일한 데이터 구조는 $ \ Theta (와 같은 형식의 연관 목록입니다. n) 대부분의 사용에 대한 $ 액세스 시간.

(더러운 게임을하면 기본 포인터에 실제로 도달 할 수 있지만 포인터는 발밑에서 움직일 수 있습니다. 그럼에도 불구하고 포인터를 움직일 수있는 방법이 있습니다.하지만 물어볼 필요가 있다면 사용할 수 없습니다. 어쨌든 그렇게 절박하지는 않습니다.)

두 개의 서로 다른 참조에 고유 한 내용이있는 경우 쉽게 참조를 비교할 수 있습니다. 그래서 그렇게해라! 참조에 고유 식별자를 추가하십시오. 전역 카운터를 유지하고 참조를 만들 때마다 카운터를 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 추상 형식으로 만들 수 있습니다. 또한 Hashtbl 재미있는 인터페이스를 사용하여 해시 테이블 모듈을 정의 할 수 있습니다. 더 명확하고 더 모듈화 된 구조로 변수와 해시 테이블 구조를 정의하는 또 다른 방법이 있습니다. 유형 variable 파라 메트릭 표준 라이브러리 데이터 구조 펑은 (Hashtbl.Make, Set.Make, Map.Make)는 단지 인수없이 형 생성자 정의되므로

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 

우리는 중간 모듈 Variable 필요하다. 다음은 관련 함수가 있지만 데이터 구조가없는 다형성 인터페이스와 연결된 해시 테이블 (및 세트 및 맵) 유형이있는 임의의 수의 단일 양식 인스턴스를 작성하는 펑터를 모두 표시하는 인터페이스입니다.당신이 당신의 프로그램이 실행 중에 2 개 이상^30 변수를 생성 할 것으로 예상 경우, int 그것을 잘라하지 않습니다

는

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^60 비트 값을 만들려면 두 개의 int 값 또는 Int64.t이 필요합니다.

프로그램이 다중 스레드 인 경우 증분 및 조회를 원할하게하려면 카운터 주변에 잠금 장치가 있어야합니다.

Answer 2

자신 만의 해시 및 동등 함수를 제공 할 수있는 기능 인터페이스를 사용할 수 있습니다. 그런 다음 값의 변경 불가능한 부분에만 기반한 함수를 작성합니다. 이 예에서 은이며 변경할 수없는 부분은 없습니다. 따라서, 당신이 테이블에서 무엇을 기대하고 있는지 명확하지 않습니다. 그러나 좀 더 현실적인 예 (내 경험상)에는 변경할 수없는 부분이 있습니다.

변경할 수없는 부분이없는 경우 해시에 사용할 부분을 특별히 추가 할 수 있습니다. 예를 들어, 각 값에 임의의 고유 한 정수를 추가 할 수 있습니다.

실제 등가성 (==)을 기반으로하는 해싱을 수행 할 수도 있습니다. 이는 참조 (및 기타 변경 가능한 값)에 대한 합리적인 정의가 있습니다. 육체 평등은 조금 까다 롭기 때문에 조심해야합니다. 예를 들어 값의 실제 주소를 해시 키로 사용할 수 없습니다. 주소는 가비지 수집으로 인해 언제든지 변경 될 수 있습니다.