Упорядоченная по времени структура данных - PullRequest
Новая
       16

Упорядоченная по времени структура данных

1 голос
/ 08 марта 2012

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

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

Вставки, удаления и правки редки (но иногда необходимы), поэтому время поиска является наиболее важным.

Есть идеи?

Простой пример: 

public class TimedDataItem
{
    DateTime Timestamp { get; set; }
}

// Large populated timestamped data set    
IList<TimedDataItem> timedDataItemsList = new Last<TimedDataItem>();

// Get a 'random' time
DateTime myTime = DateTime.Now;

// Find items around that 'random' time
TimedDataItem next = timedDataItemsList.FirstOrDefault(t=>t.Timestamp > myTime);
TimedDataItem previous = timedDataItemsList.LastOrDefault(t=>t.Timestamp < myTime);

// Also foreach over the collection in time order if required
foreach (TimedDataItem item in timedDataItemsList)
    DoStuff(item);

// Inserts, deletions, edits are extremely rare

Спасибо.

1 Ответ

3 голосов
/ 08 марта 2012

Отредактированный ответ

Предпочтительное решение - SortedSet

plus: отсортированная коллекция, позволяет логически использовать элементы в определенном диапазоне

минус: не уверен, какой алгоритм поиска, нет предыдущего и следующего 

public class TimedDataItem   
{
    public DateTime Timestamp { get; set; }
}
class TimedDataItemComparer : IComparer<TimedDataItem>
{
    public int Compare(TimedDataItem x, TimedDataItem y)
    {
        return x.Timestamp.CompareTo(y.Timestamp);
    }
}
class Program
{
    static void Main(string[] args)
    {
        SortedSet<TimedDataItem> ss = 
            new SortedSet<TimedDataItem>(new TimedDataItemComparer());

        // example data
        ss.Add(new TimedDataItem() { Timestamp = DateTime.Now.AddDays(-5) });
        TimedDataItem min = new TimedDataItem() { Timestamp = DateTime.Now.AddDays(-3) };
        ss.Add(min);
        ss.Add(new TimedDataItem() { Timestamp = DateTime.Now.AddDays(-1) });
        ss.Add(new TimedDataItem() { Timestamp = DateTime.Now });
        ss.Add(new TimedDataItem() { Timestamp = DateTime.Now.AddDays(1) });
        TimedDataItem max = new TimedDataItem() { Timestamp = DateTime.Now.AddDays(3) };
        ss.Add(max);
        ss.Add(new TimedDataItem() { Timestamp = DateTime.Now.AddDays(5) });

        // get elements in range
        SortedSet<TimedDataItem> view = ss.GetViewBetween(min, max);

        foreach (TimedDataItem item in view)
        {
            Console.WriteLine(item.Timestamp);
        }
    }    
}

Solution SortedList

плюс: отсортировано, typeSafe, разрешено следующее и предыдущее

минус: линейный поиск 

 SortedList<TimedDataItem, TimedDataItem> sl =
            new SortedList<TimedDataItem, TimedDataItem>(new TimedDataItemComparer());

 TimedDataItem first = new TimedDataItem() { Timestamp = DateTime.Now.AddDays(-5) };
 TimedDataItem second = new TimedDataItem() { Timestamp = DateTime.Now.AddDays(-3) };
 TimedDataItem third = new TimedDataItem() { Timestamp = DateTime.Now.AddDays(-1) };
 TimedDataItem fourth = new TimedDataItem() { Timestamp = DateTime.Now };
 TimedDataItem fifth = new TimedDataItem() { Timestamp = DateTime.Now.AddDays(1) };
 TimedDataItem sixth = new TimedDataItem() { Timestamp = DateTime.Now.AddDays(3) };
 TimedDataItem seventh = new TimedDataItem() { Timestamp = DateTime.Now.AddDays(5) };

 sl.Add(first, first);
 sl.Add(second, second);
 sl.Add(third, third);
 sl.Add(fourth, fourth);
 sl.Add(fifth, fifth);
 sl.Add(sixth, sixth);
 sl.Add(seventh, seventh);

 // unfortunatelly according to MSDN: 
 //   This method uses a linear search; therefore, this method is 
 //   an O(n) operation, where n is Count.
 int index = sl.IndexOfKey(third);
 TimedDataItem prev = sl.ElementAt(index - 1).Value;
 TimedDataItem next = sl.ElementAt(index + 1).Value;

Решение ArrayList

plus: позволяет использовать индекс, binarySearch (!)

минус: что делать с индексом в неупорядоченной коллекции ... 

ArrayList al = new ArrayList();
al.Add(first);
al.Add(second);
al.Add(third);
al.Add(fourth);
al.Add(fifth);
al.Add(seventh);
al.Add(seventh);

int index2 = al.BinarySearch(third, new TimedDataItemComparer2());
// al[index2] does not make sense
// as there is no guarantee, that al[index2-1] is the element
// with previous DateTime ...

class TimedDataItemComparer2 : IComparer
{
    public int Compare(object x, object y)
    {
        if (x is TimedDataItem && y is TimedDataItem)
            return ((TimedDataItem)x).Timestamp.
                       CompareTo(((TimedDataItem)y).Timestamp);
        else
            return -1;
    }
}
...