Le dictionnaire trié personnalise la recherche de clés pour plus d'efficacité

Aug 17 2020

Récemment, j'ai appris que la classe Sorted Dictionary implémentait une recherche binaire sur les clés, et je voulais l'utiliser à mon avantage. Je crée une classe de fonctions linéaires par morceaux qui représente une collection de lignes sur un tas d'intervalles.

J'ai défini une Intervalclasse comme celle-ci:

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

Et la SortedDictionaryquestion en question fonctionne comme ceci dans la classe de fonctions par morceaux:

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

Ainsi, comme vous pouvez le voir, la PiecewiseLinearFunction.FindInterval(double x)méthode recherche linéairement dans les clés du dictionnaire afin de trouver l'intervalle qui contient (ou ne contient pas) x, qui peut être utilisé pour la recherche binaire, mais qui va évidemment à l'encontre de l'objectif de faire le binaire recherche du tout.

Je me demandais si je pouvais faire en quelque sorte le regard dictionnaire la double xvaleur au lieu, et faire une recherche binaire sur les intervalles tout en vérifiant si Interval.Contains(double x)est trueou falsede décider s'il y a un intervalle valide (touche) et une ligne correspondante qui peut être utilisé pour obtenir la valeur de la fonction à x.

En d'autres termes, existe-t-il un moyen de rechercher avec un prédicat, quelque chose comme FindInterval(double x) => Functions.Keys.FindBinary(i => i.Contains(x)).

Réponses

Knoop Aug 17 2020 at 09:34

Donc, si les intervalles ne se chevauchent pas, une recherche binaire personnalisée n'est en fait pas vraiment nécessaire.

Tout d'abord, il est utile de rendre Intervalcomparable à 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;
    }
}

Maintenant, nous créons une Listextension afin que nous puissions faire une recherche binaire avec d'autres types puis juste le type de la liste:

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

Et maintenant, nous pouvons le tester comme ceci:

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