जाओ डेटा स्ट्रक्चर शीट को धोखा देते हैं

कुछ कंपनियां ऑनलाइन लेखन कोड का साक्षात्कार करती हैं। गति के लिए ओलंपियाड समस्या को हल करना आवश्यक है। ऐसी परिस्थितियों में, डेटा संरचनाओं के कार्यान्वयन के विवरण को देखने का समय नहीं है - आपको तुरंत विचार का एहसास करने की आवश्यकता है। लेकिन एल्गोरिदम और डेटा संरचनाओं पर पाठ्यक्रम या तो छद्म कोड या C ++ में उदाहरण प्रदान करते हैं। समस्याओं के अधिक संदर्भ समाधान अक्सर C ++ में लिखे जाते हैं। एक साक्षात्कार की तैयारी करते हुए, मैंने पुस्तकालयों का एक खाका बनाया - एसटीएल कंटेनरों के एनालॉग्स, ताकि कीमती समय बर्बाद न करें।

चलो स्पष्ट के साथ शुरू करते हैं।

गतिशील निरंतर सरणी

एनालॉग std::vector ।
कई प्रोसेसर चक्रों के लगातार समय के लिए सूचकांक द्वारा एक तत्व तक पहुंचने का समर्थन करता है। आप क्षमता बढ़ा या घटा सकते हैं। यह बिल्ट-इन स्लाइस है:

 vector := []int{} 

आसानी से, बुनियादी अवधारणाओं को भाषा में बनाया गया है।

Ctek

std::stack एनालॉग std::stack ।

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

 // Push stack = append(stack, value) 

 // Pop // ,  len(stack) > 0 stack, value = a[:len(stack)-1], a[len(stack)-1] 

स्लाइस ऑपरेशन एक नई मेमोरी आवंटित नहीं करता है।

बारी

std::queue एनालॉग std::queue और std::deque ।

कतारें निरंतर समय में शुरू और अंत के लिए पुनर्प्राप्ति और इसके अलावा संचालन को लागू करती हैं। जो तत्व पहले रखा गया था (प्रथम-प्रथम, प्रथम-आउट - फीफो) को पहले कतार से हटा दिया जाता है। एक बफर चैनल एक रिंग बफर पर एक कतार है, आप इसका उपयोग तब कर सकते हैं जब पाठक और लेखक अलग-अलग गोरआउट होते हैं। लेकिन मानक पुस्तकालय में कोई अलग कतार कार्यान्वयन नहीं है। ज़बरदस्त लिस्ट में लाइब्रेरी https://github.com/gammazero/deque की सलाह दी गई है।

 import "github.com/gammazero/deque" 

चल रहे संचालन:

 func (q *Deque) PushBack(elem interface{}) func (q *Deque) PushFront(elem interface{}) func (q *Deque) PopBack() interface{} func (q *Deque) PopFront() interface{} func (q *Deque) Back() interface{} func (q *Deque) Front() interface{} func (q *Deque) At(i int) interface{} 

संदेह से जुड़ी सूची

std::list अनुरूप।
इसमें अपने स्वयं के डेटा के अलावा, अगले और पिछले सूची आइटम के लिंक वाले तत्व शामिल हैं। यह मानक पुस्तकालय में है:

 import "container/list" 

जैसा कि अपेक्षित था, यह सम्मिलन संचालन का समर्थन करता है (शुरुआत में, अंत में, तत्व से पहले और बाद में, जिस पर सूचक पारित हो जाता है) और विलोपन।

 func (l *List) PushBack(v interface{}) *Element func (l *List) PushFront(v interface{}) *Element func (l *List) InsertAfter(v interface{}, mark *Element) *Element func (l *List) InsertBefore(v interface{}, mark *Element) *Element func (l *List) Remove(e *Element) interface{} 

गो पुनरावृत्तियों के लिए विशिष्ट सिंटैक्स प्रदान नहीं करता है। इसलिए, अगला / पिछला तत्व एक पॉइंटर से किसी भी नोड में प्राप्त किया जा सकता है। सूची में किसी आइटम को जोड़ने / हटाने के बाद ये तरीके खराब नहीं होते हैं, आश्चर्य के बिना।

 func (e *Element) Next() *Element func (e *Element) Prev() *Element 

प्राथमिकता कतार

