❕ 🙍🏼 👨🏾‍🤝‍👨🏼 डेटा संरचना: एक सूची जो सब कुछ कर सकती है * 👩🏻‍🤝‍👨🏼 🛴 ↪️

* सब कुछ करके, मेरा मतलब है कि किसी सरणी के एकल तत्व पर संचालन का अपेक्षाकृत त्वरित निष्पादन।

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

add (obj), get (obj), सेट (इंडेक्स, obj): लगभग सभी सूचियों का एक मूल सेट, जैसे ArrayList।
add (index, obj): ट्री जैसी संरचनाएं, उदा। आम-संग्रह से ट्रीलिस्ट।
निकालें (सूचकांक): ऊपर के समान।
(obj), indexOf (obj) शामिल हैं: आप ArrayList और HashMap का एक गुच्छा उपयोग कर सकते हैं।
remove (obj): ... मुझे जवाब देना मुश्किल लगता है। कुछ मामलों में, आप एक LinkedHashSet के साथ प्राप्त कर सकते हैं। इसे पिछले दो बिंदुओं की उपस्थिति में तुच्छ रूप से हल किया जाता है, लेकिन कौन सी संरचनाएं दोनों को जल्दी कर सकती हैं?

जब मुझे त्वरित ऐड (obj) के साथ एक संरचना की आवश्यकता होती है, तो (इंडेक्स), निकालें (इंडेक्स) और इंडेक्सऑफ (obj), Google ने उत्तर नहीं दिया। मुझे इस तरह की संरचनाओं का कोई कोड उदाहरण या विवरण नहीं मिला। शायद मैं वहाँ नहीं देख रहा था, मुझे खुद ही इसका आविष्कार करना था। लेकिन अगर कोई टिप्पणी में लिंक को छोड़ता है, तो मैं इसकी सराहना करूंगा।

शायद किसी ने महसूस किया कि आप एक ट्रीलिस्ट ले सकते हैं, जो सूची के बीच में आइटम को जल्दी से सम्मिलित / हटा सकता है और इंडेक्सऑफ (ओबज) के त्वरित निष्पादन के लिए ट्रीलिस्ट में ऑब्जेक्ट से इंडेक्स में एक हैशपॉप जोड़ सकता है। और यह एक सरल, सुरुचिपूर्ण, लेकिन गलत निर्णय होगा। आखिरकार, जब मध्य में जोड़ते हैं या बीच से हटाते हैं, तो आधे तत्वों के लिए, औसतन सूचकांकों को पुनर्गणना करना आवश्यक होगा। यह O (n) के प्रदर्शन को नीचा दिखाएगा।

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

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

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

लिंक अंत में होंगे।

क्यों जरूरी है?

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

मैं मानता हूं कि कई उदाहरण दूर की कौड़ी हैं। सभी या लगभग सब कुछ दूसरे तरीके से हल किया जा सकता है।

कैशिंग और संपीड़न

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

यह विचार यह है: किसी अन्य ऑब्जेक्ट को संसाधित करते समय, हम सूची में इसे ढूंढते हैं। यदि नहीं मिला है, तो ऑब्जेक्ट को सहेजें और इसे सूची के शीर्ष पर जोड़ें। यदि पाया जाता है, तो हम सूची में इसके सूचकांक को लेते हैं और वस्तु के बजाय हम केवल इसके सूचकांक को बचाते हैं, जिसके बाद हम वस्तु को सूची के शीर्ष पर ले जाते हैं। इस प्रकार, अक्सर होने वाली वस्तुएं छोटे सूचकांक प्राप्त करेंगी, और केवल एक बार होने वाली वस्तुएं अंततः सूची के अंत में चली जाएंगी और हटा दी जाएंगी।

मोड़

यदि कुछ कार्यों के लिए सामान्य FIFO कतार के बजाय, एक समान संरचना का उपयोग किया जाता है, तो निम्नलिखित ऑपरेशन किए जा सकते हैं:

प्रश्न का उत्तर दें: इस कार्य से पहले कितने कार्य कतार में हैं।
कतार से कार्य निकालें।

सुपरमार्केट में यह पसंद है। यदि आप एक चॉकलेट बार के लिए आए थे, लेकिन आप देखते हैं कि रेखा धीरे-धीरे आगे बढ़ रही है, तो शायद चॉकलेट बार की इतनी आवश्यकता नहीं है? :)

उच्च अंक तालिका

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

यदि वे पहले से बेहतर परिणाम दिखाते हैं तो खिलाड़ियों को सूची में उच्च स्थान पर ले जाएं।
खिलाड़ियों को सूची से हटा दें, उदाहरण के लिए, धोखाधड़ी के लिए प्रतिबंध के मामले में।
प्रत्येक खिलाड़ी को दिखाएं कि वह कहां है।
पृष्ठ द्वारा रिकॉर्ड पृष्ठ की तालिका दिखाएं।
स्थानों में एक विरल तालिका दिखाएं, उदाहरण के लिए, समय 1, 2, 3, 5, 10, 20, 50, 100, 1000, 10000 स्थान।

डेटा संरचना

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

इम्प्लिक्ट की ट्री

