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

Question

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

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

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

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

Answer 1

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

    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

В ответ Алиостаду: я не думаю, что bsearch не будет работать, если список коллекции является связанным списком. Это все еще занимает O (n)

Answer 4

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

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