cleverwareの日記

CollectionsのListは時には過剰だ、シンプルに考えよう

Java

ふと目にとまったので、ソースを読んだが突っ込みどころが多いような ;-)

d:id:nowokay:20090424 過去の状態のスナップショットを取れるMap

とりあえずシンプルにした方が、速度もメモリ消費もよくなるかな。ArrayListを使うのはメモリ的に無駄が多いし、配列の初期サイズで収まらなくなったときのことを考えれば、

あと、データを変更せず追記する一方なので、ストレージの仕組みとして使うと、変更回数の制限があるSSDと相性がいいとか。

という売り文句にはそぐわないと思う。

履歴は単方向リストで十分だし、常に先頭が最新の状態の方がコードがシンプルになります。要するに標準のライブラリは万能ではないし、使わずに済ませた方がシンプルな場合もあるということ。

こんな感じ：

public class VersionedMap<K, V> implements Map<K, V> {

    static class Version<V> {
        Version<V> next;
        long time = new Date().getTime();
        V data;
        boolean exist;

        Version(Version<V> next, V data) {
            this.next = next;
            this.data = data;
            this.exist = true;
        }

        Version(Version<V> next) {
            this.next = next;
            this.exist = false;
        }
    }

    protected Map<K, Version<V>> repos = new HashMap<K, Version<V>>();
    private int currentCount = 0;

    public VersionedMap() {
    }

    @Override
    public V get(Object key) {
        Version<V> current = repos.get(key);
        return current != null && current.exist ? current.data : null;
    }

    @Override
    public V put(K key, V value) {
        Version<V> old = repos.put(key, new Version<V>(repos.get(key), value));
        if (old != null && old.exist) {
            return old.data;
        }
        currentCount++;
        return null;
    }

    @SuppressWarnings("unchecked")
    @Override
    public V remove(Object key) {
        if (repos.containsKey(key)) {
            Version<V> old = repos.put((K)key, new Version<V>(repos.get(key)));
            if (old.exist) {
                currentCount--;
                return old.data;
            }
        }
        return null;
    }

    @Override
    public Set<java.util.Map.Entry<K, V>> entrySet() {
        Set<Map.Entry<K, V>> ret = new HashSet<Map.Entry<K, V>>();
        for (Map.Entry<K, Version<V>> e : repos.entrySet()) {
            Version<V> head = e.getValue();
            if (head.exist)
                ret.add(new AbstractMap.SimpleEntry<K, V>(e.getKey(),
                        head.data));
        }
        return ret;
    }

    public Map<K, V> getSnapShot(Date d) {
        Map<K, V> ret = new HashMap<K, V>();
        long time = d.getTime();
        for (Map.Entry<K, Version<V>> e : repos.entrySet()) {
            Version<V> history = e.getValue();
            assert history != null;
            while (history != null) {
                if (history.time < time)
                    break;
                history = history.next;
            }
            if (history != null && history.exist) {
                ret.put(e.getKey(), history.data);
            }
        }
        return ret;
    }

    ...以下省略...
}

Permalink | コメント(0) | トラックバック(0) | 13:05