एक पेड़ में नोड्स (नोड्स) होते हैं। प्रत्येक नोड में एक ऑब्जेक्ट का लिंक होता है जो नोड में संग्रहीत होता है और 2 लिंक अन्य नोड्स के लिए होता है: बाएं और दाएं। सबसे ऊपरी नोड को रूट नोड कहा जाता है। सबसे सरल मामले में, नोड कुछ इस तरह दिखता है:

class Node<T> {
  obj: T
  left: Node<T>
  right: Node<T>
}

बाएं उपरी में प्रत्येक नोड के लिए शास्त्रीय बाइनरी ट्री में, सभी ऑब्जेक्ट वर्तमान नोड की तुलना में छोटे होते हैं, और दाएं में - बड़े। उदाहरण के लिए:

                             [ element: 25 ]
                           /                 \
                          /                   \
          [ element: 14 ]                       [ element: 45 ]
           /          \                           /          \
          /            \                         /            \
[ element: 10 ]    [ element: 22 ]     [ element: 27 ]    [ element: 90 ]
                    /          \                            /
                   /            \                          /
            [ element: 17 ] [ element: 23 ]         [ element: 80 ]

लेकिन हमारे उद्देश्य के लिए, ऐसा पेड़ उपयुक्त नहीं है। हमें सॉर्ट की गई वस्तुओं को संग्रहीत करने की आवश्यकता नहीं है, लेकिन हमें एक सरणी में, सूचकांक द्वारा उन तक पहुंच की आवश्यकता है।

मैं एक पेड़ में एक सरणी कैसे रख सकता हूं? आइए सरणी के मध्य से सूचकांक I के साथ एक तत्व का चयन करें। रूट नोड में सरणी से ith तत्व रखें। 2 उपप्रकार जड़ नोड से बाहर निकलते हैं। बाएं सबट्री में हम आधा सरणी इंडेक्स <i के साथ रखते हैं, और दाईं ओर इंडेक्स> i के साथ। यह कैसे करना है? उसी तरह से: हम एक सबर्रे में बीच से एक तत्व का चयन करते हैं, इस तत्व को एक नोड में डालते हैं, हमें 2 और छोटे कर्ल मिलते हैं। और इसलिए जब तक हम सरणी के सभी तत्वों को पेड़ के नोड्स में नहीं डालते हैं।

उदाहरण के लिए, तत्वों के साथ एक सरणी ["q", "w", "e", "r", "t", "y", "u"] इस तरह दिख सकता है:

                            [el: r,  size: 7]
                           /        :        \
                          /         :         \
         [el: w, size: 3]           :           [el: y, size: 3]
           /     :    \             :             /    :     \
          /      :     \            :            /     :      \
[el: q, size: 1] : [el: e, size: 1] : [el: t, size: 1] : [el: u, size: 1]
        :        :         :        :         :        :         :
        :        :         :        :         :        :         :
       [q]      [w]       [e]      [r]       [t]      [y]       [u]

Index:  0        1         2        3         4        5         6

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

हमारे मामले में, पेड़ संतुलित है, सभी उपप्रकारों की गहराई समान है। लेकिन ऐसा होना जरूरी नहीं है।

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

आइए देखें कि कैसे ढूंढें, उदाहरण के लिए, ऐसे पेड़ में सूचकांक = 4 वाला एक तत्व।
हम क्रॉल नोड से शुरू करते हैं (रूट, "आर" तत्व के साथ हमारे मामले में)। हमारे पास 3 विकल्प हैं: हम पहले से ही दाहिने नोड पर हैं, दाईं ओर बाईं ओर, दाईं ओर दाईं ओर नोड है। वांछित तत्व की तलाश करने के लिए समझने के लिए, आपको बाएं सबट्री के आकार की तुलना करने की आवश्यकता है (हमारे मामले में left.size = 3) और वर्तमान सूचकांक (हमारे मामले में 4)। यदि ये 2 संख्याएं समान हैं, तो हमें इसमें आवश्यक नोड और वांछित तत्व मिला। यदि बाएं सबट्री का आकार बड़ा है, तो बाएं सबट्री में आवश्यक नोड है। यदि यह कम है, तो आपको सही सबट्री में देखने की आवश्यकता है, लेकिन आपको वांछित इंडेक्स को कम करने की आवश्यकता है: इंडेक्स = इंडेक्स - लेफ्ट.साइज - 1.

चूंकि हमारे मामले में लेफ्टिनेंट है। <इंडेक्स, हम नए इंडेक्स 4 - 3 के साथ तत्व के लिए सही सबट्री में देख रहे हैं। 1 = 0. तत्व "y" के साथ नोड पर जाएं।

फिर हम वही काम करते हैं जो हमने रूट नोड में किया था। बायें.साइज़ और इंडेक्स की तुलना करें। 1> 0 के बाद से, हम बाएं सबट्री में देखते हैं, तत्व "t" के साथ नोड में जाते हैं।

इस नोड में कोई भी उप-योग नहीं है, और इसका आकार 0. इंडेक्स = लेफ्ट है। इसका मतलब है कि हमें इंडेक्स 4 के साथ एक नोड मिला है और इससे आवश्यक तत्व "टी" प्राप्त कर सकते हैं।

छद्म कोड में, यह कुछ इस तरह दिखता है:

