"आयु-रिकॉर्ड" डेटास्ट्रक्चर

Question

मैं एक डेटास्ट्रक्चर खोज रहा हूं जो एग्रीकॉर्ड सूची की तरह काम करता है। यदि आपके पास कोई भी उच्च अंक नहीं है तो आपके पास एक agerecord है।

तो मुझे जोड़े (ए, बी) की एक सूची चाहिए, जहां निहितार्थ के बाद सभी जोड़े (ए 1, बी 1) और (ए 2, बी 2) के लिए ए 1> ए 2 => बी 1> बी 2 होता है।

एक प्रविष्टि विधि डालने होनी चाहिए (a_new, b_new) कि सम्मिलित करता है (a_new, b_new) वहाँ एक जोड़ी मौजूद नहीं है अगर (a_k, b_k) a_k < ऐसी है कि a_new लेकिन b_k> b_new। यदि यह मानदंड संतुष्ट है तो नई जोड़ी डाली गई है और सूची से सभी जोड़े जैसे कि a_k> a_new लेकिन b_k < b_new हटा दिए गए हैं।

डेटास्ट्रक्चर को हटाने का समर्थन करने की आवश्यकता नहीं है।

Answer 1

यहां एक सामान्य समाधान है जो मुझे लगता है कि आपके लिए नौकरी होगी। यह प्रदर्शन के लिए अनुकूलित नहीं है, और न ही यह विशेष रूप से अच्छी तरह से परीक्षण किया गया है।

public class AgePair<T, Y> 
    where T : IComparable<T> 
    where Y : IComparable<Y> 
{ 
    public T A { get; set; } 

    public Y B { get; set; } 
} 

public class AgeRecordList<T, Y> : IEnumerable<AgePair<T,Y>> 
    where T : IComparable<T> 
    where Y : IComparable<Y> 
{ 
    private List<AgePair<T, Y>> m_List = new List<AgePair<T, Y>>(); 

    public void Add(T a, Y b) 
    { 
     AgePair<T, Y> newPair = new AgePair<T, Y> { A = a, B = b }; 

     // Get all elements that are younger 
     var younger = GetYounger(newPair.A); 

     // Find any of the younger with a higher score 
     // If found, return without inserting the element 
     foreach (var v in younger) 
     { 
      if (v.B.CompareTo(newPair.B) >= 0) 
      { 
       return; 
      } 
     } 

     // Cache elements to delete 
     List<AgePair<T, Y>> toDelete = new List<AgePair<T, Y>>(); 

     // Find all the elder elements  
     var elder = GetElder(newPair.A); 

     // Find all elder elements with a lower B 
     foreach (var v in elder) 
     { 
      if (v.B.CompareTo(newPair.B) <= 0) 
      { 
       // Mark for delete 
       toDelete.Add(v); 
      } 
     } 

     // Delete those elements found above 
     foreach (var v in toDelete) 
     { 
      m_List.Remove(v); 
     } 

     // Add the new element 
     m_List.Add(newPair); 

     // Sort the list (ascending by A) 
     m_List.Sort(CompareA); 
    } 

    private List<AgePair<T, Y>> GetElder(T t) 
    { 
     List<AgePair<T, Y>> result = new List<AgePair<T, Y>>(); 

     foreach (var current in m_List) 
     { 
      if (t.CompareTo(current.A) <= 0) 
      { 
       result.Add(current); 
      } 
     } 

     return result; 
    } 

    private List<AgePair<T, Y>> GetYounger(T t) 
    { 
     List<AgePair<T, Y>> result = new List<AgePair<T, Y>>(); 

     foreach (var current in m_List) 
     { 
      if (t.CompareTo(current.A) > 0) 
      { 
       result.Add(current); 
      } 
     } 

     return result; 
    } 

    private static int CompareA(AgePair<T,Y> item1, AgePair<T,Y> item2) 
    { 
     return item1.A.CompareTo(item2.A); 
    } 


    public IEnumerator<AgePair<T, Y>> GetEnumerator() 
    { 
     return m_List.GetEnumerator(); 
    } 

} 

संपादित करें 1: एल्गोरिथ्म के उच्च स्तरीय अवलोकन

1. सभी युवा या बराबर तत्वों का पता लगाएं,
2. सभी युवा या बराबर तत्वों के लिए, यदि किसी भी एक उच्च बी
3. तो देखने (2) वापसी
4. सभी बड़े तत्वों को खोजें
5. यदि किसी भी बड़े तत्व के पास कम स्कोर है, तो
हटाएं
6. क्रमबद्ध आरोही क्रम में सूची (ए द्वारा)

संपादित करें 2: गति आसानी से एक द्वारा बढ़ाया जा सकता) एक बार आप छोटी तत्व मिले, तो आप उस बिंदु से जारी रख सकते हैं जब बजाय बड़े तत्वों की तलाश में सभी को फिर से शुरू करना, और बी) सॉर्ट विधि सूची का उपयोग करके इसे क्रमबद्ध करने के बजाय, आप InsertAt (0 या प्रथम बुजुर्ग की अनुक्रमणिका)

Answer 2

का उपयोग कर सकते हैं यह एजलिस्ट प्रत्येक आयु के लिए सर्वश्रेष्ठ रिकॉर्ड का ट्रैक रखती है, फिर अनदेखा करती है विजेताओं के लिए पूछे जाने वाले युग में agerecords नहीं है।

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

यदि समय उपलब्ध होने पर अंतरिक्ष प्रीमियम पर है, तो GetWinners विधि के समान एक क्लीनअप विधि लिखना आसान है। प्रत्येक सम्मिलन के बाद साफ करने के लिए InsertMethod से भी बुलाया जा सकता है।

public class AgeList<T, U> where T:IComparable<T> where U:IComparable<U> 
{ 
    Dictionary<T, U> store = new Dictionary<T, U>(); 

    public void Insert(T a, U b) 
    { 
     if (!store.ContainsKey(a) || store[a].CompareTo(b) < 0) 
     { 
      store[a] = b; 
     } 
     //else discard by doing nothing 
    } 

    public IEnumerable<KeyValuePair<T, U>> GetWinners() 
    { 
     bool first = true; 
     U record = default(U); 
     foreach(T key in store.Keys.OrderBy(t => t)) 
     { 
      U newValue = store[key]; 
      if (first) 
      { 
       first = false; 
       record = newValue; 
       yield return new KeyValuePair<T, U>(key, record); 
      } 
      else if (record.CompareTo(newValue) < 0) 
      { 
       record = newValue; 
       yield return new KeyValuePair<T, U>(key, record); 
      } 
     } 
    } 
}