स्विफ्ट में सही डेटा संरचना का चयन

फिर से नमस्कार। सप्ताहांत के लिए जाने से पहले हम आपके साथ सामग्री का एक अनुवाद साझा करना चाहते हैं जो विशेष रूप से बुनियादी पाठ्यक्रम "iOS- डेवलपर" के लिए तैयार किया गया था।

---

किसी दिए गए मानों का प्रतिनिधित्व करने के लिए किस डेटा संरचना का उपयोग करना तय करना अक्सर लगता है की तुलना में अधिक कठिन है। चूंकि प्रत्येक प्रकार की डेटा संरचना एक निश्चित संख्या में उपयोग के मामलों के लिए अनुकूलित है, इसलिए प्रत्येक डेटा सेट के लिए सही फिट चुनना अक्सर हमारे कोड के प्रदर्शन पर बड़ा प्रभाव डाल सकता है।

मानक स्विफ्ट पुस्तकालय तीन मुख्य डेटा संरचनाओं के साथ आता है - Array , Dictionary और Set , जिनमें से प्रत्येक के पास अनुकूलन, प्लसस और मिन्यूज़ का अपना सेट है। आइए उनकी कुछ विशेषताओं को देखें, साथ ही ऐसे मामलों को भी देखें जहां हमें अपने उद्देश्यों के लिए सही डेटा संरचना खोजने के लिए मानक पुस्तकालय से आगे जाने की आवश्यकता हो सकती है।

लकीर का फकीर होना

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

उदाहरण के लिए, यहां हम एक आरेखण में एक Canvas पर रखे आकृतियों के संग्रह को संग्रहीत करने के लिए एक सरणी का उपयोग करते हैं। फिर, जब हमें कैनवास को एक छवि में प्रस्तुत करने की आवश्यकता होती है, तो हम DrawingContext का उपयोग करके प्रत्येक तत्व को खींचने के लिए सरणी के माध्यम से DrawingContext - इस प्रकार है:

 struct Canvas { var shapes: [Shape] func render() -> Image { let context = DrawingContext() shapes.forEach(context.draw) return context.makeImage() } } 

जब यह हमारे सभी आकृतियों के अनुक्रमिक प्रतिपादन की बात आती है, जैसा कि हमने ऊपर किया था, तो सरणी पूरी तरह से फिट बैठती है। Arrays न केवल अपने तत्वों को बहुत कुशल तरीके से संग्रहीत करता है, उनके पास एक गारंटीकृत सॉर्टिंग ऑर्डर भी होता है, जो बिना किसी अतिरिक्त कार्य के एक पूर्वानुमानित रेंडरिंग ऑर्डर प्रदान करता है।

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

 extension Canvas { mutating func remove(_ shape: Shape) { guard let index = shapes.firstIndex(of: shape) else { return } shapes.remove(at: index) } } 

सबसे पहले, उपरोक्त कोड इतनी समस्याग्रस्त नहीं लग सकता है, लेकिन यह किसी भी कैनवास के लिए एक प्रदर्शन अड़चन बन सकता है जिसमें बड़ी संख्या में आकृतियाँ होती हैं, क्योंकि समय की जटिलता के संदर्भ में firstIndex रैखिक (O (N)) है।

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

गति निर्धारित करता है

इसके बजाय, आइए देखें कि हम Canvas को अपने अंतर्निहित डेटा संरचना को बदलकर स्वयं को अनुकूलित कर सकते हैं या नहीं। उपरोक्त समस्या को ध्यान में रखते हुए, हमारे प्रारंभिक विचारों में से एक Array बजाय Set (सेट) का उपयोग करना हो सकता है। जैसा कि हमने पहले ही स्विफ्ट में सेट्स की शक्ति पर चर्चा की, सरणियों के सेटों के महत्वपूर्ण लाभों में से एक यह है कि डालने और हटाने दोनों को हमेशा एक स्थिर (ओ (1)) समय में किया जा सकता है, चूंकि आइटम हैश मूल्य द्वारा संग्रहीत किए जाते हैं, सूचकांक द्वारा नहीं।