function get(node: Node<T>, index: int): T {
  val leftSize: int = (node.left == null) ? 0 : node.left.size;
  if (leftSize == index) {
    return node.obj;
  } else if (leftSize > index) {
    return get(node.left, index);
  } else {
    return get(node.right, index — leftSize — 1);
  }
}

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

थोड़ा अनुकूलन

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

                             [el: r, pos: 3]
                           /        :        \
                          /         :         \
         [el: w, pos: -2]           :           [el: y, pos: +2]
           /     :    \             :             /    :     \
          /      :     \            :            /     :      \
[el: q, pos: -1] : [el: e, pos: +1] : [el: t, pos: -1] : [el: u, pos: +1]
        :        :         :        :         :        :         :
        :        :         :        :         :        :         :
       [q]      [w]       [e]      [r]       [t]      [y]       [u]

Index:  0        1         2        3         4        5         6

उदाहरण के लिए, रूट नोड "r" की स्थिति 3 है। नोड "w" की स्थिति -2 मूल नोड के सापेक्ष है या निरपेक्ष स्थिति 3 + (-2) = 1. इसी प्रकार, आप एक और स्तर नीचे जा सकते हैं, उदाहरण के लिए, नोड "ई" की स्थिति 3 है + (-2) + (+1) = 2. जो है, नोड इंडेक्स पेड़ के मूल से इस नोड तक की स्थिति का योग है।

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

अनुक्रमण जोड़ें

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

लेकिन पहले, आइए कार्य को थोड़ा सरल करें। आइए एक संरचना बनाएं जो केवल अद्वितीय तत्वों को संग्रहीत करता है।

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

class IndexedTreeListSet<T> {
  root: Node<T>
  indexMap: Map<T, Node<T>>
}

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

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

class Node<T> {
  obj: T
  left: Node<T>
  right: Node<T>
  parent: Node<T>
  pos: int
}

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

अद्वितीय तत्वों वाली सूची के लिए, समस्या को हल किया जा सकता है।

सच है, हमें एक छोटी सी समस्या है। मान लीजिए कि हम सेट (इंडेक्स, ऑबज) कहते हैं। हम नोड में एक तत्व को दूसरे के साथ आसानी से बदल सकते हैं, लेकिन केवल तभी जब सूची में कोई नया तत्व न हो। और यदि हां, तो मुझे क्या करना चाहिए? पुरानी स्थिति से अतिरिक्त आइटम निकालें और नए में डालें? या इसके विपरीत, पहले जोड़ें और फिर हटाएं? परिणाम अलग हो सकता है। और आप कुछ भी नहीं कर सकते हैं या एक अपवाद नहीं फेंक सकते हैं। कोई सही समाधान नहीं है।

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

हम विशिष्टता को हटा देते हैं

ठीक है, चीजों को और जटिल करते हुए, हम उसी वस्तुओं को बनाए रखें। जाहिर है, आपको तालिका के साथ कुछ करने की आवश्यकता है। इसमें नोड्स की सूची संग्रहीत करने का पहला विचार बहुत अच्छा नहीं लगता है: सूची की लंबाई में वृद्धि के साथ, प्रदर्शन बिगड़ जाएगा। O (n) तक यदि सभी सूची आइटम समान हैं।

तो चलो एक सूची के बजाय नोड्स के सॉर्ट किए गए ट्री को एक तालिका में संग्रहीत करने का प्रयास करें। सूची में स्थिति के अनुसार क्रमबद्ध।

class IndexedTreeList<T> {
  root: Node<T>
  indexMap: Map<T, TreeSet<Node<T>>>
}

फिर आकार मी के ट्रीसेट <node> से प्रविष्टि / विलोपन लॉग (m) नोड्स के पदों की तुलना के दौरान होगा, और प्रत्येक तुलना लॉग (n) समय से अधिक होगी। समान संरचना में डालने या हटाने की अंतिम जटिलता ओ (लॉग (एन) * (1 + लॉग (एम))) में होगी, जहां n सूची में तत्वों की कुल संख्या है और एम सूची में तत्वों की संख्या सम्मिलित / हटाए गए के बराबर है। सबसे खराब स्थिति में, जब सभी तत्व एक-दूसरे के बराबर होते हैं, तो हम जटिलता ओ (लॉग (एन) ^ 2) प्राप्त करते हैं।

एक चौकस पाठक शायद आपत्ति करेगा: लेकिन अपरिवर्तनीयता के बारे में क्या? आखिरकार, हम वस्तुओं को बदल नहीं सकते हैं यदि वे टेबल की हैं? सामान्य तौर पर, यह है। हालांकि, एक पेड़ के लिए जो वस्तुओं को सॉर्ट करता है कुंजी में, तुलना के लिए मानक नियमों के अलावा, यह अपरिवर्तनीय को संरक्षित करने के लिए पर्याप्त है: यदि एक <b, तो यह संपत्ति समय के साथ नहीं बदलना चाहिए। यह सिर्फ हमारा मामला है: यदि एक नोड की स्थिति दूसरे नोड की स्थिति से कम है, तो इस संपत्ति को संरक्षित किया जाएगा, भले ही उनके बीच कितने नोड जोड़े या हटाए गए हों।

क्या संरचना को लगातार बनाना संभव है?

