Ускорение поиска диапазонов данных из коллекции - PullRequest
Новая
       18

Ускорение поиска диапазонов данных из коллекции

2 голосов
/ 15 ноября 2009

Скажите, у меня есть класс 

public class TimestampedTrackId
{
    private readonly int trackId;
    private readonly DateTime insertTime;
    public TimestampedTrackId(int trackId, DateTime insertTime)
    {
        this.trackId = trackId;
        this.insertTime = insertTime;
    }

    public int TrackId
    {
        get
        {
            return trackId;
        }
    }

    public DateTime InsertTime
    {
        get
        {
            return insertTime;
        }
    }
}

У меня большой список типа List<TimestampedTrackId>, и мне нужно извлечь TimestampedTrackId экземпляров из этого списка, где свойство InsertTime находится между минимальным и максимальным DateTime. 

List<TimestampedTrackId> tracks; //Count=largeNumber
... 
tracks.Where(t=>t.InsertTime>min&&t.InsertTime<max)

A List<T>, очевидно, не является подходящим контейнером для этой задачи, поскольку он требует поиска по каждому элементу, чтобы проверить, находится ли InsertTime между минимальным и максимальным значениями.

Итак, я предполагаю, что часть ускорения этого кода будет включать переупаковку списка в более подходящую коллекцию, но какую коллекцию?

При правильной коллекции (которая может быть ключевой), какой запрос я мог бы использовать, чтобы использовать максимальную скорость поиска?

Заранее спасибо

Ответы [ 2 ]

4 голосов
/ 15 ноября 2009

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

.NET изначально его не имеет, но есть хорошая реализация здесь .

3 голосов
/ 15 ноября 2009

Можете ли вы отсортировать список по InsertTime? Если это так, List<T>.BinarySearch является вашим другом - укажите IComparer<TimestampedTrackId>, который сравнивается на InsertTime и BinarySearch для min и max. (Вам нужно будет создать «фиктивные» TimestampedTrackId объекты со значениями InsertTime min и max для их поиска.)

Если BinarySearch возвращает отрицательное значение, вы должны взять побитовое дополнение (используя оператор ~), чтобы узнать индекс, куда будет вставлено значение. Также помните, что если у нескольких элементов может быть одинаковый InsertTime, вам нужно будет работать в обратном направлении от индекса min и вперед от индекса max, чтобы убедиться, что вы получите полный диапазон. В любом случае, это все равно будет намного эффективнее, чем линейный поиск. По общему признанию это немного более странно:)

...