Sıralanmış Sözlük verimlilik için anahtar aramayı özelleştirir
Son zamanlarda, Sıralı Sözlük sınıfının tuşlar üzerinde ikili arama yaptığını öğrendim ve bunu kendi avantajım için kullanmak istedim. Bir grup aralıkta bir çizgi koleksiyonunu temsil eden parçalı bir doğrusal fonksiyon sınıfı yapıyorum .
Şöyle bir Interval
sınıf tanımladım :
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}]";
}
Ve SortedDictionary
söz konusu parça parçalı fonksiyon sınıfında şu şekilde çalışır:
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;
}
}
}
Gördüğünüz gibi, PiecewiseLinearFunction.FindInterval(double x)
yöntem x
, ikili arama için kullanılabilen (veya içermeyen) aralığı bulmak için sözlüğün anahtarları arasında doğrusal olarak arama yapar , ancak bu açık bir şekilde ikili dosya yapma amacını bozar. hiç bak.
Bir şekilde yukarı Sözlük göz yapabiliriz acaba double x
yerine değeri ve aralıkları üzerinde bir ikili arama yaparsanız kontrol ederken Interval.Contains(double x)
olduğunu true
veya false
geçerli bir aralık (anahtar) ve get için kullanılabilecek bir karşılık gelen çizgi varsa karar vermek işlev değeri x
.
Başka bir deyişle, bir yüklemle arama yapmanın bir yolu var mı, gibi bir şey FindInterval(double x) => Functions.Keys.FindBinary(i => i.Contains(x))
.
Yanıtlar
Dolayısıyla, aralıklar çakışmazsa, aslında özel bir ikili aramaya ihtiyaç yoktur.
Her şeyden önce aşağıdakileri Interval
karşılaştırabilirsek yardımcı olur 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;
}
}
Şimdi bir List
uzantı oluşturuyoruz, böylece diğer türlerle ikili arama yapabiliyoruz, ardından sadece listenin türü:
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)));
}
}
Ve şimdi bunu şu şekilde test edebiliriz:
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