संक्षिप्त उत्तर: नहीं, यह असंभव है। पेड़ की द्विवर्णता के कारण, जड़ से पत्तियों और पीठ तक, हमारे पास प्रत्येक पेड़ का नोड प्रत्येक से जुड़ा हुआ है। दृढ़ता इस तरह से नहीं की जा सकती है, आपको किसी भी परिवर्तन के साथ पूरी संरचना को फिर से बनाना होगा।

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

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

कुछ कार्यान्वयन सुविधाएँ

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

ट्रीलिस्ट से विरासत में मिली एक अन्य विशेषता पेड़ के पत्तों में उप-वृक्षों के लिंक हैं। प्रत्येक नोड बूलियन को छोड़ देता हैबिक्री और दाहिना। ये चर बाएं / दाएं उपप्रकार की उपस्थिति या अनुपस्थिति का संकेत देते हैं। यदि कोई सबट्री नहीं है, तो बाएं / दाएं में, उप-लिंक के लिंक के बजाय, नोड के लिए एक लिंक जो पिछले या अगले तत्व से मेल खाती है, संग्रहीत है। हमारे उदाहरण में, ["q", "w", "e", "r", "t", "y", "u"] नोड "e" पत्तेदार है, इसका कोई उपप्रकार नहीं है। तदनुसार, leftIsPrepret और rightIsNext क्रमशः सत्य हैं, और बाएं और दाएं बिंदु क्रमशः "w" और "r" हैं। यह दृष्टिकोण तेजी से सूची के माध्यम से पुनरावृति में मदद करता है। और यह नई सुविधाओं की प्रोग्रामिंग में हस्तक्षेप करता है :)

तालिका ऑब्जेक्ट → नोड के साथ काम करने के बारे में थोड़ा सा। आदर्श रूप से, आपको संरचना में जोड़ते समय एक बार तालिका में एक तत्व डालना होगा और संरचना से हटाते समय इसे एक बार हटाना होगा। व्यवहार में, मैं इसे हासिल नहीं कर सका। जब आप एक आइटम जोड़ते हैं, तो इसे तालिका में जोड़ा जाता है, सब कुछ वैसा ही होता है जैसा उसे होना चाहिए। हालाँकि, जब आप किसी आइटम को हटाते हैं, तो संतुलन एल्गोरिदम कभी-कभी नोड्स के बीच आइटम ले जाता है। परिणाम दो विलोपन और एक विलोपन के बजाय तालिका में एक रिकॉर्ड है। यह तय किया जा सकता है अगर आप बचे हुए ऑप्टिमाइज़ेशन और राइट आईनेक्स्ट से ऑप्टिमाइज़ेशन हटा दें। और यहां तक कि एक छोटे से प्रदर्शन लाभ प्राप्त करें, और न केवल हटाने के दौरान। कुछ परीक्षणों में, वृद्धि 10-20% थी। लेकिन मेरे परीक्षणों में पुनरावृत्ति की गति काफी कम हो जाती है, 1.5-2.5 गुना। मैंने अभी के लिए अनुकूलन छोड़ने का फैसला किया।

जावा में, मुख्य प्रकार के टेबल हैंशप और ट्रीपैप हैं। तालिका के लिए, एक ऑब्जेक्ट → एक नोड डिफ़ॉल्ट रूप से हैशपॉप का उपयोग करता है। हालाँकि, आप ट्री-मैप का उपयोग किसी कार्य-विशेष तुलनित्र के साथ कर सकते हैं। इस स्थिति में, IndexOf (obj) और remove (obj) उस ऑब्जेक्ट को खोज / हटा देगा जो कि तुलनित्र कोड के अनुसार निर्दिष्ट ऑब्जेक्ट के बराबर है। उदाहरण के लिए, हम उपयोगकर्ताओं की एक सूची संग्रहीत करते हैं, और तुलनित्र केवल नाम से उपयोगकर्ताओं की तुलना करता है। तब हम इस सवाल का जवाब दे सकते हैं कि "नेपोलियन?" नाम के साथ सूची के कौन से स्थान हैं। या सूची से सभी नेपोलियन को हटा दें :)।

संरचना अशक्त का समर्थन नहीं करती है। आप इसे ठीक कर सकते हैं, लेकिन कोई भावना नहीं है कि यह आवश्यक है।

इस तथ्य के बारे में कि संरचना "सब कुछ जानती है", मैं, निश्चित रूप से, थोड़ा भ्रामक था। बेशक, एकल तत्वों के साथ काम करते समय, सब कुछ ठीक है और कुछ शर्तों के तहत भी लघुगणक के लिए। हालांकि, वह कुछ ऐसी चीजों को नहीं जानती जो अन्य संरचनाएं कर सकती हैं। उदाहरण के लिए, एक कार्टिसियन पेड़ जिसमें एक निहित कुंजी होती है, हब पर इसके बारे में लेख थे यह नहीं जानता कि कैसे जल्दी से इंडेक्सऑफ किया जाए, लेकिन यह जानता है कि लॉगरिथम (औसतन, गारंटी नहीं) के लिए एक सूची में एक सूची और दो सूची बनाने का तरीका बताया गया है, साथ ही इसे लगातार बनाया जा सकता है।

प्रदर्शन

जावा में, प्रदर्शन आमतौर पर जेएमएच ढांचे का उपयोग करके मापा जाता है। Java11 के तहत 2017 मैकबुक प्रो पर टेस्ट आयोजित किए गए थे।

