7561


開発環境:  
Windows7 x64 の VirtualBox 上の  
CentOS7(多分x64) g++

ハッシュテーブルの概念自体は、いろいろなサイトで説明されているので、自作も考えましたが、  
速度など考えるといろいろ試してみたりと、大変なので、  
今回は`unordered_map`の使用を想定しています。

ちょっとしたクローラー的な物を開発しており(他サイトに迷惑を掛ける事はまず無いです。)、  
仮想環境上で上手く動作すれば、8G程度のメモリを乗せたマシンでも安く組んで、  
その上で動かそうと考えています。

そこで、`unordered_map`を用いて、  
過去に調べたデータの[履歴]や、収集した[データ]の格納を考えています。

ここで、[履歴]の方はクロール時に毎回アクセスする事になります。  
しかし、[データ]については、([データ]を解析した後、)最悪破棄しても問題ありません。(アクセスする事は稀です。)

となると、`unordered_map`を用いて、  
[履歴]と[データ]を等しく格納するのはメインメモリの無駄遣いのように思います。  
これらを切り分けて格納する事はできるでしょうか？

<<質問①>>  
要するに、[履歴]は頻繁にアクセスするのでO(1)でアクセスしたい。  
[データ]は、そのままHDDに格納してしまいたい。  
ただし、[データ]には[履歴]と同じキーワード(ハッシュ値)で、  
それなり(……このそれなりが曲者かもしれないですが)の速度でアクセスしたい。O(N)はさすがに困る。

* * *

`unordered_map`は、  
<http://vivi.dyndns.org/tech/cpp/unordered_map.html#assign>  
などで説明されており、  
「全てのキー・値の取得」する場合は、

[code]

    std::unordered_map<std::string, int> mp
    // いろんな値を設定;
    for(auto itr = mp.begin(); itr != mp.end(); ++itr) {
        std::cout << "key = " << itr->first           // キーを表示
                        << ", val = " << itr->second << "\n";    // 値を表示
    }
    
[/code]

(上記URLより引用)  
のようにすればいいようです。

例えばマシンをシャットダウンする場合、  
当然メモリ上のハッシュテーブルを上記のような方法で退避する必要があると思います。  
しかし、この方法で退避すると、HDDの容量こそ削減できるものの、  
再起動時にハッシュ値を全て再計算する事になると思います。

<<質問②>>  
ハッシュテーブルのバイナリをそのままHDDに退避する事は可能ですか？  
(全て自作ならこのくらいはそれ程難しい話しではないと思うのですが……たぶん)

あるいは、一件一件退避するとして、そのコストは……どの程度でしょうか？  
(もちろん規模と実装に依るのは分かっているのですが、  
見当が付かないので、どうすればいいか困っています。  
処理が30秒で終わるのか、1時間かかるのか。 )

* * *

<<質問③>>  
`unordered_map`を用いるとして、ハッシュテーブルのサイズが、  
メインメモリの容量を越えてしまった場合、どうなるのでしょうか？

また、その場合の解決策について教えて下さい。

* * *

最後に、  
MySQLなどのデータベース?がC++から使えるかどうかは良く分かりませんが、  
取りあえず、今回は余り使いたくないです。  
ライセンスを気にしなくてはいけない程のコードは書いていませんが、  
巻き込まれたくは無いです。

ただ、もし、随分と簡単にMySQLなどのデータベースが、  
この問題を明快に解決してくれるのであれば、  
使えて損は無いので、ちょっと気になります。  
(でもなるべくC++で作りたい、というのが本音です。)


CC BY-SA 3.0
2015-03-06T14:41:30.273
7559
2016-02-02T06:47:30.690
2016-02-02T06:47:30.690
8000
8724
question
c++ c++11
C++でハッシュテーブルを用いたデータベースのような物を考えています。


アプリケーションの要件を見ると`unordered_map`では機能が貧弱ですので、[LevelDB](https://github.com/google/leveldb)などの永続化できるKVSの利用をおすすめします。

`unordered_map`はすべてのデータをメモリ上に置いているのでアクセスは速いですが、データが増えるとメモリを圧迫しますし、データを永続化する場合の処理を自作しなくてはなりません。(boost::serializationなどを使う手もありますが)

`LevelDB`の場合は自動でデータをHDDに保存してくれますし、必要に応じて`Cache`としてデータをメインメモリ上に置くのでアクセス速度とメモリ使用量のバランスを取ることができます。質問者さんが心配している部分はライブラリ側でうまく取り計らってくれるということになりますので、`unordered_map`をそのまま使うよりずっと便利です。


CC BY-SA 3.0
2015-03-06T15:42:10.607
7561
2015-03-06T16:00:57.747
2015-03-06T16:00:57.747
3639
3639
7559
answer