सेट का उपयोग करने के लिए Canvas को अपडेट करके, हम निम्नलिखित प्राप्त करते हैं:

 struct Canvas { var shapes: Set<Shape> func render() -> Image { let context = DrawingContext() shapes.forEach(context.draw) return context.makeImage() } mutating func remove(_ shape: Shape) { shapes.remove(shape) } } 

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

अनुक्रमणिका अनुक्रमणिका

चलो प्रयोग करना जारी रखें। अब देखते हैं कि क्या हम Dictionary Canvas को ऑप्टिमाइज़ कर सकते हैं, जो हमें इसकी आईडी के आधार पर किसी भी आकृति के सूचकांक को खोजने की अनुमति देता है। हम अपनी shapes सरणी के लिए पहुँच स्तर को private बदलकर शुरू करेंगे ताकि हम नए add पद्धति का उपयोग करके तत्वों के सम्मिलन को नियंत्रित कर सकें। और हर बार एक नया आंकड़ा जोड़ा जाता है, हम इसके सूचकांक को भी अपने शब्दकोश में जोड़ते हैं:

 struct Canvas { private var shapes = [Shape]() private var indexes = [Shape.ID : Int]() func render() -> Image { let context = DrawingContext() shapes.forEach(context.draw) return context.makeImage() } mutating func add(_ shape: Shape) { let index = shapes.count indexes[shape.id] = index shapes.append(shape) } } 

चूंकि अब हम हमेशा यह जानते हैं कि किसी दिए गए आंकड़े को किस सूचकांक में संग्रहीत किया जाता है, हम एक सेट का उपयोग करते समय तेजी से निरंतर समय में विलोपन कर सकते हैं:

 extension Canvas { mutating func remove(_ shape: Shape) { guard let index = indexes[shape.id] else { return } shapes.remove(at: index) indexes[shape.id] = nil } } 

हालांकि, हमारे नए Canvas कार्यान्वयन में एक बहुत गंभीर बग है। हर बार जब हम किसी आकृति को हटाते हैं, तो हम वास्तव में उन सभी अनुक्रमितों को अमान्य कर देते हैं, जो हमारे द्वारा हटाए गए से अधिक हैं - क्योंकि इनमें से प्रत्येक तत्व सरणी की शुरुआत में एक कदम आगे बढ़ जाएगा। हम प्रत्येक विलोपन के बाद इन सूचकांकों को समायोजित करके इस समस्या को हल कर सकते हैं, लेकिन यह फिर से हमें ओ (एन) क्षेत्र में वापस लाएगा, जिसे हमने शुरुआत से ही बचने की कोशिश की थी।

हमारे नवीनतम कार्यान्वयन में इसके गुण हैं। सामान्य तौर पर, दो डेटा संरचनाओं के संयोजन का उपयोग करना ऐसी स्थितियों में एक महान विचार हो सकता है, क्योंकि हम अक्सर एक डेटा संरचना की ताकत का उपयोग दूसरे की कमियों की भरपाई करने के लिए कर सकते हैं, और इसके विपरीत।

तो, आइए फिर से एक अलग संयोजन के साथ प्रयास करें, लेकिन इस बार आइए अपनी वास्तविक आवश्यकताओं पर विचार करके शुरू करें :

• हमें निरंतर समय की जटिलता के लिए आवेषण और विलोपन दोनों की आवश्यकता है, और इसका आधार सूचकांक ज्ञात किए बिना आंकड़ा हटाना संभव होना चाहिए।
• स्थिर रेंडरिंग ऑर्डर बनाए रखने में सक्षम होने के लिए हमें एक गारंटीकृत सॉर्टिंग ऑर्डर की आवश्यकता होती है।

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

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

लिंक की गई सूची बनाएं

आइए एक List संरचना की घोषणा करके शुरू करें जो हमारी सूची में पहले और अंतिम नोड को ट्रैक करेगी। हम इन दोनों गुणों को डेटा स्थिरता सुनिश्चित करने के लिए अपने प्रकार के बाहर केवल-पढ़ने के लिए बनाएंगे:

 struct List<Value> { private(set) var firstNode: Node? private(set) var lastNode: Node? } 

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

 extension List { class Node { var value: Value fileprivate(set) weak var previous: Node? fileprivate(set) var next: Node? init(value: Value) { self.value = value } } } 