मैंने मानक ArrayList, TreeList के अपाचे कॉमन-कलेक्शन और कई परिदृश्यों में मेरे दो वर्गों IndexedTreeList और IndexedTreeListSet के प्रदर्शन की तुलना की। प्रत्येक परिदृश्य में, एक ही प्रकार के 1000 ऑपरेशन किए गए थे, इसलिए परिणाम को 1000 से गुणा किया जाना चाहिए।

स्पॉइलर के तहत कोड

@Fork(1)
@Warmup(iterations = 3)
@Measurement(iterations = 5)
public class PerformanceCompare {

    public static final Map<String, Class> CLASSES = Stream.of(TreeList.class, IndexedTreeListSet.class, IndexedTreeList.class,
            ArrayList.class)
            .collect(Collectors.toMap(c -> c.getSimpleName(), c -> c));

    public static final int ITERATIONS = 1000;

    @State(Scope.Benchmark)
    public static class Plan {

        @Param({"10", "100", "1000", "10000", "100000", "1000000"/*, "10000000"*/})
        public int size;

        @Param({"ArrayList", "TreeList", "IndexedTreeList", "IndexedTreeListSet"})
        public String className;

        private Random random;
        private List<Integer> list;

        @Setup
        public void init() throws IllegalAccessException, InstantiationException {
            random = new Random();
            list = (List<Integer>) CLASSES.get(className).newInstance();

            for (int i = 0; i < size; i++) {
                list.add(i);
            }
        }
    }


    @Benchmark
    public void indexOfKnown(Plan plan, Blackhole blackhole) {
        List<Integer> list = plan.list;
        Random random = plan.random;
        int value = 0;
        for (int i = 0; i < ITERATIONS; i++) {
            value = list.indexOf(random.nextInt(plan.size));
        }
        blackhole.consume(value);
    }

    @Benchmark
    public void indexOfUnknown(Plan plan, Blackhole blackhole) {
        List<Integer> list = plan.list;
        Random random = plan.random;
        int value = 0;
        for (int i = 0; i < ITERATIONS; i++) {
            value += list.indexOf(random.nextInt());
        }
        blackhole.consume(value);
    }

    @Benchmark
    public void addRemoveRandom(Plan plan, Blackhole blackhole) {
        List<Integer> list = plan.list;
        Random random = plan.random;
        int value = 0;
        for (int i = 0; i < ITERATIONS; i++) {
            list.add(random.nextInt(list.size() + 1), random.nextInt());
            value += list.remove(random.nextInt(list.size()));
        }
        blackhole.consume(value);
    }

    @Benchmark
    public void get(Plan plan, Blackhole blackhole) {
        List<Integer> list = plan.list;
        Random random = plan.random;
        int value = 0;
        for (int i = 0; i < ITERATIONS; i++) {
            value += list.get(random.nextInt(list.size()));
        }
        blackhole.consume(value);
    }

    @Timeout(time = 1, timeUnit = TimeUnit.MILLISECONDS)
    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
                .include(PerformanceCompare.class.getSimpleName())
                .forks(1)
//                .jvmArgs("-Xms2048m", "-Xmx2048m", "-XX:MaxDirectMemorySize=512M")
                .build();

        new Runner(opt).run();
    }
}

शुरुआत करने के लिए, मैंने एक सूची से एक यादृच्छिक आइटम प्राप्त करने की गति की तुलना की। मैं आपको तुरंत चेतावनी दूंगा कि इस परीक्षा में ओवरहेड बहुत महत्वपूर्ण है। 100,000 * 1,000 प्रति सेकंड के संचालन के परिणाम गंभीर रूप से विकृत हैं।

परीक्षा परिणाम प्राप्त करें

PerformanceCompare.get                       ArrayList       10  thrpt    5  79865.412 ± 10145.202  ops/s
PerformanceCompare.get                       ArrayList      100  thrpt    5  81862.243 ±   983.727  ops/s
PerformanceCompare.get                       ArrayList     1000  thrpt    5  81033.507 ±  4540.206  ops/s
PerformanceCompare.get                       ArrayList    10000  thrpt    5  64096.123 ±  1430.361  ops/s
PerformanceCompare.get                       ArrayList   100000  thrpt    5  41289.491 ± 11286.114  ops/s
PerformanceCompare.get                       ArrayList  1000000  thrpt    5   8598.944 ±  2048.461  ops/s
PerformanceCompare.get                        TreeList       10  thrpt    5  33912.275 ±  3754.284  ops/s
PerformanceCompare.get                        TreeList      100  thrpt    5  21346.854 ±   863.588  ops/s
PerformanceCompare.get                        TreeList     1000  thrpt    5  14808.414 ±   508.098  ops/s
PerformanceCompare.get                        TreeList    10000  thrpt    5   8679.384 ±   109.250  ops/s
PerformanceCompare.get                        TreeList   100000  thrpt    5   4605.998 ±  1028.945  ops/s
PerformanceCompare.get                        TreeList  1000000  thrpt    5   2241.381 ±   768.147  ops/s
PerformanceCompare.get                 IndexedTreeList       10  thrpt    5  34054.357 ±  3682.829  ops/s
PerformanceCompare.get                 IndexedTreeList      100  thrpt    5  21934.002 ±  2339.947  ops/s
PerformanceCompare.get                 IndexedTreeList     1000  thrpt    5  14626.691 ±   369.893  ops/s
PerformanceCompare.get                 IndexedTreeList    10000  thrpt    5   7386.863 ±   342.150  ops/s
PerformanceCompare.get                 IndexedTreeList   100000  thrpt    5   4562.126 ±   352.772  ops/s
PerformanceCompare.get                 IndexedTreeList  1000000  thrpt    5   2105.718 ±   702.064  ops/s
PerformanceCompare.get              IndexedTreeListSet       10  thrpt    5  33317.503 ±  2307.829  ops/s
PerformanceCompare.get              IndexedTreeListSet      100  thrpt    5  21247.440 ±  1253.386  ops/s
PerformanceCompare.get              IndexedTreeListSet     1000  thrpt    5  14665.557 ±   487.833  ops/s
PerformanceCompare.get              IndexedTreeListSet    10000  thrpt    5   7667.214 ±    80.093  ops/s
PerformanceCompare.get              IndexedTreeListSet   100000  thrpt    5   3454.023 ±    82.994  ops/s
PerformanceCompare.get              IndexedTreeListSet  1000000  thrpt    5   1768.701 ±    35.878  ops/s