एनालॉग std::priority_queue
आपको किसी भी क्रम में आइटम को स्टैक करने की अनुमति देता है, और किसी भी समय शेष की सर्वोच्च प्राथमिकता प्राप्त करता है। इसका उपयोग, उदाहरण के लिए, एक न्यूनतम फैले हुए पेड़ के निर्माण के लिए एल्गोरिथ्म में किया जाता है, जब अगले चरण में एल्गोरिथ्म सबसे छोटे छोरों का चयन करता है, जो पहले से ही एक छोर पर आच्छादित कोने में शुरू होते हैं।

मानक लाइब्रेरी में एक एडेप्टर होता है जो किसी भी प्रकार के कंटेनर को sort.Interface (जो क्रमबद्ध करता है। sort.Interface ) को प्राथमिकता कतार में sort.Interface ।

 import "container/heap" 

यह एक क्लासिक बाइनरी हीप है । हे (लॉग एन) में सम्मिलन और विलोपन।

 func Pop(h Interface) interface{} func Push(h Interface, x interface{}) func Remove(h Interface, i int) interface{} 

हैश टेबल

यह एक शब्दकोश और एक सहयोगी सरणी है।

एनालॉग std::unordered_map ।

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

 unorderedMap := make(map[string]int) 

मेक (मानचित्र) का परिणाम एक सूचक है, और इसके काम करने का तरीका मानक कंटेनरों से थोड़ा अलग है:

 //  : _, ok := unorderedMap["route"] //  : delete(unorderedMap, "route") //  : n := len(unorderedMap) 

"रनटाइम / मैप", std :: unordered_map के विपरीत, प्रोग्रामर का ध्यान रखता है - पुनरावृति के दौरान मानों को हटाना सुरक्षित है।

बहुत

एनालॉग std::unordered_set ।
लगभग एक हैश तालिका के समान है, लेकिन मूल्य को बचाने के बिना।
यदि हमें केवल एक त्वरित प्रविष्टि की आवश्यकता है, तो हम फिर से अंतर्निहित मानचित्र का उपयोग कर सकते हैं। यह इंगित करने के लिए कि केवल कुंजी महत्वपूर्ण है, केवल खाली मान निर्दिष्ट करना आवश्यक है।

 var m = make(map[string]struct{}) m["!"] = struct{}{} _, ok := m["!"] // true 

लेकिन यह कार्यान्वयन जटिल ऑपरेटरों का समर्थन नहीं करता है। विलय करने, अंतर करने के लिए, बॉक्स से अंतर, आपको तीसरे पक्ष के पुस्तकालयों की आवश्यकता है। सबसे अधिक उपयोग किया जाता है, सितारों की संख्या को देखते हुए: https://github.com/deckarep/golang-set

 import "github.com/deckarep/golang-set" 

एपीआई का सबसे जरूरी हिस्सा:

 Add(i interface{}) bool Remove(i interface{}) Cardinality() int // len() Contains(i ...interface{}) bool IsSubset(other Set) bool Intersect(other Set) Set Union(other Set) Set Difference(other Set) Set SymmetricDifference(other Set) Set 

इंट सेट करें

मानक पुस्तकालय के प्रयोगात्मक भाग में एक अनुकूलित सेट इंट है जो हर बिट को बचाता है।

 import "golang.org/x/tools/container/intsets" 

यह यूनियन, चौराहे, सेटों के अंतर का भी समर्थन करता है।

बाइनरी सर्च ट्री

एनालॉग्स std::set और std::map ।
यह हैश टेबल के नौसिखिए बुरे एनालॉग की तरह लग सकता है:
घटनाओं को जोड़ने, हटाने और जाँच का भी समर्थन करते हैं, लेकिन O (लॉग एन) से परे।
लेकिन पेड़ स्टोर नोड्स को कुंजी द्वारा क्रमबद्ध करते हैं।

मानक गो लाइब्रेरी में कोई पेड़ नहीं हैं, एवीएल, रेड-ब्लैक और बी-ट्री युक्त भंडार का व्यापक रूप से उपयोग किया जाता है।

 import "github.com/emirpasic/gods/trees/avltree" 

आमतौर पर इस्तेमाल की जाने वाली एपीआई विधियाँ:

 func (tree *Tree) Get(key interface{}) (value interface{}, found bool) func (tree *Tree) Put(key interface{}, value interface{}) func (tree *Tree) Remove(key interface{}) func (tree *Tree) Size() int func (tree *Tree) Keys() []interface{} func (tree *Tree) Values() []interface{} func (tree *Tree) Left() *Node func (tree *Tree) Right() *Node 

