सॉर्ट किए गए डिक्शनरी से मेरी कुंजी पर सबसे नज़दीकी आइटम कैसे प्राप्त करें?

Question

वर्तमान में मैं एक विशिष्ट संख्या के लिए SortedList<T,U> पर एक बाइनरी खोज का उपयोग कर रहा हूं, और यदि यह अस्तित्व में नहीं है तो मुझे इसके बजाय निकटतम निम्न-बाउंड कुंजी-आइटम मिलता है।

मैंने देखा कि यह inserting unsorted data में धीमा था जो मैं बहुत कुछ कर रहा हूं।

क्या SortedDictionary के साथ कुछ ऐसा करने का कोई तरीका है, या क्या मुझे बस अपने SortedList पर चिपकना चाहिए?

Answer 1

SortedList<K, V> डेटा डालने पर वास्तव में धीमा है क्योंकि प्रत्येक बार जब कोई नया तत्व जोड़ा जाता है तो आंतरिक सरणी में <=N तत्वों को स्थानांतरित करता है। अतिरिक्तता की जटिलता O(N) है। फिर भी यह बाइनरी खोज का समर्थन करता है जो O(log N) में सटीक तत्व या पड़ोसियों को खोजने की अनुमति देता है।

संतुलित बाइनरी पेड़ आपकी समस्या का समाधान करने के लिए सबसे अच्छी डेटा संरचना है। O(log N)

खोजें मद में SortedList<K, V>

निकालें आइटम में

आइटम
1. जोड़े O(log N) में बनाम O(N) या O(log N)
में अपने निकटतम: आप निम्न कार्रवाई डब्ल्यू/लघुगणक जटिलता करने के लिए कर सकेंगे

तत्व या के लिए खोज रहे अपने द्विआधारी पेड़ में निकटतम कम ही सीमित है सरल है:

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

बाइनरी पेड़ को कार्यान्वित करने का वर्णन करने वाले कई लेख हैं। फिर भी मैं एक प्रकार का हैक का उपयोग कर .NET Framework संग्रह का पुन: उपयोग करने जा रहा हूं :)

अब, मैं आपको SortedSet<T> पेश कर रहा हूं जो स्वयं ही लाल-काले पेड़ है। इसमें एक कमी है, इसमें निकटतम नोड्स को तुरंत खोजने की कोई क्षमता नहीं है। लेकिन हम पेड़ में खोज के एल्गोरिदम को जानते हैं (यह 1 में वर्णित है) और इसे SortedSet<T>.Contains विधि (नीचे * पर संकुचित) में लागू किया गया है। अब हम रूट से सभी नोड्स को हमारे कस्टम तुलनाकर्ता का उपयोग करके ट्रैवर्सल के दौरान अंतिम बार देखे गए नोड पर कैप्चर कर सकते हैं। उसके बाद हम ऊपर कलन विधि का उपयोग निकटतम कम बाध्य नोड पा सकते हैं:

public class LowerBoundSortedSet<T> : SortedSet<T> { 

    private ComparerDecorator<T> _comparerDecorator; 

    private class ComparerDecorator<T> : IComparer<T> { 

     private IComparer<T> _comparer; 

     public T LowerBound { get; private set; } 

     private bool _reset = true; 

     public void Reset() 
     { 
      _reset = true; 
     } 

     public ComparerDecorator(IComparer<T> comparer) 
     { 
      _comparer = comparer; 
     } 

     public int Compare(T x, T y) 
     { 
      int num = _comparer.Compare(x, y); 
      if (_reset) 
      { 
       LowerBound = y; 
      } 
      if (num >= 0) 
      { 
       LowerBound = y; 
       _reset = false; 
      } 
      return num; 
     } 
    } 

    public LowerBoundSortedSet() 
     : this(Comparer<T>.Default) {} 

    public LowerBoundSortedSet(IComparer<T> comparer) 
     : base(new ComparerDecorator<T>(comparer)) { 
     _comparerDecorator = (ComparerDecorator<T>)this.Comparer; 
    } 

    public T FindLowerBound(T key) 
    { 
     _comparerDecorator.Reset(); 
     this.Contains<T>(key); 
     return _comparerDecorator.LowerBound; 
    } 
} 

आप देखते हैं कि निकटतम नोड खोजने सामान्य खोज से अधिक नहीं लेता है, अर्थात O(log N)। तो, यह आपकी समस्या का सबसे तेज़ समाधान है। यह संग्रह निकटतम खोजने में SortedList<K, V> जितना तेज़ है और इसके अतिरिक्त SortedSet<T> जितना तेज़ है।

SortedDictionary<K, V> के बारे में क्या? यह लगभग एक ही चीज़ को छोड़कर SortedSet<T> जैसा ही है: प्रत्येक कुंजी का मूल्य होता है। मुझे उम्मीद है कि आप SortedDictionary<K, V> के साथ ऐसा करने में सक्षम होंगे।

* decompiled SortedSet<T>.Contains विधि:

public virtual bool Contains(T item) 
{ 
    return this.FindNode(item) != null; 
} 

internal virtual SortedSet<T>.Node FindNode(T item) 
{ 
    for (SortedSet<T>.Node node = this.root; node != null; { 
    int num; 
    node = num < 0 ? node.Left : node.Right; 
    } 
) 
    { 
    num = this.comparer.Compare(item, node.Item); 
    if (num == 0) 
     return node; 
    } 
    return (SortedSet<T>.Node) null; 
}