Самый быстрый способ поиска коллекции по DateTime

Question

У меня есть словарь, содержащий 10 ключей, каждый со списком, содержащим до 30 000 значений. Значения содержат свойство DateTime.

Мне часто нужно извлечь небольшое подмножество одного из ключей, например, диапазон дат 30-60 секунд.

Выполнение этого легко, но заставить его работать быстро не так. Каким будет наиболее эффективный способ запроса данных в памяти?

Большое спасибо.

Answer 1

Сортировка списков по дате по первой, а затем поиск нужных элементов по бинарному поиску (i.e k item) и их возврат, поиск найденного объекта - O (log (n)), потому что вам нужно найти первый и последний индекс. возвращая их в O (K) во всех Это O (K + журнал (п))

IEnumerable<item> GetItems(int startIndex, int endIndex, List<item> input) 
    { 
     for (int i=startIndex;i<endIndex;i++) 
      yield return input[i]; 
    } 

Answer 2

1) Держите словарь, но использовать SortedList вместо списка для значения словарей, отсортированных по DateTime собственности

2) Реализация бинарного поиска, чтобы найти верхние и нижние кромки в диапазоне в отсортированном списке который дает вам индексы.

3) Просто выберите значения в диапазоне с помощью Sortedlist.Values.Skip(lowerIndex).Take(upperIndex - lowerIndex)

Answer 3

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

Я бы сохранил 2 словаря, один проиндексирован, как и сейчас, и тот, где индексы индексируются по дате. я бы определил временные рамки (скажем, 1 минуту) и добавил каждый объект в список в зависимости от минуты, в который он произошел, а затем добавьте каждый список в словарь под ключом этой минуты. затем, когда вы хотите данные для определенного периода времени, сгенерируйте соответствующую минуту (ы) и получите список (ы) из словаря. Это зависит от того, что вы можете знать ключ в другом словаре из объектов.

Answer 4

В ответ на Aliostad: Я не думаю, что bsearch не будет работать, если список коллекции связанный список , Он по-прежнему принимает значение O (n)