java - 时间快照的数据结构

Question

我的需求是能够在一段时间内将对象存储在数据结构中，然后能够获取特定时间数据的快照。我有一些解决方案，但我想知道是否有更优化的方法来执行此操作。我在想可能有一种方法可以优化存储机制，不需要迭代每个元素来获取当时的快照。

在真实场景中，数据的更新随时都可能到来。数据结构中的对象由整数索引。我用 Map 快速模拟了一些东西来说明我正在尝试做什么(其中 arraylist 是对象的更新历史)。

public class TimeStoreTest {

    static SimpleDateFormat df = new SimpleDateFormat("yy-MM-dd HH:mm:ss");

    public static void main(String[] args) throws Exception {

        Date[] dates = new Date[] { df.parse("2014-01-23 10:30:30"),
                df.parse("14-01-23 10:33:30"), df.parse("14-01-23 10:36:30"),
                df.parse("14-01-23 10:39:30"), df.parse("14-01-23 10:42:30") };

        Map<Integer, List<SimpleObject>> timeStore = new HashMap<Integer, List<SimpleObject>>();

        for (int i = 0; i < 10; i += 2) {
            List<SimpleObject> objs = new ArrayList<SimpleObject>();

            objs.add(new SimpleObject(i, dates[0]));
            timeStore.put(i, objs);
        }

        for (int i = 1; i < 10; i += 2) {
            List<SimpleObject> objs = new ArrayList<SimpleObject>();

            objs.add(new SimpleObject(i, dates[1]));
            timeStore.put(i, objs);
        }

        for (int i = 0; i < 10; i += 2) {
            List<SimpleObject> objs = timeStore.get(i);
            objs.add(new SimpleObject(i, dates[2]));
        }

        for (int i = 1; i < 10; i += 2) {
            List<SimpleObject> objs = timeStore.get(i);
            objs.add(new SimpleObject(i, dates[3]));
        }

        for (int i = 5; i < 10; i++) {
            List<SimpleObject> objs = timeStore.get(i);
            objs.add(new SimpleObject(i, dates[4]));
        }

        System.out.println("Current Data Store: ");
        for (Entry<Integer, List<SimpleObject>> entry : timeStore.entrySet()) {
            System.out.println(entry);
        }

        Date queryDate = df.parse("14-01-23 10:31:00");

        System.out.println("Query for object snapshot @ " + queryDate);
        for (SimpleObject obj : getObjectsAtTime(queryDate, timeStore)) {
            System.out.println(obj);
        }

        queryDate = df.parse("14-01-23 10:34:30");
        System.out.println("Query for object snapshot @ " + queryDate);
        for (SimpleObject obj : getObjectsAtTime(queryDate, timeStore)) {
            System.out.println(obj);
        }

        queryDate = df.parse("14-01-23 10:39:30");
        System.out.println("Query for object snapshot @ " + queryDate);
        for (SimpleObject obj : getObjectsAtTime(queryDate, timeStore)) {
            System.out.println(obj);
        }

        queryDate = df.parse("14-01-23 10:42:00");

        System.out.println("Query for object snapshot @ " + queryDate);
        for (SimpleObject obj : getObjectsAtTime(queryDate, timeStore)) {
            System.out.println(obj);
        }

        queryDate = df.parse("14-01-23 10:45:00");

        System.out.println("Query for object snapshot @ " + queryDate);
        for (SimpleObject obj : getObjectsAtTime(queryDate, timeStore)) {
            System.out.println(obj);
        }

    }

    public static List<SimpleObject> getObjectsAtTime(Date date,
            Map<Integer, List<SimpleObject>> store) {
        List<SimpleObject> objectsAtTime = new ArrayList<SimpleObject>();

        for (Entry<Integer, List<SimpleObject>> entry : store.entrySet()) {

            SimpleObject previousObject = null;

            List<SimpleObject> list = entry.getValue();

            for (int i = 0; i < list.size(); i++) {
                SimpleObject currentObject = list.get(i);
                if (previousObject != null) {
                    if (date.after(previousObject.updatedTime)
                            && date.before(currentObject.updatedTime)) {
                        objectsAtTime.add(previousObject);
                        break;
                    } else if (currentObject.updatedTime.equals(date)) {
                        objectsAtTime.add(currentObject);
                        break;
                    } else if (i == list.size() - 1
                            && date.after(previousObject.updatedTime)) {
                        objectsAtTime.add(currentObject);
                    }
                }

                previousObject = currentObject;
            }

        }

        return objectsAtTime;

    }
}

class SimpleObject implements Comparable {
    int id;
    Date updatedTime;

    public SimpleObject(int id, Date updatedTime) {
        this.id = id;
        this.updatedTime = new Date(updatedTime.getTime());

    }

