هل هناك وظيفة مقدمة منخفضة على قائمة تصنيف ؟

Question

هل هناك وظيفة منصة أقل على SortedList<K ,V>ب يجب أن تعيد الوظيفة العنصر الأول مساويا أو أكبر من المفتاح المحدد. هل هناك بعض الطبقة الأخرى التي تدعم هذا؟

الرجال - يرجى قراءة السؤال مرة أخرى. لا أحتاج إلى وظيفة إرجاع المفتاح إذا كان موجودا. أنا مهتم بالسيناريو عندما لا يكون هناك مطابقة رئيسية دقيقة.

أنا مهتم بوقت O (سجل ن). وبعد هذا يعني أنني لا أملك مشكلة في حل الحلقة، بل ترغب في الحصول على طريقة فعالة للقيام بذلك.

لقد فعلت بعض الاختبارات على هذا.

لا يتم تحسين بيانات LinQ من خلال عدم تحسين جهاز التحويل البرمجي أو وقت التشغيل، لذلك يمشيون جميع عناصر المجموعة وبطيئة O (n). بناء على إجابة Mehrdad Afshari، إليك بحث ثنائي يعمل في O (Log N) في مجموعة المفاتيح:

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 مجموعة.

ها نحن. هذا هو O (سجل ن):

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 (افتراض أنك تستخدم C # 3)، ولكن باستخدام الحمل الزائد من Firstordefault الذي يأخذ المسند:

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

(يمكن للكثير من الطرق العديدة الأخرى أن تتخذ المسندات التي هي اختصار لطيف)

Answer 3

غير مدرك واحد، لكنه عبارة LINQ بسيطة:

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

first سيكون إما أن يكون أول كائن يمر بالمقارنة أو default(T) (وهو عادة null).

يحرر

نسخة davew:

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

هل نفس الوظيفة ولكن من الممكن أن تكون أسرع، سيتعين عليك اختبارها.

Answer 4

أو يمكنك كتابة طريقة تمديد الخاصة للقيام بذلك. لاحظ أن كل هذه الوظائف غير مضمونة للذهاب في سلسلة تغيير.

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;
}