基於物理標識的替代Hashtbl.hash

我試圖派生描述結構化值的Graphviz文件。這是爲了診斷目的，所以我希望我的圖儘可能地反映內存中的實際結構。我使用的是下面值映射到Graphviz的頂點，所以我可以重用頂點時的值有兩個或兩個以上的入站參考：基於物理標識的替代Hashtbl.hash

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的文件表明，它是適合使用的時候都StateIdentity.equal = (=)當StateIdentity.equal = (==)，但我想確保哈希表訪問儘可能接近O（1），所以不希望Hashtbl.hash在每次查找中走過一個（在這種情況下可能很大）對象圖。

我知道ocaml的來回移動時的參考，但有一個O（1）代理參考身份提供ocaml的？

答案Hashtable of mutable variable in Ocaml表明沒有。

我厭惡的序列號附加到狀態，因爲這是診斷代碼，所以我讓做的任何錯誤都掩蓋其他錯誤的可能性。

來源

2012-10-24 Mike Samuel

「Hashtbl.hash的文檔表明，當StateIdentity.equal =（=）和StateIdentity.equal =（==）時它們都適用。」雖然不是這樣。當與物理平等相關聯時，「Hashtbl.hash」有很多衝突，意思是你使用它，你的散列表可能會退化成一系列結構相同，物理上不同的密鑰的長列表。 –

@PascalCuoq，很對。「合適的」我的意思是「保持替換和找到不變」，並不是指保持查找關鍵比較的數量不變。 –

如果您使用OCaml的<...>對象類型意義上的單詞「object」，則可以使用Oo.id爲每個實例獲取唯一的整數標識。否則，對於「是否有價值認同的一般代理」的答案是「否」。在這種情況下，我的建議是從Hashtbl.hash開始，評估它是否適合您的需要，並設計您自己的哈希函數。

您也可以玩Hashtbl.hash_param（見documentation）在散列期間打開值遍歷旋鈕。請注意，Hashtbl代碼使用鏈接列表來存儲相同哈希值的桶，因此具有大量哈希衝突將觸發線性搜索行爲。移動到使用二叉搜索樹進行衝突桶的其他實現可能會更好。但是，再次，你應該評估你的情況，然後才能轉向更復雜的（而且在「好例子」）解決方案中表現更差。

來源

2012-10-24 15:49:56 gasche

感謝您的指針。按照對象，我的意思是結構化的價值，而不是「class」的一個實例。 –

我發現它非常棘手使用物理平等做散列。你當然不能使用值的地址作爲你的哈希鍵，因爲（正如你所說），東西會被GC移動。一旦你有一個散列鍵，只要你的值是可變的，你似乎可以使用物理相等來進行比較。如果你的值不可變，OCaml並不能保證（==）的含義。實際上，如果OCaml編譯器或運行時期望（或相反），那麼相等（=）的不可變對象在理論上可以合併爲單個物理對象。

當我通過各種可能的工作，我通常最終把一個序列號到我的價值觀，當我需要一個唯一的ID。正如gasche所說，如果你的值是實際的OO風格的對象，你可以使用Oo.id。

來源

2012-10-24 15:59:54

和其他人一樣，我認爲獨一無二的ID是最佳選擇。

唯一ID不難安全生成。一種解決方法是使用所謂的私人記錄如下。它可以防止模塊的用戶複製ID字段：

 
module type Intf = 
sig 
    type t = private { 
    id : int; 
    foo : string; 
    } 

    val create_t : foo: string -> t 
end 

module Impl : Intf = 
struct 
    type t = { 
    id : int; 
    foo : string; 
    } 

    let create_id = 
    let n = ref 0 in 
    fun() -> 
     if !n = -1 then 
     failwith "Out of unique IDs" 
     else (
     incr n; 
     !n 
    ) 

    let create_t ~foo = { 
    id = create_id(); 
    foo 
    } 
end

來源

2012-10-24 17:02:13

我認爲你的'sig'缺少'val create_t：〜foo：string - > t' –

感謝您的修復。 –

感謝您的回答。 –

對不起，醜陋的黑客攻擊，但我前一段時間做這樣的事情。

有關的技巧是保證值將不會在內存中的表中插入後移動。有兩種情況可以在內存中移動值：從副本複製到主要堆和主要堆壓縮。這意味着當你在表中插入一個值時，它必須位於主堆中，並且在表上的兩個操作之間必須確保沒有發生壓縮。

檢查值是否在次堆中可以使用C函數is_young完成，如果是這種情況，可以使用Gc.minor（）強制將值遷移到主堆。

對於第二個問題，您可以完全禁用壓縮或重建壓縮表。禁用它可以使用

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

檢測到壓實發生可以通過在每ACCES比較受

(Gc.quick_stat()).Gc.compactions

通知返回的數字表做可以做到這一點，你必須在訪問前禁用壓實桌子。如果您禁用壓縮，則還應考慮更改分配策略以避免無限制的堆碎片。

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

如果你想要的東西在舊版本的OCaml的真醜（之前4.00）壓實保持值以相同的順序在內存中，這樣你就可以實現一組或地圖基於物理地址，而不必擔心。

來源

2012-10-24 21:00:43

我想我會在嘗試取決於這麼多實現細節的東西之前耗盡所有其他途徑，但感謝您解釋GC的相關詳細信息。 –

基於物理標識的替代Hashtbl.hash

回答

相關問題