C # binarysearch список <T>членом T - PullRequest
Новая
       38

C # binarysearch список <T>членом T

5 голосов
/ 02 апреля 2010

У меня есть базовый класс 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 .

Каким будет хороший способ приблизиться к этому?

Ответы [ 5 ]

1 голос
/ 02 апреля 2010

Я думаю, что вы уже на правильном пути с вашей функцией comparer. Он сравнивает два T, сравнивая даты их.

Чтобы обработать параметр inFromTime для BinarySearch, вы можете создать фиктивное событие с правильным значением TimeStamp и передать его в BinarySearch.

Кроме того, просто чтобы убедиться: список отсортирован по полю времени? В противном случае двоичный поиск не будет работать.

Редактировать

Эта проблема сложнее, чем я думал. Решение, которое поможет вам:

  • Создайте класс адаптера, который представляет ваш EventList как IList.
  • Используйте метод расширения BinarySearch в IList для поиска.

К сожалению, нет встроенного метода расширения BinarySearch , поэтому вам придется написать свой собственный. В случае, если вы пишете свой собственный поиск, может не стоить дополнительных усилий, чтобы поместить его в метод расширения. В этом случае, возможно, лучше всего реализовать собственный алгоритм BinarySearch в классе EventList.

Другой вариант будет, если существует форма BinarySearch, которая принимает делегата, который извлекает соответствующий ключ из T, но который также недоступен.

0 голосов
/ 02 апреля 2010

Возможно, вы могли бы рассмотреть возможность использования SortedList в качестве базового класса вместо List. Затем можно использовать метод IndexOfKey для поиска указанной метки времени. Этот метод выполняет бинарный поиск.

0 голосов
/ 02 апреля 2010 
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) { }
}
0 голосов
/ 02 апреля 2010

Если ваш класс Event содержит свойство, по которому вы хотите отсортировать, ваш подход будет нормальным. Затем компилятор может проверить, что независимо от того, что передается в T, он наследует от Event и содержит свойство DateTime. Если Event не содержит свойство DateTime, вы, вероятно, захотите добавить его к событию или ограничить T более конкретным типом, который содержит свойство, необходимое для поиска.

Не забудьте убедиться, что ваш список отсортирован перед применением BinarySearch.

0 голосов
/ 02 апреля 2010

Самый простой способ - определить небольшой вспомогательный класс, который реализует 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());
...