Sorted Dictionary menyesuaikan pencarian kunci untuk efisiensi
Baru-baru ini, saya mengetahui bahwa kelas Sorted Dictionary mengimplementasikan pencarian biner di atas kunci, dan saya ingin menggunakan ini untuk keuntungan saya. Saya membuat kelas fungsi linier sepotong - sepotong yang merepresentasikan kumpulan garis pada banyak interval.
Saya mendefinisikan Interval
kelas seperti ini:
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}]";
}
Dan yang SortedDictionary
dimaksud bekerja seperti ini di kelas fungsi pemenggalan:
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;
}
}
}
Jadi seperti yang Anda lihat, PiecewiseLinearFunction.FindInterval(double x)
metode ini mencari secara linier melalui kunci kamus untuk menemukan interval yang berisi (atau tidak berisi) x
, yang dapat digunakan untuk pencarian biner, tetapi itu jelas mengalahkan tujuan melakukan biner. lihat semua.
Saya bertanya-tanya apakah saya bisa membuat kamus mencari double x
nilainya, dan melakukan pencarian biner selama interval sambil memeriksa apakah Interval.Contains(double x)
ada true
atau false
untuk memutuskan apakah ada interval yang valid (kunci) dan baris yang sesuai yang dapat digunakan untuk mendapatkan nilai fungsi pada x
.
Dengan kata lain, apakah ada cara untuk mencari dengan predikat, seperti FindInterval(double x) => Functions.Keys.FindBinary(i => i.Contains(x))
.
Jawaban
Jadi, jika intervalnya tidak tumpang tindih, sebenarnya tidak diperlukan pencarian biner kustom.
Pertama-tama akan membantu jika kita membuat Interval
perbandingan dengan 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;
}
}
Sekarang kami membuat List
ekstensi sehingga kami dapat melakukan pencarian biner dengan jenis lain lalu hanya jenis daftar:
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)));
}
}
Dan sekarang kita bisa mengujinya seperti ini:
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