พจนานุกรมเรียงลำดับปรับแต่งการค้นหาคีย์เพื่อประสิทธิภาพ

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