Sorted Dictionary menyesuaikan pencarian kunci untuk efisiensi

Aug 17 2020

Baru-baru ini, saya mengetahui bahwa kelas Sorted Dictionary mengimplementasikan pencarian biner di atas kunci, dan saya ingin menggunakan ini untuk keuntungan saya. Saya membuat kelas fungsi linier sepotong - sepotong yang merepresentasikan kumpulan garis pada banyak interval.

Saya mendefinisikan Intervalkelas seperti ini:

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

Dan yang SortedDictionarydimaksud bekerja seperti ini di kelas fungsi pemenggalan:

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

Jadi seperti yang Anda lihat, PiecewiseLinearFunction.FindInterval(double x)metode ini mencari secara linier melalui kunci kamus untuk menemukan interval yang berisi (atau tidak berisi) x, yang dapat digunakan untuk pencarian biner, tetapi itu jelas mengalahkan tujuan melakukan biner. lihat semua.

Saya bertanya-tanya apakah saya bisa membuat kamus mencari double xnilainya, dan melakukan pencarian biner selama interval sambil memeriksa apakah Interval.Contains(double x)ada trueatau falseuntuk memutuskan apakah ada interval yang valid (kunci) dan baris yang sesuai yang dapat digunakan untuk mendapatkan nilai fungsi pada x.

Dengan kata lain, apakah ada cara untuk mencari dengan predikat, seperti FindInterval(double x) => Functions.Keys.FindBinary(i => i.Contains(x)).

Jawaban

Knoop Aug 17 2020 at 09:34

Jadi, jika intervalnya tidak tumpang tindih, sebenarnya tidak diperlukan pencarian biner kustom.

Pertama-tama akan membantu jika kita membuat Intervalperbandingan dengan 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;
    }
}

Sekarang kami membuat Listekstensi sehingga kami dapat melakukan pencarian biner dengan jenis lain lalu hanya jenis daftar:

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

Dan sekarang kita bisa mengujinya seperti ini:

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