मैं SortedDictionary से पिछली कुंजी कैसे प्राप्त करूं?

Question

मेरे पास कुंजी मूल्य जोड़े वाले शब्दकोश हैं।

SortedDictionary<int,int> dictionary=new SortedDictionary<int,int>(); 
dictionary.Add(1,33); 
dictionary.Add(2,20); 
dictionary.Add(4,35); 

मैं एक ज्ञात कुंजी मान से पिछली कुंजी मान जोड़ी प्राप्त करना चाहता हूं। उपर्युक्त मामले में, यदि मेरे पास कुंजी 4 है, तो मैं <2,20> कैसे प्राप्त कर सकता हूं?

Answer 1

इसके बाद से यह एक द्विआधारी खोज वृक्ष कि पूर्ववर्तियों या उत्तराधिकारियों का खुलासा नहीं करता के रूप में कार्यान्वित किया जाता है एक SortedDictionary<TKey, TValue> साथ कुशलता से इस लागू करने के लिए मुश्किल है।

आप निश्चित रूप से "ज्ञात" कुंजी प्राप्त होने तक प्रत्येक KeyValuePair को गिन सकते हैं। LINQ का एक छोटा सा के साथ, इस तरह (यह मानते हुए कुंजी निश्चित रूप से मौजूद है और पहली कुंजी नहीं है) दिखेगा:

SortedDictionary<int, int> dictionary = ... 
int knownKey = ... 

var previousKvp = dictionary.TakeWhile(kvp => kvp.Key != knownKey) 
          .Last(); 

उन मान्यताओं पकड़ नहीं है, तो आप कर सकता है:

var maybePreviousKvp = dictionary.TakeWhile(kvp => kvp.Key != knownKey) 
           .Cast<KeyValuePair<int, int>?>() 
           .LastOrDefault(); 

(चेक maybePreviousKvp != null पता लगाने के लिए कि है कि पिछले KeyValuePair सफलतापूर्वक प्राप्त की गई थी।)

लेकिन इस सब पर कुशल होने के लिए नहीं जा रहा है।

---

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

SortedList<int, int> dictionary = ... 
int knownKey = ... 

int indexOfPrevious = dictionary.IndexOfKey(knownKey) - 1; 

// if "known" key exists and isn't the first key 
if(indexOfPrevious >= 0) 
{ 
    // Wrap these in a KeyValuePair if necessary 
    int previousKey = dictionary.Keys[indexOfPrevious]; 
    int previousValue = dictionary.Values[indexOfPrevious];  
} 

कुंजी-सूची पर एक द्विआधारी खोज चलाता है, O(log n) समय में चल रहे: तो फिर आपकी क्वेरी के रूप में सरल हो जाता है। बाकी सब कुछ निरंतर समय में चलना चाहिए, जिसका अर्थ है कि पूरा ऑपरेशन लॉगरिदमिक समय में चलाना चाहिए।

---

अन्यथा, आपको स्वयं को लागू करना होगा/एक बीएसटी संग्रह ढूंढना होगा जो पूर्ववर्ती/उत्तराधिकारी का पर्दाफाश करता है।

Answer 2

Dictionary<TKey,TValue> अनसुलझा है, इसलिए पिछले कुछ आइटम के लिए चीज़ नहीं है। इसके बजाय आप SortedDictionary<TKey,TValue> का उपयोग कर सकते हैं।

संपादित करें: क्षमा करें, मैंने केवल एलओएल शीर्षक पढ़ा है।

आप उपयोग LINQ करने के लिए है हैं:

int givenKey = 4; 
var previousItem = dict.Where((pair, index) => 
            index == dict.Count || 
            dict.ElementAt(index + 1).Key == givenKey) 
         .FirstOrDefault(); 

Answer 3

आप शब्दकोश के माध्यम से लूप और मूल्यों का ट्रैक रखने के सकता है, मुझे लगता है। कुछ ऐसा:

public int GetPreviousKey(int currentKey, SortedDictionary<int, int> dictionary) 
{ 
    int previousKey = int.MinValue; 
    foreach(KeyValuePair<int,int> pair in dictionary) 
    { 
     if(pair.Key == currentKey) 
     { 
      if(previousKey == int.MinValue) 
      { 
       throw new InvalidOperationException("There is no previous key."); 
      } 
      return previousKey; 
     } 
     else 
     { 
      previousKey = pair.Key; 
     } 
    } 
} 

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

Answer 4

KeyValuePair<int, int> lookingForThis = dictionary 
    .Reverse() 
    .SkipWhile(kvp => kvp.Key != 4) 
    .Skip(1) 
    .FirstOrDefault(); 

Answer 5

यदि यह मामला है तो मैं linq का उपयोग करना पसंद करूंगा ...इसे आज़माएं यह निश्चित रूप से काम करेगा

SortedDictionary<int,int> dictionary = new SortedDictionary<int,int>(); 
dictionary.add(1, 33); 
dictionary.add(2, 20); 
dictionary.add(4, 35); 

int SelectedKey = 4; 

var ResutValue = (from n in dictionary  
       where n.Key < TheSelectedKey 
       select n.Value).Last(); 

this.txtResult.Text = ResultValue.ToString(); 

Answer 6

इसके बारे में कैसे? हालांकि मैंने इसका परीक्षण किया है, लेकिन इस दिशा में सोचने के लिए कुछ देना चाहिए। आशा करता हूँ की ये काम करेगा।

 int input = 4; 
     List<int> lKeys = dictionary.Keys.ToList(); 
     int reqIndex = lKeys.IndexOf(input) - 1; 
     int reqAnswer = dictionary[reqIndex]; 

अन्य स्थितियों के लिए परीक्षण की तरह अगर (reqIndex! = -1) आदि ..

Answer 7

मैं भी इस समस्या का एक जवाब के लिए देख रहा था, और मैं यहाँ जवाब के सभी की तुलना में एक बेहतर समाधान सोचा C5 Collections (GitHub/NuGet) से TreeDictionary<K, V> का उपयोग करना है, जो एक लाल-काले पेड़ का कार्यान्वयन है।

यह Predecessor/TryPredecessor और WeakPredessor/TryWeakPredecessor तरीकों (और साथ ही उत्तराधिकारियों के लिए बराबर विधि) जो करता है आप अपनी ज़रुरत है।

उदाहरण के लिए

:

TreeDictionary<int,int> dictionary = new TreeDictionary<int,int>(); 
dictionary.Add(1,33); 
dictionary.Add(2,20); 
dictionary.Add(4,35); 

// applied to the dictionary itself, returns KeyValuePair<int,int> 
var previousValue = dictionary.Predecessor(4); 
Assert.Equals(previousValue.Key, 2); 
Assert.Equals(previousValue.Value, 20); 

// applied to the keys of the dictionary, returns key only 
var previousKey = dictionary.Keys.Predecessor(4); 
Assert.Equals(previousKey, 2); 

// it is also possible to specify keys not in the dictionary 
previousKey = dictionary.Keys.Predecessor(3); 
Assert.Equals(previousKey, 2);