найдите объект в наборе с самой близкой датой
если у меня есть набор дат и значений. Я хочу получить значение, которое является также:
- Связанный с датой в наборе
- если это не существует, я хочу линейную интерполяцию между двумя точками, которые являются вокруг точки, которую я ищу
АО, вот простой пример. Если набор:
Date Value
1/1/2009 100
1/1/2010 200
1/1/2011 300
если бы я ищу 01.06.2010, я получил бы значение назад 250. я могу использовать любой набор, если Вы лучше в решении, чем другой (словарь, массив, и т.д.)
3 ответа
Достаточно простого отсортированного (по дате) списка. Просто найдите последнюю дату (назовем ее d1 ), которая меньше или равна дате, которую вы ищете (назовем ее d ). Следующая дата d2 будет после d , при условии, что нет повторяющихся дат.
Теперь, если значение v1 соответствует d1 , а v2 соответствует d2 , тогда значение, которое вы ищете, будет v1 + ( v2 - v1 ) / ( d2 - d1 ) * ( d - d1 ).
Вы можете попробовать SortedDictionary. Сделайте что-то вроде этого:
int FindInterpolated(DateTime needle)
{
try
{
DateTime lower = haystack.First(key => haystack[key] <= needle);
DateTime upper = haystack.Last(key => haystack[key] >= needle);
int v1 = haystack[lower];
int v2 = haystack[upper];
long ticksLower = lower.Ticks;
long ticksUpper = upper.Ticks;
return (v1 * ticksLower + v2 * ticksUpper) / (ticksLower + ticksUpper);
}
catch (InvalidOperationException)
{
// thrown if needle is out of range
// (not between smallest and biggest keys in the haystack)
...
}
}
Вы можете использовать тип List для хранения пар, сортировать их и использовать List.BinarySearch.
Например, вы можете получить что-то вроде следующего:
struct Pair
{
public Pair(DateTime t, int v)
{
date = t;
value = v;
}
public DateTime date;
public int value;
}
....
List<Pair> pairs = new List<Pair>();
pairs.Add(new Pair(DateTime.Now, 100));
pairs.Add(new Pair(DateTime.Now, 200));
....
// Sort using the time.
pairs.Sort(delegate(Pair pair1, Pair pair2) {
return pair1.date.CompareTo( pair2.date);
}
);
// Do binary search.
int index = pairs.BinarySearch(new Pair(dateToSearch, 0),
delegate(Pair pair1, Pair pair2) {
return pair1.date.CompareTo(pair2.date);
});
if (index >= 0) {
// Found the element!
return pairs[index].value;
}
// If not found, List.BinarySearch returns the complement
// of the index where the element should have been.
index = ~index;
// This date search for is larger than any
if (index == pairs.Count) {
//
}
// The date searched is smaller than any in the list.
if (index == 0) {
}
// Otherwise return average of elements at index and index-1.
return (pairs[index-1].value + pairs[index].value)/2;
Конечно, код не самый лучший из возможных, но вы поняли идею: используйте List, сортируйте его, а затем выполняйте BinarySearch.
Дополнительную информацию можно найти в MSDN.
Список: http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx
List.Sort: http://msdn.microsoft.com/en-us/library/3da4abas.aspx
List.BinarySearch: http://msdn.microsoft.com/en-us/library/3f90y839.aspx