найти предмет в коллекции с ближайшей датой

Question

если у меня есть коллекция дат и значений. Я хочу получить значение, которое либо:

1. Связано с датой в коллекции
2. если его не существует, я хочу линейную интерполяцию между двумя точками, которые находятся вокруг точки, которую я ищу

АО, вот простой пример. Если коллекция:

Date   Value  
1/1/2009   100  
1/1/2010   200  
1/1/2011   300  

если я ищу 6/1/2010, я получу значение обратно 250. Я могу использовать любую коллекцию, если одна лучше в решении, чем другая (словарь, массив и т. Д.)

Answer 1

Вы можете использовать тип 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 для получения дополнительной информации.

List: 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

Answer 2

Учитывая "список дат" и "контрольную дату", получает "ближайшие цифры n". Код C # проверен.

public class ClosestDate
{
    public void GetClosestDate(DateTime referenceDate, 
                                List<DateTime> listDates, int maxResults)
    {
        // final ordered date list
        List<DateTime> finalList = new List<DateTime>();

        DateTime selectedDate = DateTime.MaxValue;

        // loop number of results
        for (int i = 0; i < maxResults; i++)
        {
            // get next closest date
            int tempDistance = int.MaxValue;
            foreach (DateTime currentDate in listDates)
            {
                int currenDistance = this.DateDiff(currentDate, referenceDate);

                if (currenDistance < tempDistance)
                {
                    tempDistance = currenDistance;
                    selectedDate = currentDate;
                }
            }

            // build final list
            finalList.Add(selectedDate);
            // remove element from source list
            listDates.Remove(selectedDate);
        }

        // print results
        foreach (DateTime date in finalList)
        {
            Console.WriteLine(date.ToShortDateString());
        }

    }

    private int DateDiff(DateTime Date1, DateTime Date2)
    {
        TimeSpan time = Date1 - Date2;
        return Math.Abs(time.Days);
    }
}

Answer 3

Будет достаточно простого отсортированного списка (по дате). Просто найдите последнюю дату (назовем ее d1 ), которая меньше или равна дате, которую вы ищете (назовем ее d ). Следующая дата d2 будет проходить после d , при условии, что повторяющихся дат нет.

Теперь, если значение v1 соответствует d1 , а v2 соответствует d2 , то значение, которое вы ищете, равно v1 + ( v2 - v1 ) / ( d2 - d1 ) * ( d - d1 ).

Answer 4

Вы можете попробовать 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)
        ...
    }
}