पिछली संपत्ति को कमजोर बनाने का कारण यह है कि यदि हम दोनों दिशाओं में मजबूत लिंक रखते हैं तो रिट-लूप से बचना होगा। चक्र बनाए रखने से बचने के बारे में अधिक जानने के लिए, लेख "मेमोरी मैनेजमेंट" देखें ।

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

 extension List: Sequence { func makeIterator() -> AnyIterator<Value> { var node = firstNode return AnyIterator { //   ,    ,    : let value = node?.value node = node?.next return value } } } 

चूँकि उपरोक्त पुनरावृत्ति बहुत सरल है, हम कस्टम पुनरावृत्ति प्रकार को लागू करने की आवश्यकता से बचने के लिए AnyIterator मानक पुस्तकालय का उपयोग करते हैं। अधिक जटिल परिदृश्यों के लिए, IteratorProtocol एक मैच जोड़कर इसे लागू किया जा सकता है।

अगला, आवेषण के साथ शुरू करके, हमारी लिंक की गई सूची को संशोधित करने के लिए एक एपीआई जोड़ें। हम append विधि के साथ List विस्तार करेंगे, जो सम्मिलित मूल्य के लिए एक नया नोड जोड़ता है और फिर इस नोड को लौटाता है - इस तरह:

 extension List { @discardableResult mutating func append(_ value: Value) -> Node { let node = Node(value: value) node.previous = lastNode lastNode?.next = node lastNode = node if firstNode == nil { firstNode = node } return node } } 

ऊपर, हम @discardableResult विशेषता का उपयोग करते हैं, जो संकलक से कहता है कि कोई चेतावनी उत्पन्न न करें यदि हमारी पद्धति को कॉल करने का परिणाम उपयोग नहीं किया गया था, क्योंकि हम हमेशा उस नोड में रुचि नहीं रखते हैं जो बनाया गया था।

चूंकि लिंक की गई सूचियाँ अनुक्रमित पर आधारित नहीं हैं, लेकिन लिंक के माध्यम से मूल्यों की एक श्रृंखला बनाए रखने पर, विलोपन को लागू करना दूरस्थ नोड्स के निम्न और पिछले पड़ोसियों को अपडेट करने का एक मामला है, ताकि वे इसके बजाय एक-दूसरे को इंगित करें:

 extension List { mutating func remove(_ node: Node) { node.previous?.next = node.next node.next?.previous = node.previous //  « »,        ,    : if firstNode === node { firstNode = node.next } if lastNode === node { lastNode = node.previous } } } 

पूर्वगामी के आधार पर, हमारी सूची का प्रारंभिक संस्करण पूरा हो गया है, और हम इसे कार्रवाई में सत्यापित करने के लिए तैयार हैं। आइए हमारी नई सूची का उपयोग करने के लिए कैनवस को अपडेट करें, साथ ही एक शब्दकोश जो हमें जल्दी से यह पता लगाने की अनुमति देता है कि कौन सी नोड किसी दिए गए आकार आईडी से मेल खाती है:

 struct Canvas { private var shapes = List<Shape>() private var nodes = [Shape.ID : List<Shape>.Node]() func render() -> Image { let context = DrawingContext() shapes.forEach(context.draw) return context.makeImage() } mutating func add(_ shape: Shape) { nodes[shape.id] = shapes.append(shape) } mutating func remove(_ shape: Shape) { guard let node = nodes.removeValue(forKey: shape.id) else { return } shapes.remove(node) } } 

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

निष्कर्ष

इस तथ्य के बावजूद कि डेटा संरचनाएं इतनी मौलिक हैं कि उन्हें सभी प्रकार की प्रोग्रामिंग भाषाओं में पाया जा सकता है, जिस निर्णय के बारे में प्रत्येक विशिष्ट स्थिति में उपयोग करने के लिए अभी भी एक महत्वपूर्ण मात्रा में विचार, परीक्षण और प्रयोग की आवश्यकता हो सकती है, खासकर अगर हम चाहते हैं ताकि डेटा सेट बढ़ने पर हमारा कोड प्रभावी बना रहे।

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

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

अगर आप कोई प्रश्न, टिप्पणी या प्रतिक्रिया चाहते हैं तो आप मुझे ट्विटर पर देख सकते हैं या मुझे ईमेल कर सकते हैं।

आपका ध्यान के लिए धन्यवाद!