-1


ドキュメントがあり、ドキュメントが 4 台の異なるマシンに分散しているとします。繰り返し回数が最も多い (4 台のマシンすべてを組み合わせた) 文字を取得したいと考えています。

私が持っている 1 つのアプローチは、各マシンでハッシュマップを使用し、各マシンの頻度を個別に計算してから、そのハッシュマップをメイン サーバーに渡し、4 台のマシンすべてからのハッシュマップをマージすることです。したがって、頻度が最も高い文字を取得します。

しかし、ここでのキャッシュは、各マシンから転送されるデータを最小限に抑えたいということです。

どのような改善を行うことができますか?

[編集]
各マシンはドキュメントの一部を保持します

4

2 に答える 2

3

気にしなければ、もっと時間がかかります...

  1. 各コンピューターは、最も頻繁に使用される文字を渡します。うまくいけば、頻度が最も高い文字の数は少なくなります。理想的には、ほとんど常に 1 つだけです。
  2. メインサーバーはそれらを組み合わせてセットにします。セットに1人のキャラクターがいる場合。それ以外の場合、このセットは、おそらく配列またはリストとしてコンピューターに渡されます。各コンピューターから 1 文字のみを想定すると、このリストには 2 ～ 4 文字しか含まれません。
  3. 各コンピューターは、セット内の各文字の頻度を返します。
  4. メイン サーバーは頻度を合計し、最も頻度の高いものを取得します。
于 2013-07-16T08:01:15.030 に答える
0

ドキュメント内の文字の分布に関する事前の知識がなければ、4 台のコンピューターすべてからのデータをそのうちの 1 台に減らす必要があると断言します。転送されるデータを最小限に抑えるには、各コンピューターで文字数を保持するデータ構造のサイズを最小限に抑える必要があります。

文字を含むアルファベットで作業していると仮定すると、問題は整数Nを保持できるデータ構造の設計(アルファベットの文字数である範囲内) であり、そのようなデータ構造はいくつでも見つかります。.N[0..m]m

もちろん、文字の分布に関する予備知識がある場合、たとえば、それが英語で書かれた純粋なテキストであることがわかっている場合、データ圧縮に対するさまざまなアプローチが考えられます。

の値が比較的小さく、実際に見つかる可能性が高いことを考えると、N転送mされるデータの量を最小限に抑えるために複雑な構造を考案する価値はおそらくないというコメントの一般的な主張に同意します。N整数の配列を送信することで十分です最も考えられる状況。

于 2013-07-16T07:55:25.960 に答える