    @Override
    public String toString() {
        return "(object id=" + id + "; t="
                + TimeStoreTest.df.format(updatedTime) + ")";
    }

    @Override
    public int compareTo(Object object) {
        // TODO Auto-generated method stub
        return updatedTime.compareTo(((SimpleObject) object).updatedTime);
    }
}

结果:

当前数据存储:

0=[(object id=0; t=14-01-23 10:30:30), (object id=0; t=14-01-23 10:36:30)]
1=[(object id=1; t=14-01-23 10:33:30), (object id=1; t=14-01-23 10:39:30)]
2=[(object id=2; t=14-01-23 10:30:30), (object id=2; t=14-01-23 10:36:30)]
3=[(object id=3; t=14-01-23 10:33:30), (object id=3; t=14-01-23 10:39:30)]
4=[(object id=4; t=14-01-23 10:30:30), (object id=4; t=14-01-23 10:36:30)]
5=[(object id=5; t=14-01-23 10:33:30), (object id=5; t=14-01-23 10:39:30), (object id=5; t=14-01-23 10:42:30)]
6=[(object id=6; t=14-01-23 10:30:30), (object id=6; t=14-01-23 10:36:30), (object id=6; t=14-01-23 10:42:30)]
7=[(object id=7; t=14-01-23 10:33:30), (object id=7; t=14-01-23 10:39:30), (object id=7; t=14-01-23 10:42:30)]
8=[(object id=8; t=14-01-23 10:30:30), (object id=8; t=14-01-23 10:36:30), (object id=8; t=14-01-23 10:42:30)]
9=[(object id=9; t=14-01-23 10:33:30), (object id=9; t=14-01-23 10:39:30), (object id=9; t=14-01-23 10:42:30)]
Query for object snapshot @ Thu Jan 23 10:31:00 PST 2014
(object id=0; t=14-01-23 10:30:30)
(object id=2; t=14-01-23 10:30:30)
(object id=4; t=14-01-23 10:30:30)
(object id=6; t=14-01-23 10:30:30)
(object id=8; t=14-01-23 10:30:30)
Query for object snapshot @ Thu Jan 23 10:34:30 PST 2014
(object id=0; t=14-01-23 10:30:30)
(object id=1; t=14-01-23 10:33:30)
(object id=2; t=14-01-23 10:30:30)
(object id=3; t=14-01-23 10:33:30)
(object id=4; t=14-01-23 10:30:30)
(object id=5; t=14-01-23 10:33:30)
(object id=6; t=14-01-23 10:30:30)
(object id=7; t=14-01-23 10:33:30)
(object id=8; t=14-01-23 10:30:30)
(object id=9; t=14-01-23 10:33:30)
Query for object snapshot @ Thu Jan 23 10:39:30 PST 2014
(object id=0; t=14-01-23 10:36:30)
(object id=1; t=14-01-23 10:39:30)
(object id=2; t=14-01-23 10:36:30)
(object id=3; t=14-01-23 10:39:30)
(object id=4; t=14-01-23 10:36:30)
(object id=5; t=14-01-23 10:39:30)
(object id=6; t=14-01-23 10:36:30)
(object id=7; t=14-01-23 10:39:30)
(object id=8; t=14-01-23 10:36:30)
(object id=9; t=14-01-23 10:39:30)
Query for object snapshot @ Thu Jan 23 10:42:00 PST 2014
(object id=0; t=14-01-23 10:36:30)
(object id=1; t=14-01-23 10:39:30)
(object id=2; t=14-01-23 10:36:30)
(object id=3; t=14-01-23 10:39:30)
(object id=4; t=14-01-23 10:36:30)
(object id=5; t=14-01-23 10:39:30)
(object id=6; t=14-01-23 10:36:30)
(object id=7; t=14-01-23 10:39:30)
(object id=8; t=14-01-23 10:36:30)
(object id=9; t=14-01-23 10:39:30)
Query for object snapshot @ Thu Jan 23 10:45:00 PST 2014
(object id=0; t=14-01-23 10:36:30)
(object id=1; t=14-01-23 10:39:30)
(object id=2; t=14-01-23 10:36:30)
(object id=3; t=14-01-23 10:39:30)
(object id=4; t=14-01-23 10:36:30)
(object id=5; t=14-01-23 10:42:30)
(object id=6; t=14-01-23 10:42:30)
(object id=7; t=14-01-23 10:42:30)
(object id=8; t=14-01-23 10:42:30)
(object id=9; t=14-01-23 10:42:30)

所以，您可以看到它有效，但我正在努力寻找提高效率的方法。

Answer 1

使用 NavigableMap 可能会让您的生活更轻松。看看例如 TreeMap#floorEntry()它的作用类似于您的 getObjectsAtTime 方法。

它还有其他方法，例如 subMap 也可能很方便。