Il dizionario ordinato personalizza la ricerca delle chiavi per l'efficienza

Question

Recentemente, ho appreso che la classe Sorted Dictionary implementa la ricerca binaria sulle chiavi e volevo usarla a mio vantaggio. Sto creando una classe di funzione lineare a tratti che rappresenta una raccolta di linee su un gruppo di intervalli.

Ho definito una Intervalclasse come questa:

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

E l' SortedDictionaryelemento in questione funziona in questo modo nella classe di funzioni a tratti:

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

Quindi, come puoi vedere, il PiecewiseLinearFunction.FindInterval(double x)metodo ricerca linearmente tra le chiavi del dizionario per trovare l'intervallo che contiene (o non contiene) x, che può essere utilizzato per la ricerca binaria, ma che ovviamente vanifica lo scopo di fare il binario cercare affatto.

Mi chiedevo se potessi in qualche modo fare in modo che il dizionario cerchi double xinvece il valore, e fare una ricerca binaria sugli intervalli controllando se Interval.Contains(double x)è trueo falseper decidere se c'è un intervallo valido (chiave) e una riga corrispondente che può essere utilizzata per ottenere il valore della funzione in x.

In altre parole, c'è un modo per cercare con un predicato, qualcosa di simile FindInterval(double x) => Functions.Keys.FindBinary(i => i.Contains(x)).

Answer 1

Quindi, se gli intervalli non si sovrappongono, in realtà non c'è davvero bisogno di una ricerca binaria personalizzata.

Prima di tutto aiuta se rendiamo Intervalcomparabili a 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;
    }
}

Ora creiamo Listun'estensione in modo da poter eseguire la ricerca binaria con altri tipi, quindi solo il tipo dell'elenco:

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

E ora possiamo testarlo in questo modo:

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