ToDo:
まぁなんらかのキャッシュが作りたいとして、 基本は hash map なわけだけど、 1000要素を越えたら一番古いヤツを消せるものができると嬉しいとする。
まぁ普通に考えると hash_map と hash_map::iterator をデータとして持っていて 最終更新時間が一番古いのが top に来るヒープがあればいいのかなーと思うんだけど、 まぁなんか二つデータ構造持つとかは2つが inconsistent になったりすると悲しいので、 なんか1つでなんとかできる構造があればすごいんだけど、 まぁなんか無いのかな。 無さそうだけど。
あともう一個思うこととして、 単に一番古いのを覚えておくために O(N) のメモリを 別に使うってのはなんかイヤだよなーということで、 それを最小化したければ、 hashmap を open hash で作っておいて ヒープの方に入れるデータは index にしておけば 1要素あたりの消費メモリが sizeof(void*)==8 より小さくなっていいのかなぁとか。
ところで今やってみて気付いたんだけど sizeof(unordered_map<int, int>::const_iterator)==16 なのね。 なんかこう 64bit 環境ですごいイヤなことの一つとして ポインタのサイズのせいで細かいオブジェクトがたくさんあるようなものの メモリ使用量が結構増えるってのがあって、 うーんそういうの的にやさしくない感じだなぁ。
(02:33)
| 前 | 2009年 12月 |
次 | ||||
| 日 | 月 | 火 | 水 | 木 | 金 | 土 |
| 1 | 2 | 3 | 4 | 5 | ||
| 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| 20 | 21 | 22 | 23 | 24 | 25 | 26 |
| 27 | 28 | 29 | 30 | 31 | ||
全てリンクフリーです。 コード片は自由に使用していただいて構いません。 その他のものはGPL扱いであればあらゆる使用に関して文句は言いません。 なにかあれば下記メールアドレスへ。
>キャッシュ
Javaにはそのものズバリ "LinkedHashMap" というクラスがあります。この手のLRUキャッシュを作るのにぴったりです。実装は多分 hash_map と list<hash_map::iterator> を両方持っているだけのような気がします...
HashMapの各ノードがprevとnextを持ったリンクリストにもなっているんじゃないでしょうか。今手元のJava (Sun のかは不明) の実装を見たら以下のような内部クラスを使ってました。
static class LinkedEntry<K, V> extends HashMapEntry<K, V> {
LinkedEntry<K, V> nxt;
LinkedEntry<K, V> prv;
LinkedEntry() {
super(null, null, 0, null);
nxt = prv = this;
}
LinkedEntry(K key, V value, int hash, HashMapEntry<K, V> next,
LinkedEntry<K, V> nxt, LinkedEntry<K, V> prv) {
super(key, value, hash, next);
this.nxt = nxt;
this.prv = prv;
}
}
Java なら
http://commons.apache.org/collections/apidocs/org/apache/commons/collections/map/LRUMap.html
が。実装は↑のような構造をLRUで適宜並びかえるだけだったと思いますが