1

私はアルゴリズムが必要な実際の状況に取り組んでおり、それから一般的な問題を引き起こしました。2つの配列があることを考えると：-

Source [10] = {'a'、'v'、'l'、'r'、'p'、's'、'x'、'd'、'q'、'o'、'g'、 'm'}

Target [N] = {'a'、'v'、'l'、'r'、'p'、's'、'x'、'd'、'q'、'o'、'g'、 'm'、a'、' v'、' l'、' r'、' p'、a'、'v'、'l'、'r'、'p'、a'、

'v'、'l'、'r'、'p'、a'、' v'、' l'、' r'、' p'、a'、'v'、'l'、'r'、 'p'、a'、' v'、' l'、' r'、' p'、a'、'v'、'l'、'r'、'p'、a'、' v'、

'l'、'r'、'p'、a'、' v'、' l'、' r'、' p'、....}

ターゲットのソースから文字の出現頻度を見つけるための効率的なアルゴリズムが必要です。

完全なターゲットリストをハッシュしてから、ソースを反復処理して、ハッシュリストでルックアップを実行することを考えました。人々はアプローチをコメント/検証できますか？

4

2 に答える 2

2

文字セットが適度に制限されている場合は、カウントの配列へのインデックスとして文字コードを使用できます。16ビット文字があるとしましょう。あなたはこれを行うことができます：

int[] counts = new int[65536];
foreach (char c in Target)
    counts[c]++;

の配列が手元にある場合は、配列内のcountsからコードを検索することで、頻度を簡単に見つけることができます。Sourcecounts

このソリューションは、可能な限り漸近的に高速ですが、最もメモリ効率の高いソリューションではない場合があります。

于 2013-01-25T16:42:49.760 に答える
0

ハッシュリストが何であるかわからないので、コメントすることはできません。効率を上げるために、ターゲットアレイをマルチセットに変換することをお勧めします。Guavaには、そのようなものの優れた実装があります（ただし、Javaコレクションフレームワークにはありません）。Apache Commons （これはと呼ばれますBag）も同様です。次に、ソースを繰り返し処理して、マルチセット内の各要素の頻度を調べることができます。このスレッドで説明されているように、マルチセットを使用する方が、from要素から周波数を使用するよりも簡単ですがHashMap、サードパーティのライブラリを使用する必要があります。

于 2013-01-25T16:16:03.190 に答える