यहां, विचित्र रूप से पर्याप्त है, सबसे बड़ा हित मानक ArrayList है। सैद्धांतिक रूप से, इससे बाहर निकलने की गति स्थिर होनी चाहिए और तत्वों की संख्या पर निर्भर नहीं होना चाहिए। व्यवहार में, प्रदर्शन पहले लगभग 90,000 * 1000 संचालन प्रति सेकंड (ओवरहेड याद रखें) रखता है, लेकिन कई हजार वस्तुओं की सूची लंबाई के साथ यह शिथिल होना शुरू हो जाता है। यह लगातार बढ़ती कैश मिस के कारण है: प्रोसेसर कैश में आवश्यक डेटा नहीं है और अधिक से अधिक बार आपको रैम में डेटा के लिए जाने की आवश्यकता होती है। एक लाख तत्वों के साथ, परीक्षण की गति 10 गुना कम है, लेकिन व्यवहार में, प्रदर्शन में गिरावट और भी अधिक है।

ट्रीलिस्ट, इंडेक्सट्रीलिस्ट और इंडेक्सट्रीलिस्टस्टैट समान परिणाम दिखाते हैं। ArrayList की तुलना में बहुत धीमी गति से। यहां तक कि तत्वों की एक छोटी संख्या के साथ, ट्रीलिस्ट ArrayList की तुलना में कई गुना धीमा है, हालांकि परीक्षण केवल 2 बार अंतर दिखाता है।

अगला परीक्षण addRemoveRandom है। यहां, प्रत्येक परीक्षण में, मैं एक तत्व को यादृच्छिक स्थिति में सम्मिलित करता हूं और एक तत्व को यादृच्छिक स्थिति से हटाता हूं।

AddRemoveRandom परीक्षा परिणाम

PerformanceCompare.addRemoveRandom           ArrayList       10  thrpt    5  12440.764 ±   485.642  ops/s
PerformanceCompare.addRemoveRandom           ArrayList      100  thrpt    5   9880.123 ±   464.014  ops/s
PerformanceCompare.addRemoveRandom           ArrayList     1000  thrpt    5   5288.905 ±  1219.055  ops/s
PerformanceCompare.addRemoveRandom           ArrayList    10000  thrpt    5   1024.942 ±   179.366  ops/s
PerformanceCompare.addRemoveRandom           ArrayList   100000  thrpt    5     91.219 ±    25.380  ops/s
PerformanceCompare.addRemoveRandom           ArrayList  1000000  thrpt    5      5.499 ±     0.400  ops/s
PerformanceCompare.addRemoveRandom            TreeList       10  thrpt    5   6242.607 ±   350.290  ops/s
PerformanceCompare.addRemoveRandom            TreeList      100  thrpt    5   3117.945 ±   116.066  ops/s
PerformanceCompare.addRemoveRandom            TreeList     1000  thrpt    5   1829.778 ±    80.516  ops/s
PerformanceCompare.addRemoveRandom            TreeList    10000  thrpt    5   1230.077 ±    53.381  ops/s
PerformanceCompare.addRemoveRandom            TreeList   100000  thrpt    5    443.571 ±    69.207  ops/s
PerformanceCompare.addRemoveRandom            TreeList  1000000  thrpt    5    308.963 ±    84.077  ops/s
PerformanceCompare.addRemoveRandom     IndexedTreeList       10  thrpt    5   3556.511 ±   144.596  ops/s
PerformanceCompare.addRemoveRandom     IndexedTreeList      100  thrpt    5   2120.777 ±    83.848  ops/s
PerformanceCompare.addRemoveRandom     IndexedTreeList     1000  thrpt    5   1211.112 ±    92.288  ops/s
PerformanceCompare.addRemoveRandom     IndexedTreeList    10000  thrpt    5    789.458 ±    19.450  ops/s
PerformanceCompare.addRemoveRandom     IndexedTreeList   100000  thrpt    5    302.989 ±    40.030  ops/s
PerformanceCompare.addRemoveRandom     IndexedTreeList  1000000  thrpt    5    178.822 ±    92.853  ops/s
PerformanceCompare.addRemoveRandom  IndexedTreeListSet       10  thrpt    5   4138.007 ±   119.943  ops/s
PerformanceCompare.addRemoveRandom  IndexedTreeListSet      100  thrpt    5   2435.803 ±    20.276  ops/s
PerformanceCompare.addRemoveRandom  IndexedTreeListSet     1000  thrpt    5   1445.054 ±   276.909  ops/s
PerformanceCompare.addRemoveRandom  IndexedTreeListSet    10000  thrpt    5    972.256 ±    19.987  ops/s
PerformanceCompare.addRemoveRandom  IndexedTreeListSet   100000  thrpt    5    366.608 ±    94.487  ops/s
PerformanceCompare.addRemoveRandom  IndexedTreeListSet  1000000  thrpt    5    227.677 ±    48.276  ops/s

