डेटा की एल्गोरिदमिक जटिलता। हैशटेबल

Question

मैं एक ऐसा फ़ंक्शन लिखने का प्रयास कर रहा हूं जो हैश का उपयोग करता है (ए * के कार्यान्वयन के लिए)।

थोड़ा सा शोध करने के बाद, मैंने पाया है कि डिफैक्टो मानक Data.Map है।

हालांकि, जब API दस्तावेज़ पढ़ने, मैंने पाया कि: O(log n). Find the value at a key.

https://downloads.haskell.org/~ghc/6.12.2/docs/html/libraries/containers-0.3.0.0/Data-Map.html

वास्तव में प्रलेखन आम तौर पर बड़ी हे बार काफी एक मानक हैश की हे (1) से हीन पता चलता है।

तो मुझे Data.HashTable मिला। https://hackage.haskell.org/package/base-4.2.0.2/docs/Data-HashTable.html यह प्रलेखन सीधे बड़े ओ का उल्लेख नहीं करता है, जिससे मुझे विश्वास होता है कि यह शायद मेरी अपेक्षाओं को पूरा करता है।

मेरे पास कई प्रश्न हैं: 1) क्या यह सही है? ओ है (lookupInDataHashTable) = ओ (1)? 2) मैं कभी भी Data.Map का उपयोग अपनी अक्षमता के बिना क्यों करना चाहूंगा? 3) क्या मेरी डेटा संरचना आवश्यकताओं के लिए कोई बेहतर लाइब्रेरी है?

Answer 1

मैं कभी भी डेटा का उपयोग क्यों करना चाहूंगा। मैप ने इसकी अक्षमता दी?

यह कुशल नहीं हो सकता है, लेकिन यह एक Ord उदाहरण के साथ कुंजी किसी भी प्रकार का समर्थन करता है, यहां तक ​​कि उन एक पूर्णांक के लिए टुकड़ों में बांटा नहीं जा सकता है।

क्या ओ (lookupInDataHashTable) = O (1) है?

आम तौर पर हां। "LookupInDataHashTable" का वर्कफ़्लो और बड़े-ओ नोटेशन में corressponding प्रदर्शन है:

1. कुंजी हैश करें। पूर्णांक के लिए: हे (1), स्ट्रिंग के लिए: हे (स्ट्रिंग की लंबाई)
2. हैश के साथ प्रवेश एक IOArray, सभी कुंजी-मान जोड़ों जो एक ही हैश है युक्त एक सूची प्राप्त। ओ (1)
3. सूची में कुंजी देखें। ओ (सूची की लंबाई)

तो जब तक आपके पास चाबियों के रूप में बहुत लंबे तार नहीं होते हैं, तो लुकअप फ़ंक्शन gurantees O (1) प्रदर्शन।

क्या मेरी डेटा संरचना आवश्यकताओं के लिए कोई बेहतर लाइब्रेरी है?

यह आपकी कुंजी के प्रकार पर निर्भर करता है। अलग-अलग पूर्णांक के लिए Data.IntMap बेस्ट, अन्य हैश-सक्षम प्रकारों के लिए डेटा। हैशैप सभ्य प्रदर्शन दिखाता है, अन्यथा आपके पास Data.Map के अलावा कोई विकल्प नहीं है।

Answer 2

Data.HashTable को हटा दिया गया है और आपको इसे वर्तमान base पर नहीं मिलेगा।

इसे हटा दिया गया था क्योंकि यह hashtables की तुलना में खराब प्रदर्शन करता था।

हालांकि, hashtables और Data.HashTable दोनों परिवर्तनशील कार्यान्वयन, जबकि Data.Map और Data.HashMap अपरिवर्तनीय हैं।

हास्केल में उत्परिवर्तनीय हैशैप्स अन्य भाषाओं में सरणी-बाल्टी या खुले पते के समाधान के समान हैं। अपरिवर्तनीय नक्शे पेड़ या कोशिशों पर आधारित होते हैं। आम तौर पर, अपरिवर्तनीय सहयोगी कंटेनरों को ओ (1) संशोधन के साथ लागू नहीं किया जा सकता है।

तो अपरिवर्तनीय मानचित्रों का उपयोग क्यों करें?

सबसे पहले, एपीआई हास्केल में अधिक सुविधाजनक है। हम शुद्ध कार्यों में उपयोग करने योग्य मानचित्रों का उपयोग नहीं कर सकते हैं, केवल आईओ या एसटी कार्यों में।

दूसरा, अपरिवर्तनीय नक्शे धागे के बीच सुरक्षित रूप से साझा किया जा सकता है, जो अक्सर एक महत्वपूर्ण विशेषता है।

तीसरा, व्यावहारिक रूप से, परिवर्तनीय और अपरिवर्तनीय मानचित्रों के बीच प्रदर्शन अंतर महत्वहीन हो सकता है, i। ई। यह समग्र कार्यक्रम प्रदर्शन पर ध्यान केंद्रित नहीं करता है। ओ (लॉग एन) भी उपलब्ध स्मृति से घिरा हुआ है, इसलिए हमें ओ (1) की तुलना में शानदार असम्पीटिक मतभेद नहीं मिलते हैं। विशेष रूप से, Data.HashMap 16-शाखा वाली त्रिभुज का उपयोग करता है, इसलिए त्रिभुज गहराई वास्तविक रूप से 6 या 7 से अधिक नहीं हो सकती है।

चौथा, अपरिवर्तनीय मानचित्र उन कारणों से केवल तेज़ हो सकता है जिन्हें मैं पूरी तरह से समझ नहीं पा रहा हूं (अधिक अनुकूलित पुस्तकालय? जीएचसी से बेहतर अनुकूलन?); मैंने से परिवर्तनीय मानचित्रों के साथ Data.HashMap को प्रतिस्थापित करने के लिए दो बार कोशिश की है, लेकिन प्रदर्शन हमेशा बाद में थोड़ा खराब था।