5

開発環境:
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++で作りたい、というのが本音です。)

6
  • 3
    はじめに断っておきますがこれは本筋ではないコメントです。ハッシュテーブルということならKVS系のDBが色々出ているのでそういったものを使うという選択肢はあるかなと思いました。たとえばRedisなどが割りと有名かもしれません。
    – 3100
    Commented 2015年3月6日 15:41
  • ハッシュテーブルの"キー"には何を利用したいのでしょうか?(ある"キー"と"履歴"と"データ"で1個の組になるようなモノ)
    – yohjp
    Commented 2015年3月6日 16:29
  • 返信が遅れて申し訳ない。皆さんの反応速度に驚いております。 >>3100さん 少し調べて見ると、BSDライセンスと言う物が存在するのですね。 なるほど、これなら、著作権表示さえ気を付ければ問題無さそうです。 部分部分の使えそうなソースコードを公開するのは良いのですが、 全体を上げるのは少し抵抗がある物で^^。
    – ADMIS
    Commented 2015年3月7日 5:25
  • >>yohjpさん >>ハッシュテーブルの"キー"には何を利用したいのでしょうか? 申し訳ない。ハッシュを計算するのだから何でも同じだと思っていましたが、気になりますよね。 なんとなく、はばかられたので書きませんでしたが、 今回はウェブと言うよりは、twitterの人気の投稿を解析する、みたいな事をやろうと思っています。 (余り他にやっている人が居ないので、と思っていたら、昨日発見したので、既に二番煎じ以降ですね……) >>(他サイトに迷惑を掛ける事はまず無いです。)、 と言うのは、twitterのAPI使用に制限があるので、最悪無限ループにハマっても制限が掛かると言う意味です。 当然最悪が無いように気を付けます。 まだ開発中なので仕様が確定していませんが、 肝心の「ハッシュテーブルの"キー"」はツイートのid、あるいはユーザのidにする予定です。 OpenSSLを使ったsocket通信でtwitterからJSONを取得すると、 [std::string]型によって整数が文字列として表現されていたので、 [unsigned long long]型に変換しています。 今回は既に[unsigned long long]まで変換しているので、これをキーとして扱おうと考えています。
    – ADMIS
    Commented 2015年3月7日 5:26
  • @ADMIS この回答の編集はレビューキューという仕組みで行っているので気にしないでください。あと解決した場合は回答に表示されているチェックマークをクリックして承認します。また自己解決の場合は質問者自身が回答を投稿することが推奨されています。
    – pgrho
    Commented 2015年3月7日 6:20

1 件の回答 1

3

アプリケーションの要件を見るとunordered_mapでは機能が貧弱ですので、LevelDBなどの永続化できるKVSの利用をおすすめします。

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

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

1
  • >>h2so5さん なるほど、確かにunordered_mapは機能が貧弱の様です。 LevelDBについて調べてみましたが、 これはunordered_mapにちょっとやそっと手を加えただけでは追いつかなさそうです。 休日プログラマー的には性能に寄らず全て自分で書く、というのも一興ですが、 流石に私でもデータベースプログラムの重要性を感じ取ったので、 今回はご紹介いただいた辺りのデータベースプログラムを利用させていただこうと思います。 皆さんどうもありがとうございます。
    – ADMIS
    Commented 2015年3月7日 5:31

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。