Hashtbl.hash

Question

पर भौतिक पहचान आधारित विकल्प मैं एक संरचित मूल्य का वर्णन करने वाली ग्राफ़विज़ फ़ाइल प्राप्त करने का प्रयास कर रहा हूं। यह नैदानिक ​​उद्देश्यों के लिए है, इसलिए मैं चाहता हूं कि मेरा ग्राफ यथासंभव यथासंभव स्मृति में वास्तविक संरचना को दर्पण करे। मैं Graphviz कोने करने के लिए मान मैप करने के लिए इतना है कि मैं एक शीर्ष जब एक मूल्य के दो या अधिक भीतर का संदर्भ है पुन: उपयोग कर सकते हैं नीचे उपयोग कर रहा हूँ:

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 = (==) लेकिन मैं यह सुनिश्चित करना चाहता हूं कि हैश तालिका का उपयोग संभवतः ओ (1) के करीब है, इसलिए Hashtbl.hash प्रत्येक लुकअप पर ऑब्जेक्ट ग्राफ़ (इस मामले में संभावित रूप से बड़ा) नहीं चल रहा है।

मुझे पता है कि ओकम्ल चाल के आसपास संदर्भ हैं, लेकिन क्या ओकैम में संदर्भ संदर्भ के लिए ओ (1) प्रॉक्सी है?

Hashtable of mutable variable in Ocaml का उत्तर नहीं बताता है।

मैं राज्यों को सीरियल नंबर संलग्न करने के लिए नाराज हूं, क्योंकि यह नैदानिक ​​कोड है इसलिए कोई भी त्रुटि जो मैं कर रहा हूं जिसमें अन्य बग मास्क करने की क्षमता है।

Answer 1

यदि आप ओकैमल के <...> ऑब्जेक्ट प्रकारों के अर्थ में "ऑब्जेक्ट" शब्द का उपयोग कर रहे हैं, तो आप प्रत्येक उदाहरण के लिए एक अद्वितीय पूर्णांक पहचान प्राप्त करने के लिए Oo.id का उपयोग कर सकते हैं। अन्यथा "मान पहचान के लिए एक सामान्य प्रॉक्सी है" का जवाब "नहीं" है। इस मामले में मेरी सलाह Hashtbl.hash से शुरू होगी, यह मूल्यांकन करें कि यह आपकी ज़रूरत के अनुरूप है या नहीं, और अन्यथा अपने स्वयं के हैशिंग फ़ंक्शन को डिज़ाइन करें।

हैशिंग के दौरान मूल्य ट्रैवर्सल पर घुंडी करने के लिए आप Hashtbl.hash_param (documentation देखें) के साथ भी खेल सकते हैं। ध्यान दें कि हैशब्लबल कोड समान-हैश मानों की बाल्टी के लिए लिंक्ड सूचियों का उपयोग करता है, इसलिए बहुत सारे हैश टकराव होने से रैखिक खोज व्यवहार ट्रिगर होगा। संघर्ष बाल्टी के लिए बाइनरी खोज पेड़ों का उपयोग करके अन्य कार्यान्वयन में जाना बेहतर हो सकता है। लेकिन फिर, आपको अधिक जटिल (और "अच्छे मामले") समाधानों में खराब प्रदर्शन के साथ जाने से पहले अपनी स्थिति का मूल्यांकन करना चाहिए।

Answer 2

मुझे हैशिंग करने के लिए शारीरिक समानता का उपयोग करना बहुत मुश्किल लगता है। आप निश्चित रूप से मूल्य के पते की तरह कुछ हैश की कुंजी के रूप में उपयोग नहीं कर सकते हैं, क्योंकि (जैसा कि आप कहते हैं) चीजें जीसी द्वारा घूमती हैं। एक बार आपके पास हैश कुंजी हो जाने पर, ऐसा लगता है कि जब तक आपके मान म्यूटेबल नहीं होते हैं तब तक आप तुलना करने के लिए भौतिक समानता का उपयोग कर सकते हैं। यदि आपके मान म्यूटेबल नहीं हैं, तो ओकैमल (==) के अर्थ के बारे में ज्यादा गारंटी नहीं देता है। व्यावहारिक शब्दों में, अपरिवर्तनीय ऑब्जेक्ट्स जो बराबर (=) हैं, सैद्धांतिक रूप से एक भौतिक वस्तु में विलय किया जा सकता है यदि ओकैमल कंपाइलर या रनटाइम चाहता है (या इसके विपरीत)।

जब मैं विभिन्न संभावनाओं के माध्यम से काम करता हूं, तो मुझे आमतौर पर एक अद्वितीय आईडी की आवश्यकता होने पर अनुक्रम संख्या मेरे मूल्यों में डाल देती है। जैसा कि गैसचे कहते हैं, यदि आप अपने मूल्य वास्तविक ओओ-स्टाइल ऑब्जेक्ट्स हैं तो आप Oo.id का उपयोग कर सकते हैं।

Answer 3

दूसरों की तरह, मुझे लगता है कि अद्वितीय आईडी जाने का तरीका हैं।

अद्वितीय आईडी सुरक्षित रूप से उत्पन्न करना मुश्किल नहीं है। एक समाधान निम्नानुसार एक तथाकथित निजी रिकॉर्ड का उपयोग करना है। यह आईडी फील्ड को से मॉड्यूल के उपयोगकर्ताओं पर रोक:

 
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 

Answer 4

बदसूरत हैक के लिए

क्षमा करें, लेकिन मैं ऐसा ही कुछ कुछ समय पहले बनाया है।

इस बारे में चाल यह सुनिश्चित करना है कि तालिका में डालने के बाद मान स्मृति में स्थानांतरित नहीं किया जाएगा।ऐसी दो स्थितियां हैं जो स्मृति में मूल्यों को स्थानांतरित कर सकती हैं: नाबालिग से प्रमुख ढेर और प्रमुख ढेर की गणना में कॉपी करें। इसका मतलब है कि जब आप तालिका में कोई मान डालते हैं, तो यह मुख्य ढेर में होना चाहिए और तालिका पर दो संचालन के बीच होना चाहिए, आपको यह सुनिश्चित करना होगा कि कोई भी compaction नहीं हुआ।

यह जांचना कि मामूली ढेर में मूल्य सी फ़ंक्शन is_young का उपयोग करके किया जा सकता है, यदि यह मामला है, तो आप Gc.minor() का उपयोग करके प्रमुख ढेर में माइग्रेट करने के लिए मूल्य को मजबूर कर सकते हैं।

दूसरी समस्या के लिए, आप या तो संकलन पूरी तरह से निष्क्रिय कर सकते हैं या तालिकाओं पर तालिका को पुनर्निर्माण कर सकते हैं। उसे अक्षम करना

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

का उपयोग कर पता लगा रहा है कि एक संघनन हुआ तालिका संख्या से

(Gc.quick_stat()).Gc.compactions 

सूचना लौटे करने के लिए प्रत्येक acces में तुलना करके किया जा सकता है किया जा सकता है आप तक पहुँचने से पहले संघनन को निष्क्रिय किया जाना चाहिए कि टेबल। यदि आप कॉम्पैक्शन अक्षम करते हैं तो आपको ढेर के असंतुलित विखंडन से बचने के लिए आवंटन नीति को बदलने पर भी विचार करना चाहिए।

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

आप वास्तव में कुछ OCaml के पुराने संस्करणों में बदसूरत चाहते हैं (से पहले 4.00) संघनन मूल्य एक ही क्रम में स्मृति में रखा है ताकि आप एक सेट को लागू कर सकता है या चिंता किए बिना आधारित भौतिक पता नक्शे पर।