C＃二分查找列表＆LT; T＆GT;由T的成员 [英] C# binarysearch a list<T> by a member of T

问题描述

我有一个基类事件与的DateTime 成员时间戳。
其他事件类地段将获得来源于此。

I have a baseclass Event with a DateTime member TimeStamp. Lots of other event-classes will derive from this.

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

I want to be able to search a list of events fast, so I'd like to use a binary search.

（该表数据被排序时间戳，但有可能是重复的时间戳为同时发生的事件）

(The list-data is sorted on timestamp, but there might be duplicate timestamps for events that occurred simultaneously)

于是我开始写是这样的：

So I started out writing something like this :

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
   }
}

问题是，二分查找只接受T（让 - 一个事件输入）作为参数，而我要搜索一个基于的成员 - 在时间戳的

The problem is that the BinarySearch only accepts T (so - an Event type) as parameter, while I want to search based on a member of T - the TimeStamp.

什么是解决这个好办法？

What would be a good way to approach this ?

推荐答案

我觉得你已经是在以正确的方式与你的比较器功能。它通过比较它们的日期比较两个T的。

I think that you already are on the right way with your comparer function. It compares two T's by comparing the dates of them.

要处理 inFromTime 参数二分查找您可以创建一个具有正确的<$ C $的虚拟事件C>时间戳并传递假人二分查找。

To handle the inFromTime parameter to BinarySearch you can create a dummy Event which has the correct TimeStamp and pass that dummy to BinarySearch.

另外，公正，以确保：是对列表进行排序的时间字段？否则二分查找将无法工作。

Also, just to make sure: Is the list sorted on the time field? Otherwise binarysearch won't work.

这个问题更加复杂，比我第一个念头。一个解决方案，这将有助于你的是：

This problem is more complex than I first thought. A solution that would help you is:

• 请适配器类它暴露你的EVENTLIST作为一个IList。


• 使用上IList中BinarySearch的扩展方法做搜索。

不幸的是没有内置的<一个href=\"http://stackoverflow.com/questions/967047/how-to-perform-a-binary-search-on-ilistt\">BinarySearch扩展方法，所以你必须写自己的。如果你写你自己的搜索它可能不值得额外的努力把它放在一个扩展方法。在这种情况下，只是实现自定义的二分查找算法，自己在你的类事件列表可能是你能做的最好的。

Unfortunately there is no built in BinarySearch extension method, so you will have to write your own. In case you write your own search it might not be worth the extra effort to put it in an extension method. In that case just implementing a custom BinarySearch algorithm yourself in your EventList class is probably the best you can do.

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

Another option would be if there was a form of BinarySearch that accepted a delegate that extracts the relevant key from T, but that is not available either.

这篇关于C＃二分查找列表＆LT; T＆GT;由T的成员的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！