在最近日期的集合中查找项目

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以获取更多信息.

列表: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

一个简单的排序（按日期）列表就足够了。只需找到小于或等于您要查找的日期（我们称之为 d ）的最后一个日期（我们称之为d1 ）。假设没有重复的日期，下一个日期d2将超过d 。

现在，如果值v1对应于d1，v2对应于d2，那么您要查找的值是v1 + ( v2 - v1 ) / ( d2 - d1 ) * ( d - d1 )。