Sıralanmış Sözlük verimlilik için anahtar aramayı özelleştirir

Aug 17 2020

Son zamanlarda, Sıralı Sözlük sınıfının tuşlar üzerinde ikili arama yaptığını öğrendim ve bunu kendi avantajım için kullanmak istedim. Bir grup aralıkta bir çizgi koleksiyonunu temsil eden parçalı bir doğrusal fonksiyon sınıfı yapıyorum .

Şöyle bir Intervalsınıf tanımladım :

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

Ve SortedDictionarysöz konusu parça parçalı fonksiyon sınıfında şu şekilde çalışır:

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

Gördüğünüz gibi, PiecewiseLinearFunction.FindInterval(double x)yöntem x, ikili arama için kullanılabilen (veya içermeyen) aralığı bulmak için sözlüğün anahtarları arasında doğrusal olarak arama yapar , ancak bu açık bir şekilde ikili dosya yapma amacını bozar. hiç bak.

Bir şekilde yukarı Sözlük göz yapabiliriz acaba double xyerine değeri ve aralıkları üzerinde bir ikili arama yaparsanız kontrol ederken Interval.Contains(double x)olduğunu trueveya falsegeçerli bir aralık (anahtar) ve get için kullanılabilecek bir karşılık gelen çizgi varsa karar vermek işlev değeri x.

Başka bir deyişle, bir yüklemle arama yapmanın bir yolu var mı, gibi bir şey FindInterval(double x) => Functions.Keys.FindBinary(i => i.Contains(x)).

Yanıtlar

Knoop Aug 17 2020 at 09:34

Dolayısıyla, aralıklar çakışmazsa, aslında özel bir ikili aramaya ihtiyaç yoktur.

Her şeyden önce aşağıdakileri Intervalkarşılaştırabilirsek yardımcı olur 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;
    }
}

Şimdi bir Listuzantı oluşturuyoruz, böylece diğer türlerle ikili arama yapabiliyoruz, ardından sadece listenin türü:

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

Ve şimdi bunu şu şekilde test edebiliriz:

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