Структура данных для хранения списка объектов с меткой времени

У меня есть список объектов с меткой времени, и единственным запросом, который мне нужно выполнить, будет «найти все объекты с временной шкалой больше, чем x». Какая структура данных лучше всего подходит для оптимизации вышеуказанного поиска? Я в порядке с большими временами вставки, но, если возможно, предпочел бы не идти с полной реализацией EPL.Структура данных для хранения списка объектов с меткой времени

источник

2013-10-08 qwerty

, что является временной меткой объект в вашем приложении? Объект, который содержит поле даты? – MaVRoSCy

Интервал дерево это первое, что приходит на ум. – Justin

Если вы используете базу данных SQL в приложении где-то, а затем создать индекс для поля метки времени и просто сделать запрос.

В противном случае, если у вас нет базы данных, это выглядит как работа для TreeMap или ConcurrentSkipList. Оба реализуют метод subMap(K, K), headMap(K) и tailMap(K) от NavigableMap interface. Вы можете указать пользовательский заказ для любого SortedMap (и его подинтерфейсов), выполнив интерфейс Comparable в ваших ключах или указав Comparator при создании вашей коллекции. Если вам не нужно отображать значение ключа, вы также можете просто использовать NavigableSet и их реализации TreeSet или ConcurrentSkipListSet.

источник

2013-10-08 09:49:13

Структура находится в памяти (нет db). Реализации NavigableMap (особенно в коллекциях google) выглядят многообещающими. Спасибо за указатель. – qwerty

+1 для NavigableMap – Rich

Не могли бы вы упомянуть о том, Сопоставимый интерфейс ? –

Вы можете использовать такой код:

//declare an ArrayList of Objects 
ArrayList<MyTimestampedObject> list = loadObjects(); 

//new list to store Objects after condition check 
ArrayList<MyTimestampedObject> newList = new ArrayList<MyTimestampedObject>(); 

//loop through the list 
for(MyTimestampedObject tmp:list){ 

    //check condition 
    if(tmp.getDate()>x){ 
    //do something 
    newList.add(tmp); 
    } 

}

источник

2013-10-08 09:15:47 MaVRoSCy

Благодарим за отзыв. Однако это будет решение O (N). Я ищу что-то более оптимистичное, если возможно – qwerty

Я считаю, что реализация сопоставимого интерфейса намного лучше –

Вы можете использовать любую отсортированный структуру данных, которая позволяет бинарный поиск (если вы не заботитесь о времени введения), и для данного в X, выполнить поиск (который занимает O(logN) время), чтобы найти первый объект с timestamp > X , поскольку структура данных упорядочена, все объекты в структуре данных после этого объекта также имеют timestamp > X.

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

источник

2013-10-08 11:30:24

Как насчет BST (бинарное дерево поиска? ЗаказовМои дает вам именно то, что вам нужно, с O (LogN).

источник

2013-10-09 11:18:10

Структура данных для хранения списка объектов с меткой времени

ответ

Смежные вопросы