यह माना जा सकता है कि ArrayList छोटी सूचियों पर तेज़ है। हालांकि, तथ्य यह है कि वह इस परीक्षण में 10,000 तत्वों की सूची में जीतता है, दिलचस्प लग रहा है। जाहिरा तौर पर, System.arrayCopy बहुत अच्छी तरह से अनुकूलित है और आधुनिक प्रोसेसर की सभी विशेषताओं का उपयोग करता है। 10,000 आइटम पर शुरू, विशेष डेटा संरचनाएं जीतना शुरू कर रही हैं। 1,000,000 तत्वों के साथ, गति का अंतर 30-50 गुना है।

IndexedTreeList और IndexedTreeListSet ट्री लिस्ट की तुलना में धीमी होने की उम्मीद है। लगभग 1.5 - 2 बार।

शेष 2 परीक्षण indexOfKnown और indexOfUn परिचित को बस इस संरचना की मुख्य विशेषता का प्रदर्शन करना चाहिए। परीक्षणों के बीच अंतर यह है कि एक मामले में हम एक तत्व की तलाश कर रहे हैं जो सूची में है, और दूसरे मामले में हम एक तत्व की तलाश कर रहे हैं जो सूची में नहीं है।

परीक्षा परिणाम indexOfKnown और indexOfUn परिचित