दो विशेष रूप से महत्वपूर्ण वृक्ष विधियाँ हैं:

 func (tree *Tree) Ceiling(key interface{}) (ceiling *Node, found bool) 

कुंजी की तुलना में बड़ी से छोटी मौजूदा वस्तु लौटाता है।

 func (tree *Tree) Floor(key interface{}) (floor *Node, found bool) 

एक कुंजी से कम का सबसे बड़ा मौजूदा तत्व देता है।

इसके लिए कार्य अपेक्षाकृत अक्सर साक्षात्कारों में पाए जाते हैं। वास्तविक जीवन में इसका उपयोग डेटाबेस इंडेक्स में किया जाता है:

 select x from table where x <= $1 limit 1; 

यदि कोई इंडेक्स है, तो यह बी-ट्री में बॉर्डर के लिए 1 सर्च के लिए, ओ (लॉग एन) के लिए काम करेगा।

ब्लूम फ़िल्टर

लेकिन stl में यह डेटा संरचना नहीं है।
एक हैश तालिका की तरह, यह आपको यह जांचने की अनुमति देता है कि कोई तत्व सेट से संबंधित है या नहीं। लेकिन फ़िल्टर जोड़ते समय कुंजियों को संग्रहीत नहीं करता है, और निरंतर मात्रा में मेमोरी लेता है। झूठी सकारात्मक प्रतिक्रिया प्राप्त करना संभव है (सेट में कोई तत्व नहीं है, लेकिन डेटा संरचना रिपोर्ट करती है कि यह है), लेकिन गलत नकारात्मक नहीं। यह लगभग सभी गैर-मौजूदा कुंजियों को जल्दी से काटने के लिए एक फिल्टर के रूप में उपयोग किया जाता है, अधिक महंगा सत्यापन को सहेजना, उदाहरण के लिए, डिस्क से पढ़ना या डेटाबेस से अनुरोध करना।
एक तृतीय-पक्ष पुस्तकालय है: https://github.com/willf/bloom

 import "github.com/willf/bloom" 

ऐसा अक्सर उपयोग नहीं किया जाता है, आप एपीआई पर झांक सकते हैं।

HyperLogLog

मानक C ++ लाइब्रेरी में ऐसी कोई चीज नहीं है।

संभाव्य डेटा संरचना। एक छोटी सी त्रुटि (% 0.4%) के साथ, यह बिना चाबी के भंडारण के अद्वितीय तत्वों की संख्या पर विचार करता है। यह विशाल मेमोरी बचत प्रदान करता है। यदि कार्य आगंतुकों या अनुरोधों की संख्या की शीघ्र गणना करना है - हाइपरलॉग आदर्श है।

अब इसके लिए सबसे लोकप्रिय पुस्तकालय है।

https://github.com/axiomhq/hyperloglog

 import "github.com/axiomhq/hyperloglog" 

छंटाई

एनालॉग्स std::sort एंड std::stable_sort ।
उपभोक्ता दृष्टिकोण से, केवल 2 मौलिक रूप से भिन्न प्रकार हैं:
स्थिर (समान तत्वों के क्रम को न बदलें [[4, 0], [1, 2], [1, 1], [5, 6]] -> [[1, 2], [1, 1], [4 , 0], [5, 6]])
और स्थिर नहीं है, शेष क्षेत्रों की स्थिरता की गारंटी नहीं है।
दोनों मानक पुस्तकालय में हैं:

 func Sort(data Interface) 

यह एक Hoar क्विकॉर्ट कार्यान्वयन है, अस्थिर है। लेकिन लंबाई के वर्गों के लिए <12 ढेर छँटाई का उपयोग अनुकूलन के रूप में किया जाता है।

 func Stable(data Interface) 

अंदर, यह एक मर्ज प्रकार है, लेकिन दक्षता के लिए, जब पुनरावर्ती एल्गोरिदम 20 से कम तत्वों के ब्लॉक तक पहुंचता है, तो सम्मिलन प्रकार का उपयोग किया जाता है।

ये ओ (एन लॉग एन) के लिए काम करने वाले क्लासिक एल्गोरिदम हैं।

यदि आप इसे पढ़ते हैं, तो बधाई। विशिष्ट API को जानने से परीक्षण समस्याओं को हल करने में मदद मिलती है। (यदि आपने कुछ के साथ काम किया है और सबसे अच्छा विकल्प जानते हैं - टिप्पणियों में लिखें।