5

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

我希望能够快速搜索事件列表，所以我想使用二进制搜索。

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

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

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的成员- TimeStamp进行搜索。

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

4

5 回答 5

1

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

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

另外，只是为了确保：列表是否按时间字段排序？否则二进制搜索将不起作用。

编辑

这个问题比我最初想象的要复杂。可以帮助您的解决方案是：

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

不幸的是，没有内置的BinarySearch 扩展方法，因此您必须自己编写。如果您编写自己的搜索，那么将其放入扩展方法中可能不值得付出额外的努力。在这种情况下，您自己在 EventList 类中实现自定义 BinarySearch 算法可能是您能做的最好的事情。

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

于 2010-04-02T09:17:45.133 回答
0

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

于 2010-04-02T10:36:47.580 回答
0

最简单的方法是定义一个实现IComparer<T>. 

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());
于 2010-04-02T09:20:35.253 回答
0

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

请记住在应用 BinarySearch 之前确保您的列表已排序。

于 2010-04-02T09:23:54.123 回答
0 
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) { }
}
于 2010-04-02T09:58:30.500 回答