ओकैम हैशटेबल्स में समानता

क्या ओकैम में हैशटेबल्स हैं जो = के बजाय चाबियों की समानता के परीक्षण के लिए उपयोग करते हैं? उदाहरण के लिए:ओकैम हैशटेबल्स में समानता

# type foo = A of int;; 
# let a = A(1);; 
# let b = A(1);; 
# a == b;; 
- : bool = false 
# a = b;; 
- : bool = true 
# let h = Hashtbl.create 8;; 
# Hashtbl.add h a 1;; 
# Hashtbl.add h b 2;; 
# Hashtbl.find h a;; 
- : int = 2 
# Hashtbl.find h b;; 
- : int = 2

मैं एक hashtable कि a और b बीच भेद कर सकते करना चाहते हैं। क्या यह संभव है?

स्रोत

2012-01-23 pbp

इस प्रकार की हैश तुलना थोड़ी कम नाजुक है जब आपके उदाहरण में अपरिवर्तनीय मूल्यों के साथ प्रयोग किया जाता है। दस्तावेजों का कहना है कि (==) का परिणाम उस मामले में निर्भर कार्यान्वयन है: [तुलनात्मक ** मॉड्यूल के तहत पारदर्शी मॉड्यूल **] देखें (http://caml.inria.fr/pub/docs/manual-ocaml/libref/ Pervasives.html)। सिद्धांत रूप में संकलक या रनटाइम किसी भी दो बराबर अपरिवर्तनीय मानों को शारीरिक रूप से बराबर होने का कारण बन सकता है। –

@ जेफरीस्कोफिल्ड कंपाइलर या रनटाइम उन मानों का भी कारण बन सकता है जिन्हें आप अलग-अलग होने के लिए शारीरिक रूप से बराबर होने की उम्मीद करेंगे, और यह सैद्धांतिक नहीं है: 'परीक्षण x = let t = Array.make x x x == t में 0 x (0) ;; परीक्षण 1.0; 'गणना' झूठी '। कैमल के लिए बहु-थ्रेड जीसी जो केवल कागज पर मौजूद है, अपरिवर्तनीय मानों को भी डुप्लिकेट कर सकता है। –

धन्यवाद, ये बहुत ही रोचक उदाहरण हैं, हालांकि मुझे लगता है कि ओपी सिक्का के दूसरी तरफ से अधिक चिंतित है। आप अनूठे भौतिक पहचान (ए! = बी) वाले अपरिवर्तनीय मूल्यों पर निर्भर नहीं हो सकते हैं जब तक कि वे बराबर न हों (एक <> बी)। सामान्य समाधान (या, मैंने जो उपयोग किया है) आपके मूल्यों में एक अद्वितीय पहचानकर्ता रखना है। यह निश्चित रूप से हैशिंग के साथ भी मदद करता है। –

आप कस्टम hashtables उपयोग कर सकते हैं:

module H = Hashtbl.Make(struct 
    type t = foo 
    let equal = (==) 
    let hash = Hashtbl.hash 
end)

और फिर अपने कोड में Hashtbl की H का उपयोग करने के बजाय।

स्रोत

2012-01-23 14:32:04 Thomas

जब मैं ओकैम के टप्लूप में पेस्ट करता हूं, मुझे एक वाक्यविन्यास त्रुटि मिलती है (अंतिम समापन कोष्ठक रेखांकित किया जाता है)। – pbp

'stuct' कीवर्ड पर समापन' समाप्ति 'खो रहा है। – nlucaroni

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

यदि आप कभी-कभी मूल्य बदलने की कुंजी स्वीकार कर सकते हैं (और इसलिए हैश-टेबल से पुनर्प्राप्त करना असंभव है, क्योंकि बाइंडिंग गलत बाल्टी में है), तो आप निम्नलिखित निम्न-स्तरीय फ़ंक्शन का उपयोग कर सकते हैं

external address_of_value: 'a -> int = "address_of_value"

के रूप में सी में लागू किया: हैश के रूप में

#include "caml/mlvalues.h" 

value address_of_value(value v) 
{ 
    return (Val_long(((unsigned long)v)/sizeof(long))); 
}

फिर आप का प्रयोग करेंगे:

module H = Hashtbl.Make(struct 
    type t = foo 
    let equal = (==) 
    let hash = address_of_value 
end);;

स्रोत

2012-01-23 16:22:34

तथ्य यह है कि समान बाल्टी के बराबर (=) मान हैश वास्तविक समस्या है। यदि आप अपनी हैश तालिका में कुछ बराबर (लेकिन गैर भौतिक रूप से बराबर) मान डालना चाहते हैं तो आप एक बहुत ही खराब प्रदर्शन देखेंगे जबतक कि आप एक अलग हैश फ़ंक्शन का उपयोग न करें। Http: // stackoverflow देखें।कॉम/प्रश्न/675750 9/स्टैक ओवरफ्लो-साथ-विशेष-हैशटब्लू-थ्रू-हैशटब्लू-मेक –

पुराने ओकैम संस्करणों में (मुझे नहीं पता कि यह हाल ही में बदला गया है), केवल एक मामूली जीसी या एक कॉम्पैक्शन ब्लॉक को स्थानांतरित कर सकता है, इसलिए हैशिंग यदि आप कॉम्पैक्शन बंद कर देते हैं और हैशिंग से पहले एक मामूली जीसी को मजबूर कर देते हैं तो पॉइंटर सुरक्षित था। ऐसा नहीं है कि मैं उस कार्यक्रम में अनुशंसा करता हूं जिसे आप बनाए रखना चाहते हैं। – Gilles

@ गिल्स यह अभी भी मामला है। मैंने लगभग इस जानकारी को इंगित किया, लेकिन फिर परिलक्षित किया कि मैं शायद ओपी की तुलना में अधिक तकनीकी हो रहा था। कुछ जीसी पिनिंग करते हैं, लेकिन यह इस समस्या के लिए गलत उपकरण की तरह लगता है। (==) - हैशटेबल को मामूली वस्तुओं को प्रमुख लोगों से अलग रखकर और केवल आवश्यकतानुसार इसे पुनः दबाकर कार्यान्वित किया जा सकता है। यह अभी भी आवश्यक होगा या तो प्रत्येक बार एक बार होने पर या फिर हर बार रिहाश करने के लिए आवश्यक होगा। –

ओकैम हैशटेबल्स में समानता

उत्तर

संबंधित मुद्दे