PerformanceCompare.indexOfKnown              ArrayList       10  thrpt    5  41424.356 ±   549.047  ops/s
PerformanceCompare.indexOfKnown              ArrayList      100  thrpt    5  17216.477 ±  1444.744  ops/s
PerformanceCompare.indexOfKnown              ArrayList     1000  thrpt    5   2296.306 ±    76.372  ops/s
PerformanceCompare.indexOfKnown              ArrayList    10000  thrpt    5    233.863 ±    26.926  ops/s
PerformanceCompare.indexOfKnown              ArrayList   100000  thrpt    5     23.208 ±     2.776  ops/s
PerformanceCompare.indexOfKnown              ArrayList  1000000  thrpt    5      0.919 ±     0.455  ops/s
PerformanceCompare.indexOfKnown               TreeList       10  thrpt    5  26740.708 ±  1323.125  ops/s
PerformanceCompare.indexOfKnown               TreeList      100  thrpt    5   5670.923 ±    99.638  ops/s
PerformanceCompare.indexOfKnown               TreeList     1000  thrpt    5    745.408 ±    26.827  ops/s
PerformanceCompare.indexOfKnown               TreeList    10000  thrpt    5     52.288 ±     1.362  ops/s
PerformanceCompare.indexOfKnown               TreeList   100000  thrpt    5      4.224 ±     0.855  ops/s
PerformanceCompare.indexOfKnown               TreeList  1000000  thrpt    5      0.193 ±     0.052  ops/s
PerformanceCompare.indexOfKnown        IndexedTreeList       10  thrpt    5  34485.128 ±  1582.703  ops/s
PerformanceCompare.indexOfKnown        IndexedTreeList      100  thrpt    5  29209.412 ±  1544.268  ops/s
PerformanceCompare.indexOfKnown        IndexedTreeList     1000  thrpt    5  21139.584 ±  1442.867  ops/s
PerformanceCompare.indexOfKnown        IndexedTreeList    10000  thrpt    5  12544.306 ±   312.097  ops/s
PerformanceCompare.indexOfKnown        IndexedTreeList   100000  thrpt    5   3538.201 ±   272.537  ops/s
PerformanceCompare.indexOfKnown        IndexedTreeList  1000000  thrpt    5   1420.119 ±   538.476  ops/s
PerformanceCompare.indexOfKnown     IndexedTreeListSet       10  thrpt    5  39201.995 ±  1887.065  ops/s
PerformanceCompare.indexOfKnown     IndexedTreeListSet      100  thrpt    5  34204.112 ±  1122.517  ops/s
PerformanceCompare.indexOfKnown     IndexedTreeListSet     1000  thrpt    5  25374.557 ±  1596.746  ops/s
PerformanceCompare.indexOfKnown     IndexedTreeListSet    10000  thrpt    5  14291.317 ±   391.180  ops/s
PerformanceCompare.indexOfKnown     IndexedTreeListSet   100000  thrpt    5   4215.898 ±   283.680  ops/s
PerformanceCompare.indexOfKnown     IndexedTreeListSet  1000000  thrpt    5   1729.100 ±  1260.815  ops/s
PerformanceCompare.indexOfUnknown            ArrayList       10  thrpt    5  59053.313 ±  1845.665  ops/s
PerformanceCompare.indexOfUnknown            ArrayList      100  thrpt    5  10867.572 ±   142.823  ops/s
PerformanceCompare.indexOfUnknown            ArrayList     1000  thrpt    5   1186.583 ±    28.003  ops/s
PerformanceCompare.indexOfUnknown            ArrayList    10000  thrpt    5    120.953 ±     4.146  ops/s
PerformanceCompare.indexOfUnknown            ArrayList   100000  thrpt    5     11.936 ±     0.320  ops/s
PerformanceCompare.indexOfUnknown            ArrayList  1000000  thrpt    5      0.566 ±     0.335  ops/s
PerformanceCompare.indexOfUnknown             TreeList       10  thrpt    5  28134.237 ±  2291.670  ops/s
PerformanceCompare.indexOfUnknown             TreeList      100  thrpt    5   3153.930 ±   158.734  ops/s
PerformanceCompare.indexOfUnknown             TreeList     1000  thrpt    5    322.383 ±    44.245  ops/s
PerformanceCompare.indexOfUnknown             TreeList    10000  thrpt    5     25.674 ±     1.787  ops/s
PerformanceCompare.indexOfUnknown             TreeList   100000  thrpt    5      1.867 ±     0.291  ops/s
PerformanceCompare.indexOfUnknown             TreeList  1000000  thrpt    5      0.093 ±     0.008  ops/s
PerformanceCompare.indexOfUnknown      IndexedTreeList       10  thrpt    5  66625.126 ±  5232.668  ops/s
PerformanceCompare.indexOfUnknown      IndexedTreeList      100  thrpt    5  70038.055 ±  5803.848  ops/s
PerformanceCompare.indexOfUnknown      IndexedTreeList     1000  thrpt    5  63240.467 ±   885.956  ops/s
PerformanceCompare.indexOfUnknown      IndexedTreeList    10000  thrpt    5  54731.988 ±  3950.150  ops/s
PerformanceCompare.indexOfUnknown      IndexedTreeList   100000  thrpt    5  22049.476 ±   821.924  ops/s
PerformanceCompare.indexOfUnknown      IndexedTreeList  1000000  thrpt    5   9459.862 ±   804.738  ops/s
PerformanceCompare.indexOfUnknown   IndexedTreeListSet       10  thrpt    5  70274.968 ± 15830.355  ops/s
PerformanceCompare.indexOfUnknown   IndexedTreeListSet      100  thrpt    5  71017.685 ±  6920.447  ops/s
PerformanceCompare.indexOfUnknown   IndexedTreeListSet     1000  thrpt    5  66405.960 ±  1127.231  ops/s
PerformanceCompare.indexOfUnknown   IndexedTreeListSet    10000  thrpt    5  57983.963 ±  3276.142  ops/s
PerformanceCompare.indexOfUnknown   IndexedTreeListSet   100000  thrpt    5  41277.110 ±  9919.893  ops/s
PerformanceCompare.indexOfUnknown   IndexedTreeListSet  1000000  thrpt    5   9840.185 ±  2159.352  ops/s

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

लेकिन यहाँ IndexedTreeList और IndexedTreeListSet अपेक्षित अच्छे परिणाम दिखाते हैं। ये डेटा संरचनाएं 10 तत्वों के साथ भी ArrayList की तुलना में एक indexOf निष्पादन गति दिखाती हैं। 1000 तत्वों के साथ, ये संरचनाएं 10 गुना तेज हैं, 1,000,000 तेजी से 1000 गुना। जब कोई ऐसा आइटम खोज रहा है जो सूची में नहीं है, तो उन्हें सूची से आइटम की खोज करते समय बेहतर गति देने की अपेक्षा की जाती है।

ध्यान देने के लिए और क्या दिलचस्प है, IndexOfUn परिचित परीक्षण में IndexedTreeList और IndexedTreeListSet का प्रदर्शन उपखंड है। यहां की स्थिति ArrayList.get के साथ परीक्षण के समान है। सैद्धांतिक रूप से, हमें प्रदर्शन में गिरावट नहीं मिलनी चाहिए थी, लेकिन व्यवहार में, कैश की कमी के कारण, हम इसे, इसके अलावा, महत्वपूर्ण रूप से पा गए।

एक निष्कर्ष के बजाय

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

लेकिन अगर यह एक और बाइक है, तो भी मैंने इसे उपयोगी बनाने की कोशिश की। आम-संग्रह में एक पुल अनुरोध बनाया गया है, लेकिन इस लेख को लिखने के समय अभी तक डाला नहीं गया है। यह जानते हुए कि खुले स्रोत में सब कुछ धीरे-धीरे कैसे हो सकता है, अगर महीनों तक यह प्रक्रिया चली तो मुझे आश्चर्य नहीं हुआ।

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

किसी भी स्थिति में, शस्त्रागार में एक उपकरण होना मज़ेदार है जो कि (लगभग) अनुमानित जटिलता के साथ सब कुछ कर सकता है।

संदर्भ

जीरा में अपाचे आम-संग्रह टिकट में मूल पुल अनुरोध परियोजना

डेटा संरचना: एक सूची जो सब कुछ कर सकती है *