ソートされた辞書は効率のためにキールックアップをカスタマイズします

Question

最近、Sorted Dictionaryクラスがキーのバイナリ検索を実装していることを知り、これを有利に使用したいと思いました。一連の区間にわたる行のコレクションを表す区分的線形関数クラスを作成しています。

私は次の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