Двоичный поиск C# в списке‹T› членом T

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

Что было бы хорошим способом приблизиться к этому?


class search c# binary member
person Pygmy    schedule 02.04.2010    source источник

Ответы (4)


arrow_upward
1
arrow_downward

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

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

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

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

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

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

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

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

person Anders Abel    schedule 02.04.2010
comment
Проблема в том, что BinarySearch не принимает DateTime в качестве первого параметра, а ожидает объект типа T (то есть производный от событий)! - person Pygmy; 02.04.2010
comment
Это не сработает. int index = this.BinarySearch (новое событие (inFromTime), компаратор); не работает, поскольку BinarySearch ожидает первый параметр типа T, который может отличаться от GameEvent (но быть производным от него). Я не могу использовать new T(inFromTime), так как производные классы не поддерживают конструктор только с отметкой времени параметра. - person Pygmy; 02.04.2010
comment
См. мои добавленные мысли под заголовком «Редактировать». Эта задача на первый взгляд кажется очень простой, но на самом деле это не так. - person Anders Abel; 02.04.2010

arrow_upward
0
arrow_downward

Самый простой способ — определить небольшой вспомогательный класс, реализующий 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());
person JaredPar    schedule 02.04.2010
comment
Проблема в том, что BinarySearch не принимает DateTime в качестве первого параметра, а ожидает объект типа T (то есть производный от событий)! - person Pygmy; 02.04.2010

arrow_upward
0
arrow_downward

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

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

person driis    schedule 02.04.2010
comment
Список отсортирован, проблема в первом параметре метода BinarySearch... - person Pygmy; 02.04.2010

arrow_upward
0
arrow_downward

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

person Mikael Sundberg    schedule 02.04.2010
comment
SortedList не допускает дублирования ключей. - person Pygmy; 02.04.2010