ما قاموس .net يدعم عملية "العثور على أقرب مفتاح"؟

Question

أقول بعض كود C ++ إلى C # واتصل STD :: خريطة :: Lower_bound (ك) للعثور على إدخال في الخريطة الذي يساوي مفتاحه أو أكبر من K. ومع ذلك، لا أرى أي طريقة للقيام بنفس الشيء مع SortedCtion. أظن أنه يمكنني تنفيذ الحل البديل باستخدام قائمة فرز، ولكن للأسف أنفرت قائمة بطيئة للغاية (O (N) لإدراج المفاتيح والحذف). ماذا افعل؟

ملاحظة: لقد وجدت حلا باستخدام ذلك يستفيد من سيناريو الخاص بي ... على وجه التحديد، مفاتيحي هي سكان عظيم من الأعداد الصحيحة التي تبدأ من 0، لذلك استخدمت قائمةu003CTValue> بصفتي القاموس مع مؤشر القائمة يعمل بمفتاح، يمكن البحث عن مفتاح يساوي أو أكبر من K فقط في بعض الحلقات. لكنه لا يزال من الجيد أن نرى السؤال الأصلي أجاب.

Answer 1

لقد أنشأت ثلاثة هياكل بيانات تتعلق بأشجار B + التي توفر هذه الوظيفة لأي نوع بيانات: BList<T>, BDictionary<K,V> و BMultiMap<K,V>. وبعد كل هياكل البيانات هذه تقدم FindLowerBound() و FindUpperBound() الأساليب التي تعمل مثل C ++ lower_bound و upper_bound.

Answer 2

استغرق الأمر بضعة أشهر من العمل، ولكن في النهاية يمكنني تقديم حل جزئي على الأقل لهذه المشكلة ... أسميها Trie Patricia المدمجة، وهو قاموس مفروش يوفر تشغيل "العثور على مفتاح أكبر".

http://www.codeproject.com/kb/recipes/cptrie.aspx.

إنه حل جزئي فقط لأن أنواع معينة فقط من المفاتيح مدعومة، وهي byte[], string, ، وجميع أنواع الأعداد الصحيحة البدائية (Int8..uint64). أيضا، فرز السلسلة حساسة لحالة الأحرف.

Answer 3

المشكلة هي أن جدول القاموس / التجزئة مصمم للوصول إلى موقع ذاكرة فريد يستند إلى قيمة الإدخال، لذلك ستحتاج إلى بنية بيانات مصممة لاستيعاب مجموعة تتعلق بكل قيمة تخزنها، وفي نفس الشيء تحديث الوقت كل فاصل زمني بشكل صحيح

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

أعلم أن هذه ليست إجابة مناسبة لأنني لا أستطيع أن أقول أن .NET BCL يحتوي بالفعل على مثل هذه الفئة، سيتعين عليك لسوء الحظ أن تقوم بتنفيذ واحد بنفسك، أو ابحث عن تجميع طرف ثالث يدعمه من أجلك. يبدو أن هناك مثال جميل على التعليمات البروية هنا, ، على أية حال.

Answer 4

يمكنك تجربة الرمز الذي كتبته أدناه. يستخدم البحث الثنائي، وبالتالي يفترض أن القائمة / صفيف مرتبة مسبقا.

