क्रमबद्ध शब्दकोश दक्षता के लिए महत्वपूर्ण लुक-अप को अनुकूलित करता है

Question

हाल ही में, मुझे पता चला कि सॉर्ट किए गए डिक्शनरी क्लास की बाइनरी कुंजियों को खोजती है, और मैं इसका उपयोग अपने लाभ के लिए करना चाहता था। मैं एक टुकड़े-टुकड़े रैखिक फ़ंक्शन क्लास बना रहा हूं जो अंतराल के एक गुच्छा पर लाइनों के संग्रह का प्रतिनिधित्व करता है।

मैंने एक Intervalवर्ग को इस तरह परिभाषित किया :

public class Interval : ICloneable, IComparable, IComparable<Interval>
{
    public Interval()
    {

    }
    public Interval(double start, double end)
    {
        Start = start;
        End = end;
    }

    // Properties
    public double Start { get; set; } = double.NaN;
    public double End { get; set; } = double.NaN;
    public double Span => End - Start;

    // Methods
    public object Clone() => MemberwiseClone();

    public int CompareTo(object obj)
    {
        return Start.CompareTo(obj);
    }

    public int CompareTo([AllowNull] Interval other)
    {
        if (Start < other.Start)
        {
            return -1;
        }
        else if (Start > other.Start)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }

    public bool Contains(double x) => Start <= x && x <= End;
    public override string ToString() => $"[{Start}, {End}]";
}

और SortedDictionaryविचाराधीन कृति इस तरह से कार्य करती है:

public class PiecewiseLinearFunction : ICloneable
{
    ...
    // The dictionary
    public SortedDictionary<Interval, Line2D> Functions { get; set; } = new SortedDictionary<Interval, Line2D>(); // Where Line2D is just a class that contains a function definition for a line

    // Methods
    public Interval FindInterval(double x)
        => Functions.Keys.Where(interval => interval.Contains(x)).FirstOrDefault();
    public double Solve(double x)
    {
        var interval = FindInterval(x);
        if (interval != null && Functions.ContainsKey(interval))
        {
            return Functions[interval].Solve(x);
        }
        else
        {
            return double.NaN;
        }
    }
}

तो जैसा कि आप देख सकते हैं, PiecewiseLinearFunction.FindInterval(double x)विधि शब्दकोश की कुंजियों के माध्यम से रेखीय रूप से खोज करती है ताकि अंतराल (या शामिल नहीं है) को खोजने के लिए x, जिसका उपयोग बाइनरी लुक-अप के लिए किया जा सकता है, लेकिन यह स्पष्ट रूप से बाइनरी करने के उद्देश्य को हरा देता है सब देखते हैं।

मैं सोच रहा था कि क्या मैं किसी तरह डिक्शनरी देखने के double xबजाय मूल्य बना सकता हूं , और यदि कोई वैध अंतराल (कुंजी) है और संबंधित लाइन है जिसे जांचने के लिए इस्तेमाल किया जा सकता है, तो Interval.Contains(double x)यह देखते हुए अंतराल पर एक द्विआधारी खोज करें trueया falseतय करें पर समारोह मूल्य x।

दूसरे शब्दों में, एक विधेय के साथ खोज करने का एक तरीका है, कुछ ऐसा है FindInterval(double x) => Functions.Keys.FindBinary(i => i.Contains(x))।

Answer 1

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

यदि हम इसकी Intervalतुलना करते हैं, तो सबसे पहले यह मदद करता है double:

public class Interval: IComparable<double>
{
    public double Start { get; set; }
    public double End { get; set; }

    public bool Contains(double x) => x >= Start && x <= End;
    public int CompareTo(double other)
    {
        if (Contains(other))
            return 0;
        return other < Start ? 1 : -1;
    }
}

अब हम एक Listएक्सटेंशन बनाते हैं ताकि हम अन्य प्रकारों के साथ बाइनरी खोज कर सकें, फिर सूची के प्रकार:

public static class ListExtensions
{
    public static int BinarySearch<T, TU>(this List<T> sortedSource, TU val) where T : IComparable<TU>
    {
        return sortedSource.BinarySearch(default(T), Comparer<T>.Create((item, _) => item.CompareTo(val)));
    }
}

और अब हम इसे इस तरह से परख सकते हैं:

var list = new List<Interval>
{
    new Interval
    {
        Start = 0,
        End = 4
    },
    new Interval
    {
        Start = 6,
        End = 7
    },
    new Interval
    {
        Start = 10,
        End = 12
    }
};

var index = list.BinarySearch(6.0d); //index = 1
var interval = index < 0 ? null : list[index]; //interval = [6, 7]

index = list.BinarySearch(9.0d); //index = -3
interval = index < 0 ? null : list[index]; //interval = null