RSSイントレ。
2007-07-29
[日記]
今日は気分転換にDHTのお勉強。
DHTには興味があったので、
説明しているサイトとか、論文とか読んでみたりしたんですが、
いまいちサッパリだったんですね。
なんでDHTだと効率的に管理が出来るのか。
なんでハッシュ関数を使うのか。
「答えは全部コードにある」って昔の偉い人が言っていたので、
実装が簡単らしいKademliaのソースコードを追って理解することにしました。
ググると、以外にもJavaやPythonのコードが出てきます。
ちゃんと読める自信はないのですが、大体ならどの言語も共通ですし。
…で、足りない頭をフル回転してC#で実装してみてるんですが、
何となく感じがつかめたような気が。
・DHTの目的は検索の効率化
・隔たり無く情報(キー)を分けるためにハッシュ関数を使う
・ハッシュデータに「距離」という概念を導入し、距離を元に検索するノードを絞り込む
・目標としては、ノード数Nに対してlog(N)回以内の目的のノードを探し出せること。
(たとえば、100万ノードあったとして、6ノードを辿れば目的のノードにたどり着く)
確かに、うまく考えられた方法だなと納得してしまいます。
闇雲に検索するのではなく、ルールに則って分されているというのがポイントでしょうか。
これ、ネットワーク関係だけじゃなく、検索のあらゆる分野に適用可能ですよね。
改めてスゲェって思ってしまう…。
みんな熱心に研究する訳だ。
DHTには興味があったので、
説明しているサイトとか、論文とか読んでみたりしたんですが、
いまいちサッパリだったんですね。
なんでDHTだと効率的に管理が出来るのか。
なんでハッシュ関数を使うのか。
「答えは全部コードにある」って昔の偉い人が言っていたので、
実装が簡単らしいKademliaのソースコードを追って理解することにしました。
ググると、以外にもJavaやPythonのコードが出てきます。
ちゃんと読める自信はないのですが、大体ならどの言語も共通ですし。
…で、足りない頭をフル回転してC#で実装してみてるんですが、
何となく感じがつかめたような気が。
・DHTの目的は検索の効率化
・隔たり無く情報(キー)を分けるためにハッシュ関数を使う
・ハッシュデータに「距離」という概念を導入し、距離を元に検索するノードを絞り込む
・目標としては、ノード数Nに対してlog(N)回以内の目的のノードを探し出せること。
(たとえば、100万ノードあったとして、6ノードを辿れば目的のノードにたどり着く)
確かに、うまく考えられた方法だなと納得してしまいます。
闇雲に検索するのではなく、ルールに則って分されているというのがポイントでしょうか。
これ、ネットワーク関係だけじゃなく、検索のあらゆる分野に適用可能ですよね。
改めてスゲェって思ってしまう…。
みんな熱心に研究する訳だ。
Loading...
Utilities
- タグ
- カレンダー
- 最近の更新
- Adsense