開発環境:
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
などで説明されており、
「全てのキー・値の取得」する場合は、
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"; // 値を表示
}
(上記URLより引用)
のようにすればいいようです。
例えばマシンをシャットダウンする場合、
当然メモリ上のハッシュテーブルを上記のような方法で退避する必要があると思います。
しかし、この方法で退避すると、HDDの容量こそ削減できるものの、
再起動時にハッシュ値を全て再計算する事になると思います。
<<質問②>>
ハッシュテーブルのバイナリをそのままHDDに退避する事は可能ですか?
(全て自作ならこのくらいはそれ程難しい話しではないと思うのですが……たぶん)
あるいは、一件一件退避するとして、そのコストは……どの程度でしょうか?
(もちろん規模と実装に依るのは分かっているのですが、
見当が付かないので、どうすればいいか困っています。
処理が30秒で終わるのか、1時間かかるのか。 )
<<質問③>>
unordered_map
を用いるとして、ハッシュテーブルのサイズが、
メインメモリの容量を越えてしまった場合、どうなるのでしょうか?
また、その場合の解決策について教えて下さい。
最後に、
MySQLなどのデータベース?がC++から使えるかどうかは良く分かりませんが、
取りあえず、今回は余り使いたくないです。
ライセンスを気にしなくてはいけない程のコードは書いていませんが、
巻き込まれたくは無いです。
ただ、もし、随分と簡単にMySQLなどのデータベースが、
この問題を明快に解決してくれるのであれば、
使えて損は無いので、ちょっと気になります。
(でもなるべくC++で作りたい、というのが本音です。)
KVS
系のDBが色々出ているのでそういったものを使うという選択肢はあるかなと思いました。たとえばRedis
などが割りと有名かもしれません。