トップ «前の日記(2009-12-06) 最新 次の日記(2009-12-09)» 編集

はじめてのにき

ここの位置付け

2004|11|
2005|03|04|05|06|07|08|09|10|11|12|
2006|01|02|03|04|05|06|07|08|09|10|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|07|08|09|10|11|12|
2009|01|02|03|04|05|06|07|08|09|10|11|12|
2010|01|02|03|04|05|06|07|08|09|10|11|12|
2011|01|02|03|04|05|06|07|08|09|10|11|12|
2012|01|02|03|04|05|06|07|08|09|10|11|12|
2013|01|02|03|04|05|06|07|08|09|10|11|12|
2014|01|02|03|04|05|06|07|08|09|10|11|12|
2015|01|02|03|04|05|06|07|08|09|10|11|12|
2016|01|02|03|04|05|06|07|08|09|10|11|12|
2017|01|02|03|04|05|06|07|08|09|10|11|12|
2018|01|02|03|04|05|06|07|08|09|10|11|12|
2019|01|02|03|04|05|06|07|

ToDo:


2009-12-08

_ バックアップメモ

とりあえず /data/backup に ゴルフ場と SVN と shinh.org を保持するようにした。

本当はもちょいちゃんとした管理をせにゃならんが。

(00:54)

_ キャッシュのデータ構造

まぁなんらかのキャッシュが作りたいとして、 基本は 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)

_ C++ の話してみて

なんか %rdi って何? とかいう質問があって、 x86 知ってる人に向けた x86-64 の概説みたいなのも 結構面白いのかなぁとか思った。

(02:38)

本日のツッコミ(全3件) [ツッコミを入れる]
_ yutak (2014-05-24 03:16)

>キャッシュ
Javaにはそのものズバリ "LinkedHashMap" というクラスがあります。この手のLRUキャッシュを作るのにぴったりです。実装は多分 hash_map と list<hash_map::iterator> を両方持っているだけのような気がします...

_ もわ (2014-05-24 03:16)

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;
        }
    }

_ kinaba (2014-05-24 03:16)

Java なら
http://commons.apache.org/collections/apidocs/org/apache/commons/collections/map/LRUMap.html
が。実装は↑のような構造をLRUで適宜並びかえるだけだったと思いますが

お名前:
E-mail:
コメント:
人生、宇宙、すべての答え
本日のリンク元

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
1.shinh(2014-05-24 03:16) 2.kinaba(2014-05-24 03:16) 3.shinh(2014-05-24 03:16)
search / home / index

全てリンクフリーです。 コード片は自由に使用していただいて構いません。 その他のものはGPL扱いであればあらゆる使用に関して文句は言いません。 なにかあれば下記メールアドレスへ。

shinichiro.hamaji _at_ gmail.com / shinichiro.h