Сортированный словарь: настройка поиска по ключевым словам для повышения эффективности

Aug 17 2020

Недавно я узнал, что класс 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)).

Ответы

Knoop Aug 17 2020 at 09:34

Так что, если интервалы не перекрываются, на самом деле нет необходимости в настраиваемом двоичном поиске.

В первую очередь поможет, если мы сделаем 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