Hashtable của biến có thể thay đổi trong Ocaml

Question

Tôi cần phải sử dụng hashtable của biến có thể thay đổi trong Ocaml, nhưng nó không hoạt động.

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 

Có cách nào để hoạt động không?

Answer 1

Biến có thể xảy ra có cùng nội dung vẫn có thể được phân biệt vì chúng được lưu trữ tại các vị trí khác nhau trong bộ nhớ. Chúng có thể được so sánh với toán tử bình đẳng vật lý (==). Tuy nhiên, OCaml không cung cấp bất cứ điều gì tốt hơn bình đẳng, nó không cung cấp hàm băm không tự phát hoặc thứ tự tham chiếu, do đó cấu trúc dữ liệu duy nhất bạn có thể xây dựng để lưu trữ tham chiếu là danh sách kết hợp của một số biểu mẫu, với $ \ Theta (n) $ thời gian truy cập để sử dụng nhiều nhất.

(Bạn thực sự có thể lấy con trỏ bên dưới nếu bạn chơi bẩn. Nhưng con trỏ có thể di chuyển dưới chân bạn. Tuy nhiên, có một cách để sử dụng nó, nhưng nếu bạn cần hỏi, bạn không nên sử dụng Và bạn không đủ tuyệt vọng cho điều đó.)

Sẽ dễ dàng so sánh các tham chiếu nếu hai tham chiếu riêng biệt có nội dung riêng biệt. Vì vậy, làm cho nó như vậy! Thêm số nhận dạng duy nhất vào tham chiếu của bạn. Giữ một bộ đếm toàn cầu, tăng nó lên 1 mỗi khi bạn tạo một tham chiếu và lưu trữ giá trị bộ đếm với dữ liệu. Giờ đây, các tham chiếu của bạn có thể được lập chỉ mục theo giá trị bộ đếm của chúng.

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) 

Để đảm bảo an toàn và hiệu quả hơn, hãy xác định cấu trúc dữ liệu chứa giá trị bộ đếm và mục.

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 

Bạn có thể đặt mã ở trên vào mô-đun và tạo ra tóm tắt loại counter. Ngoài ra, bạn có thể xác định mô-đun bảng băm bằng cách sử dụng giao diện functorial Hashtbl. Dưới đây là một cách khác để xác định các biến và cấu trúc bảng băm trên chúng với cấu trúc mô đun sạch hơn, mô đun hơn.

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 

Chúng ta cần các module trung gian Variable vì loại variable là tham số và functors cấu trúc dữ liệu thư viện chuẩn (Hashtbl.Make, Set.Make, Map.Make) được chỉ định cho loại hình nhà xây dựng không có tham số. Đây là một giao diện cho thấy cả giao diện đa hình (với các hàm liên quan, nhưng không có cấu trúc dữ liệu) và một hàm để xây dựng bất kỳ số lượng các cá thể đơn hình nào, với một bảng băm (và thiết lập và bản đồ) liên quan.

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 

Lưu ý rằng nếu bạn cho rằng chương trình của bạn có thể tạo hơn 2^30 biến trong khi chạy, int sẽ không cắt. Bạn cần hai giá trị int để tạo giá trị 2^60 bit hoặc Int64.t.

Lưu ý rằng nếu chương trình của bạn đa luồng, bạn cần khóa xung quanh bộ đếm, để tăng số lượng và tra cứu nguyên tử.

Answer 2

Bạn có thể sử dụng giao diện functorial, cho phép bạn cung cấp các hàm băm và bình đẳng của riêng bạn. Sau đó, bạn viết các hàm chỉ dựa trên các phần không thể thay đổi của các giá trị của bạn. Trong ví dụ này, có là không có bộ phận không thể thay đổi. Vì vậy, nó không phải là đặc biệt rõ ràng những gì bạn đang mong đợi để tìm thấy trong bảng. Nhưng trong một ví dụ thực tế hơn (theo kinh nghiệm của tôi) có những phần không thể thay đổi mà bạn có thể sử dụng.

Nếu không có bất kỳ bộ phận nào không thể thay đổi, bạn có thể thêm chúng một cách cụ thể để sử dụng trong băm. Bạn có thể thêm một số nguyên duy nhất tùy ý cho mỗi giá trị, ví dụ.

Cũng có thể thực hiện băm dựa trên bình đẳng vật lý (==), có định nghĩa hợp lý cho tham chiếu (và các giá trị có thể thay đổi khác). Bạn phải cẩn thận với nó, mặc dù, như bình đẳng vật lý là một chút khôn lanh. Ví dụ: bạn không thể sử dụng địa chỉ thực của giá trị làm khóa băm - địa chỉ có thể thay đổi bất kỳ lúc nào do thu thập rác.