क्या सॉर्टेडलिस्ट <K ,V> पर लोअर बाउंड फ़ंक्शन है?

Question

क्या SortedList<K ,V> पर लोअर बाउंड फ़ंक्शन है? फ़ंक्शन को निर्दिष्ट कुंजी से बराबर या उससे अधिक पहले तत्व को वापस करना चाहिए। क्या कोई अन्य वर्ग है जो इसका समर्थन करता है?

दोस्तों - कृपया एक बार फिर प्रश्न पढ़ें। मुझे ऐसे फ़ंक्शन की आवश्यकता नहीं है जो मौजूद होने पर कुंजी लौटाए। जब परिदृश्य में कोई सटीक कुंजी मिलान नहीं होता है तो मुझे परिदृश्य में दिलचस्पी है।

मुझे ओ (लॉग एन) समय में रूचि है। इसका मतलब है कि मुझे फोरच लूप के साथ कोई समस्या नहीं है, बल्कि यह करने का एक प्रभावी तरीका है।

मैंने इस पर कुछ परीक्षण किए हैं।

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

public static int FindFirstIndexGreaterThanOrEqualTo<T>(
      this IList<T> sortedCollection, T key 
     ) where T : IComparable<T> { 
    int begin = 0; 
    int end = sortedCollection.Count; 
    while (end > begin) { 
     int index = (begin + end)/2; 
     T el = sortedCollection[index]; 
     if (el.CompareTo(key) >= 0) 
      end = index; 
     else 
      begin = index + 1; 
    } 
    return end; 
} 

Answer 1

द्विआधारी खोज SortedList.Keys संग्रह: Mehrdad Afshari जवाब के आधार पर, यहाँ एक बाइनरी खोजें कि हे में काम करता है (लॉग एन) कुंजी संग्रह पर है।

यहां हम जाते हैं। यह हे है (लॉग n):

private static int BinarySearch<T>(IList<T> list, T value) 
{ 
    if (list == null) 
     throw new ArgumentNullException("list"); 
    var comp = Comparer<T>.Default; 
    int lo = 0, hi = list.Count - 1; 
    while (lo < hi) { 
      int m = (hi + lo)/2; // this might overflow; be careful. 
      if (comp.Compare(list[m], value) < 0) lo = m + 1; 
      else hi = m - 1; 
    } 
    if (comp.Compare(list[lo], value) < 0) lo++; 
    return lo; 
} 

public static int FindFirstIndexGreaterThanOrEqualTo<T,U> 
          (this SortedList<T,U> sortedList, T key) 
{ 
    return BinarySearch(sortedList.Keys, key); 
} 

Answer 2

एक के बारे में पता नहीं है, लेकिन यह एक सरल LINQ बयान है:

first = sortedList.Where(x => x >= theObjectForComparison).FirstOrDefault(); 

first या तो पहले उद्देश्य यह है कि तुलना या default(T) गुजरता हो (जो आमतौर पर null है)।

संपादित

DaveW के संस्करण:

first = sortedList.FirstOrDefault(x => x >= theObjectForComparison); 

एक ही काम करता है लेकिन संभावित तेजी से हो सकता है, आप ही यह परीक्षण करने के लिए होगा।

Answer 3

मैं LINQ के साथ जाना चाहते हैं (आप उपयोग कर रहे मानते हुए सी # 3), लेकिन FirstOrDefault का अधिभार कि एक विधेय लेता है का उपयोग करते हुए:

first = sortedList.FirstOrDefault(x => x >= theObjectForComparison); 

(अन्य Enumerable तरीकों का एक बहुत भी ले जा सकते हैं भविष्यवाणी करता है कि एक अच्छा शॉर्टकट है)

Answer 4

या आप ऐसा करने के लिए अपनी विस्तार विधि लिख सकते हैं। ध्यान दें कि उन सभी कार्यों को एक sequesce में जाने की गारंटी नहीं है।

Answer 5

उम्मीद है कि यह सॉर्टेडलिस्ट के कार्यान्वयन के आधार पर तेज़ होना चाहिए।

public static int FindFirstIndexGreaterThanOrEqualTo<K, V>(
     this SortedList<K, V> sortedCollection, K key 
    ) where V : new() 
{ 
    if (sortedCollection.ContainsKey(key)) 
    { 
     return sortedCollection.IndexOfKey(key); 
    } 
    sortedCollection[key] = new V(); 
    int retval = sortedCollection.IndexOfKey(key); 
    sortedCollection.Remove(key); 
    return retval; 
}