Le dictionnaire trié personnalise la recherche de clés pour plus d'efficacité
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 Interval
classe 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 SortedDictionary
question 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 x
valeur au lieu, et faire une recherche binaire sur les intervalles tout en vérifiant si Interval.Contains(double x)
est true
ou false
de 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
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 Interval
comparable à 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 List
extension 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