public static class ListExtensions
{
    public static int GetAtMostIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer)
    {
        return GetAtMostIndex(list, value, comparer, 0, list.Count);
    }

    public static int GetAtLeastIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer)
    {
        return GetAtLeastIndex(list, value, comparer, 0, list.Count);
    }

    public static int GetAtMostIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer, int index, int count)
    {
        if (count == 0)
        {
            return -1;
        }

        int startIndex = index;
        int endIndex = index + count - 1;
        int middleIndex = 0;
        int compareResult = -1;

        while (startIndex < endIndex)
        {
            middleIndex = (startIndex + endIndex) >> 1; //  / 2
            compareResult = comparer.Invoke(list[middleIndex], value);

            if (compareResult > 0)
            {
                endIndex = middleIndex - 1;
            }
            else if (compareResult < 0)
            {
                startIndex = middleIndex + 1;
            }
            else
            {
                return middleIndex;
            }
        }

        if (startIndex == endIndex)
        {
            compareResult = comparer.Invoke(list[startIndex], value);

            if (compareResult <= 0)
            {
                return startIndex;
            }
            else
            {
                int returnIndex = startIndex - 1;

                if (returnIndex < index)
                {
                    return -1;
                }
                else
                {
                    return returnIndex;
                }
            }
        }
        else
        {
            //todo: test
            return startIndex - 1;
        }
    }

    public static int GetAtLeastIndex<TItem, TValue>(/*this*/ IList<TItem> list, TValue value, Func<TItem, TValue, int> comparer, int index, int count)
    {
        if (count == 0)
        {
            return -1;
        }

        int startIndex = index;
        int endIndex = index + count - 1;
        int middleIndex = 0;
        int compareResult = -1;

        while (startIndex < endIndex)
        {
            middleIndex = (startIndex + endIndex) >> 1; //  / 2
            compareResult = comparer.Invoke(list[middleIndex], value);

            if (compareResult > 0)
            {
                endIndex = middleIndex - 1;
            }
            else if (compareResult < 0)
            {
                startIndex = middleIndex + 1;
            }
            else
            {
                return middleIndex;
            }
        }

        if (startIndex == endIndex)
        {
            compareResult = comparer.Invoke(list[startIndex], value);

            if (compareResult >= 0)
            {
                return startIndex;
            }
            else
            {
                int returnIndex = startIndex + 1;

                if (returnIndex >= index + count)
                {
                    return -1;
                }
                else
                {
                    return returnIndex;
                }
            }
        }
        else
        {
            return endIndex + 1;
        }
    }
}

Answer 5

البحث عن الأقرب إلى K:

dict.Keys.Where(i => i >= K).OrderBy(i => i).First();

أو أسرع بكثير:

public int? GetNearestKey(dict, K) 
{
    int? lowerK = null;
    foreach (int key in dict.Keys)
    {
        if (key == K) 
        {
            lowerK = K;
            break; 
        }
        else if (key >= K && (!lowerK.HasValue || key < lowerK))
        {
            lowerK = key;
        }
    }
    return lowerK;
}

Answer 6

لا يوجد تطبيق مجموعة أدوات بحث ثنائية في الإطار الأساسي، لذلك عليك إما إنشاء واحد أو العثور على تطبيق. كما لاحظت، تكون قائمة الفرز الأقرب من حيث البحث ولكن أبطأ (بسبب تنفيذ صفيفها الأساسي) للإدراج / الحذف.

Answer 7

أعتقد أن هناك خطأ في السؤال حول sortedlist. تعقيد.

sortedlist. لديه o (سجل (n)) تعقيد مطفأ إدراج عنصر جديد. إذا كنت تعرف مقدما، فيمكن القيام به في O (سجل (N)) في أسوأ الحالات.

Answer 8

يمكنك القيام بذلك SortedSet<T> مع طرق التمديد التالية:

public static class SortedSetExtensions
{
    public static bool FindLowerOrEqualThan<T>(this SortedSet<T> set, T value, out T first)
    {
        if(set.Count == 0)
        {
            first = default(T);
            return false;
        }

        var minimum = set.Min;

        if(set.Comparer.Compare(minimum, value) > 0)
        {
            first = default(T);
            return false;
        }

        first = set.GetViewBetween(minimum, value).Max;
        return true;
    }

    public static bool FindGreaterOrEqualThan<T>(this SortedSet<T> set, T value, out T first)
    {
        if (set.Count == 0)
        {
            first = default(T);
            return false;
        }

        var maximum = set.Max;

        if (set.Comparer.Compare(maximum, value) < 0)
        {
            first = default(T);
            return false;
        }

        first = set.GetViewBetween(value, maximum).Min;
        return true;
    }
}