在字典中找到最接近的日期时间键<日期时间，双精度>

Question

我将DateTime的Date部分作为查找值，并希望在类型为Dictionary<DateTime, double>的Dictionary中检索匹配值。请注意，DateTime键仅存储为Date部分。

我的问题是可能没有键与我的查找值匹配。然后我想做的是找到最近的先前的 dateTime。日期键和匹配值。

现在，我知道字典不是按键排序的。我可以使用SortedDictionary，但出于特定原因更喜欢使用Dictionary，或者切换到List集合(可以预先排序)。我的问题是，在这种情况下，您会建议怎么做:保留Dictionary结构并递减查找值，直到找到匹配的键，这样会更有效吗?或者使用列表集合并使用Linq会更好吗?每个Dictionary包含大约5000个键/值对。另外，请注意，我寻找的是一种计算效率很高的解决方案，因为查找的频率非常高(可能是数十万次(每次查找都保证与之前的任何值不同)

Answer 1

既然你需要它快，我认为最好的事情是使用BinarySearch的结果。这需要排序的List<T>。

int result = myList.BinarySearch(targetDate);
if (result >= 0)
    return myList[result];
else
{
    int nextLarger = ~result;
    // return next smaller, or if that doesn't exist, the smallest one
    return myList[Math.Max(0, nextLarger - 1)];
}

应该可以创建一个类，它将Dictionary<TKey,TValue>和排序后的List<TKey>结合起来，并且仍然像Dictionary<TKey,TValue>一样序列化。序列化可能很简单(在Json.NET中)，只需在类中添加一个[JsonConverter(typeof(KeyValuePairConverter))]。

为了完整起见，如果速度不是很重要，你可以更简单地这样做:

var result = myDict.Keys.Where(x => x < targetDate).Max();

Answer 2

我将使用自定义结构和集合来存储这些信息:

public struct DateValue
{
    public DateValue(DateTime date, double val)
        : this()
    {
        this.Date = date;
        this.Value = val;
    }
    public DateTime Date { get; set; }
}

这是一个集合的可能实现，它保存所有DateValues并封装逻辑以返回最接近的。它使用List.BinarySearch来查找它。如果没有找到直接匹配，则使用BinarySearch的逻辑来检测最近的匹配，即:

指定数组中指定值的索引，如果value为发现。如果未找到value，且value小于一个或多个数组中的元素，一个负数，它是按位补码第一个大于value的元素的索引。如果价值未找到且value大于数组中的任何元素，a的索引的位补数最后一个元素加1)

public class DateValueCollection : List<DateValue>, IComparer<DateValue>
{
    public DateValueCollection() { }
    public DateValueCollection(IEnumerable<DateValue> dateValues, bool isOrdered)
    {
        if (isOrdered)
            base.AddRange(dateValues);
        else
            base.AddRange(dateValues.OrderBy(dv => dv.Date));
    }
    public DateValue GetNearest(DateTime date)
    {
        if (base.Count == 0)
            return default(DateValue);
        DateValue dv = new DateValue(date, 0);
        int index = base.BinarySearch(dv, this);
        if (index >= 0)
        {
            return base[index];
        }
        // If not found, List.BinarySearch returns the complement of the index
        index = ~index;
        DateValue[] all;
        if(index >= base.Count - 1)
        {
            // proposed index is last, check previous and last
            all = new[] { base[base.Count - 1], base[base.Count - 2] };
        }
        else if(index == 0)
        {
            // proposed index is first, check first and second
            all = new[] { base[index], base[index + 1] };
        }
        else
        {
            // return nearest DateValue from previous and this
            var thisDV = base[index];
            var prevDV = base[index - 1];
            all = new[]{ thisDV, prevDV };
        }
        return all.OrderBy(x => (x.Date - date).Duration()).First();
    }
    public int Compare(DateValue x, DateValue y)
    {
        return x.Date.CompareTo(y.Date);
    }
}

快速测试:

var dateVals = new[] { 
    new DateValue(DateTime.Today.AddDays(10), 1), new DateValue(DateTime.Today, 3), new DateValue(DateTime.Today.AddDays(4), 7) 
};
var dvCollection = new DateValueCollection(dateVals, false);
DateValue nearest = dvCollection.GetNearest(DateTime.Today.AddDays(1));

Answer 3

何必过早担心优化问题

do it

THEN AND ONLY THEN如果它慢，那么你就有问题了用分析器来测量它

然后开始理解，然后尝试其他方法并分析它们

答案是:如果你用任何一种方式来做，并且没有性能问题，那么你只是节省了时间，并且设法做了一些其他有用的事情，为你的一天增加了价值。

不成熟的优化不仅没有意义，你通常会完全错误地判断你应该在哪里寻找