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 като базов клас вместо List. След това можете да използвате метода IndexOfKey за търсене на определен TimeStamp. Този метод прави двоично търсене.

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