C# 二进制搜索列表由 T 的成员

Question

我有一个带有 DateTime 成员 TimeStamp 的基类 Event 。 许多其他事件类将从中派生。

我希望能够快速搜索事件列表，因此我想使用二分搜索。

（列表数据按时间戳排序，但同时发生的事件可能有重复的时间戳）

所以我开始写这样的东西：

public class EventList<T> : List<T> where T : Event
{
   private IComparer<T> comparer = (x, y) => Comparer<DateTime>.Default.Compare(x.TimeStamp, y.TimeStamp);

   public IEnumerable<T> EventsBetween(DateTime inFromTime, DateTime inToTime)
   {
       // Find the index for the beginning. 
       int index = this.BinarySearch(inFromTime, comparer);

       // BLAH REST OF IMPLEMENTATION
   }
}

问题是 BinarySearch 只接受 T （所以 - 一个 Event 类型）作为参数，而我想基于 T 的成员 - 时间戳进行搜索。

解决这个问题的好方法是什么？

Answer 1

我认为您的 comparer 功能已经走在正确的道路上。它通过比较两个 T 的日期来进行比较。

要处理 BinarySearch 的 inFromTime 参数，您可以创建一个具有正确 TimeStamp 的虚拟事件，并将该虚拟事件传递给 BinarySearch.

另外，只是为了确保：列表是否按时间字段排序？否则二分查找将无法工作。

编辑

这个问题比我最初想象的更复杂。一个对您有帮助的解决方案是：

• 创建一个适配器类，将您的 EventList 公开为 IList。
• 使用 IList 上的 BinarySearch 扩展方法进行搜索。

不幸的是，没有内置的 BinarySearch 扩展方法，所以你必须自己写。如果您编写自己的搜索，则可能不值得花费额外的精力将其放入扩展方法中。在这种情况下，您自己在 EventList 类中实现自定义 BinarySearch 算法可能是最好的选择。

另一种选择是，如果有一种 BinarySearch 接受从 T 中提取相关密钥的委托，但这也不可用。

Answer 2

最简单的方法是定义一个实现 IComparer 的小帮助器类。

public class CompUtil : IComparer<T> {
  public int Compare(T left, T right) { 
    return left.TimeStamp.CompareTo(right.TimeStamp);
  }
}

然后您可以按如下方式使用它

int index = this.BinarySearch(inFromTime, new CompUtil());

Answer 3

如果您的 Event 类包含您想要排序的属性，那么您的方法就可以了。然后，编译器可以验证传入的任何 T 是否都将从 Event 继承并包含 DateTime 属性。如果 Event 不包含 DateTime 属性，您可能希望将其添加到事件中，或将 T 限制为更具体的类型，其中包含搜索所需的属性。

请记住在应用二进制搜索之前确保您的列表已排序。

Answer 4

public class EventList<TEvent, TData>
   : List<TEvent> where TEvent : Event, TData: DataTime
{
   class Comparer : IComparer<TData> { } // as JaredPar mentioned above

   public IEnumerable<TEvent> EventsBetween(TData from, TData to) { }
}

Answer 5

也许您可以考虑使用 SortedList 作为基类而不是列表。然后，您可以使用 IndexOfKey 方法搜索指定的时间戳。该方法进行二分搜索。