лучшая структура данных для отсортированных данных временных рядов, которая может быстро возвращать подмассивы?

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

Я использую С#. я думал, что использование обычного списка было бы возможно, где «datapoint» — это класс, который содержит поля timestamp и double[]. затем, чтобы вставить, я бы использовал встроенный двоичный поиск(), чтобы найти, куда вставить новые данные, и я мог бы использовать его снова, чтобы найти индексы начала/конца для поиска диапазона.

Сначала я попробовал отсортированные списки, но похоже, что вы не можете перебирать индексы i = 0,1,2,..., n, только через ключи, поэтому я не был уверен, как выполнить поиск по диапазону без какой-то запутанной функции .

но потом я узнал, что list‹> вставки () является o (n) ... не мог бы я сделать лучше, чем это, не жертвуя в другом месте?

в качестве альтернативы, есть ли какой-нибудь хороший запрос linq, который сделает все, что я хочу, в одной строке?


c# linq range sortedlist
person Community    schedule 17.04.2009    source источник

Ответы (4)


arrow_upward
1
arrow_downward

Если вы хотите использовать библиотеки, отличные от BCL, C5.SortedArray‹T› всегда хорошо работал у меня.

У него отличный метод, RangeFromTo, который достаточно хорошо справляется с проблемами такого рода.

person Reed Copsey    schedule 17.04.2009

arrow_upward
1
arrow_downward

Если у вас есть только статические данные, то подойдет любая структура, реализующая IList. Отсортируйте его один раз, а затем сделайте запросы с помощью BinarySearch. Это также должно работать, если ваши вставленные временные метки всегда увеличиваются, тогда вы можете просто выполнить List.Add() в O (1), и он все равно будет отсортирован.

    List<int> x = new List<int>();
    x.Add(5);
    x.Add(7);
    x.Add(3);

    x.Sort();

    //want to find all elements between 4 and 6
    int rangeStart = x.BinarySearch(4);

    //since there is no element equal to 4, we'll get the binary complement of an index, where 4 could have possibly been found
    //see MSDN for List<T>.BinarySearch
    if (rangeStart < 0)
        rangeStart = ~rangeStart;

    while (x[rangeStart] < 6)
    {
        //do you business
        rangeStart++;
    }

Если вам нужно вставлять данные в случайные точки в вашу структуру, поддерживать их сортировку и иметь возможность быстро запрашивать диапазоны, вам нужна структура с именем Дерево B+. Это не реализовано в фреймворке, вам нужно будет получить его где-то самостоятельно.

Вставка записи требует O(log n) операций в худшем случае

Для поиска записи требуется O(log n) операций в худшем случае

Удаление (ранее расположенной) записи требует O(log n) операций в худшем случае

Выполнение запроса диапазона с k элементами, находящимися в диапазоне, требует O((log n) + k) операций в худшем случае.

P.S. "есть ли хороший запрос linq, который сделает все, что я хочу, в одной строке"

Хотел бы я знать такой хороший запрос linq, который мог бы делать все, что я хочу, в одной строке :-)

person Max Galkin    schedule 17.06.2009

arrow_upward
0
arrow_downward

У вас есть выбор стоимости при вставке, извлечении или удалении. Существуют различные структуры данных, оптимизированные для каждого из этих случаев. Прежде чем вы выберете одну, я бы оценил общий размер ваших структур, сколько точек данных генерируется (и с какой частотой) и что будет использоваться чаще: вставка или извлечение.

Если вы вставляете много новых точек данных с высокой частотой, я бы посоветовал просмотреть LinkedList‹>. Если вы извлекаете данные чаще, я бы использовал List‹>, даже несмотря на то, что время его вставки медленнее.

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

person grover    schedule 17.04.2009
comment
Однако LinkedList будет очень медленным для его поиска по диапазону, что, по его словам, он пытался оптимизировать. - person Reed Copsey; 17.04.2009
comment
Согласен, но это зависит от нескольких факторов. Не проверив это с помощью секундомера, я бы не стал рассчитывать на мягкие факты. Я видел случаи, когда использование LinkedList было на самом деле быстрее. Это зависит от обстоятельств. Как я уже сказал, если есть больше вставок, которые O (n) становятся дорогостоящими, LinkedList работает лучше из-за O (1). Если есть больше запросов, отсортированный список‹› будет работать лучше, чем что-либо еще. - person grover; 17.04.2009

arrow_upward
0
arrow_downward

Как насчет использования реальной базы данных для хранения ваших данных и выполнения запросов к ней? Затем вы можете использовать LINQ-to-SQL.

person Erich Mirabal    schedule 24.04.2009