की समय जटिलता मुझे आश्चर्य है कि क्या एरलांग ओटीपी dict मॉड्यूल को हैश तालिका के रूप में कार्यान्वित किया गया है और उस स्थिति में यह ऐसा प्रदर्शन देता है?erlang dict
औसत प्रकरण
Search: O(1 + n/k)
Insert: O(1)
Delete: O(1 + n/k)
सबसे खराब मामला
Search: O(n)
Insert: O(1)
Delete: O(n)
स्रोत: Wikipedia Hash Table
क्योंकि ब्रित मॉड्यूल को अंतर्निहित डेटा प्रकारों (टुपल्स और सूचियों) का उपयोग करके एर्लांग में स्वयं लागू किया गया है, और यह अनौपचारिक है, यानी, प्रत्येक "अपडेट" वास्तव में पिछले नियम के थोड़ा सा पुनर्लेखित नया संस्करण बनाता है, समय जटिलता लॉगरिदमिक से बेहतर कभी नहीं हो सकती है (कार्यान्वयन किसी प्रकार के पेड़ का उपयोग करना चाहिए), लेकिन विवरण कार्यान्वयन के साथ भिन्न हो सकते हैं।
वर्तमान कार्यान्वयन (जो कई वर्षों से आसपास रहा है) वास्तव में अच्छी तरह से स्केल नहीं करता है जब प्रविष्टियों की संख्या बड़ी हो जाती है। लेखक (रॉबर्ट विर्डिंग) हाल ही में 2-3 पेड़ जैसे अन्य वृक्ष कार्यान्वयन के साथ प्रयोग कर रहे हैं, और यह संभव है कि भविष्य के रिलीज में dict मॉड्यूल का डिफ़ॉल्ट कार्यान्वयन बदल दिया जाएगा। देखें http://erlang.org/pipermail/erlang-questions/2012-June/067311.html
यदि आप इस तरह की चीज़ में रूचि रखते हैं, तो आप शुद्ध कार्यात्मक डेटा संरचनाओं के बारे में और अधिक पढ़ना चाहेंगे। यह एक अच्छा प्रारंभिक बिंदु जैसा लगता है: http://en.wikipedia.org/wiki/Purely_functional (विशेष रूप से ओकासाकी की थीसिस का लिंक)।
ठीक है, एक छोटे से मेरी लीग यहाँ से बाहर। सबसे पहले, यह एक हैशटेबल है, लेकिन मुझे निष्पादन समय के बारे में निश्चित नहीं है।
dict मॉड्यूल (lib/stdlib/src/dict.erl) के लिए स्रोत को देखते हुए, दिखाता है:
%% We use the dynamic hashing techniques by Per-�ke Larsson as
%% described in "The Design and Implementation of Dynamic Hashing for
%% Sets and Tables in Icon" by Griswold and Townsend. Much of the
%% terminology comes from that paper as well.
है कि कागज के बारे में Googling प्रश्न में पीडीएफ के साथ लिंक की एक संख्या से पता चलता है, कि तुम कार्यान्वयन के तकनीकी विवरणों के लिए संदर्भित कर सकते हैं (साथ ही, स्रोत कोड में अधिक टिप्पणियां भी उपयोगी हो सकती हैं)
आशा है कि यह उस पर कुछ प्रकाश डालेगा!