LINQ查询 - 最近相邻日期

Question

我正在尝试编写一个方法，该方法将确定最接近给定日期的日期，给定一组日期和目标日期。例如，给定一个（简化的）日期集{2011年1月，2011年3月，2011年11月}和目标日期为2011年4月，该方法将返回2011年3月。

起初，我考虑使用LINQ的skip函数，但我不确定适当的Func是否会在超过日期之前停止。下面的代码似乎是可行的解决方案，但我不确定是否有更有效的方法来实现这一点。假设Last和First每次都是线性时间。

源数据集可以包含0到10,000个日期，通常约为5,000个。此外，我将在5到50次迭代中遍历整个过程（这是不同迭代的目标日期数）。

// assume dateSet are ordered ascending in time.
public DateTime GetClosestDate(IEnumerable<DateTime> dateSet, DateTime targetDate)
{
   var earlierDate = dateSet.Last(x => x <= targetDate);
   var laterDate = dateSet.First(x => x >= targetDate);

   // compare TimeSpans from earlier to target and later to target.
   // return closestTime;
}

- Stealth Rabbi

Answer 1

使用 MinBy 函数，该函数来自于 MoreLINQ 库:

var nearest = dateSet.MinBy(date => Math.Abs((date - targetDate).Ticks);

换句话说，对于每个日期，通过相互减去（无论哪种方式），取得所得到的TimeSpan中的Ticks数量，并找出其绝对值。选择差异最小的日期。

如果不能使用MoreLINQ，则可以编写类似的代码，或者进行两步操作：

var nearestDiff = dateSet.Min(date => Math.Abs((date - targetDate).Ticks));
var nearest = dateSet.Where(date => Math.Abs((date - targetDate).Ticks) == nearestDiff).First();

- Jon Skeet

---

没有MoreLINQ，可以使用其他LINQ表达式进行相同的算术运算：return dateSet.OrderBy(date => Math.Abs((date - targetDate).Ticks)).First(); - Mike Mertsock

@esker：这样做可以解决问题，但它需要O(N) 的内存和O(N log N) 的时间，而不是O(1) 的内存和O(N) 的时间。在我看来，这基本上是不优雅的 :) 但是没错，也许这就是所需的一切... - Jon Skeet

@Skeet，你说的是“O(1)内存和O(N)”是什么意思？是指你的解决方案，还是使用MinBy函数？ - Stealth Rabbi

我对确定大O符号有点生疏。你的算法需要O(2n)的时间，对吗？它必须遍历一次列表来获取nearestDiff，然后再遍历一次来查找最近的元素？ 我猜esker的答案中N Log N是来自OrderBy子句。LINQ的排序需要n log n的时间？ - Stealth Rabbi

@Stealth Rabbi：O(2n) == O(n)，只是不同的常数因子。 - Jon Skeet

Answer 2

使用Last和First会迭代dateSet两次。您可以使用自己的逻辑迭代dateSet。这样会更有效率，但除非您的dateSet非常大或者枚举dateSet因某些其他原因非常昂贵，否则在速度上获得的小优势可能不值得编写更复杂的代码。您的代码应该首先易于理解。

- Olivier Jacot-Descombes

---

源数据集可以在0到10,000个日期之间，通常约为5,000个。此外，我会在5到50次迭代中遍历整个过程（这是不同迭代的目标日期数）。我将把这添加到描述中。 - Stealth Rabbi

Answer 3

这很简单！

List<DateTime> MyDateTimeList =....;
....

getNearest(DateTime dt)
{
   return MyDateTimeList.OrderBy(t=> Math.ABS((dt-t).TotalMiliSeconds)).First();
}

- Amir Alizade

---

请查看被接受答案下面的讨论，说明为什么这并不是一个改进，事实上应该被反对。 - Gert Arnold