3

私のタイトルが編集されたので、これが宿題であることをみんなに知ってもらいたかった. 問題はプログラムを最適化することだけです。ハッシングは私の考えです。

--

私は、相互のアナグラムである単語をグループ化して出力する C プログラムの最適化に取り組んでいます。

現在、プログラムは基本的にリンクされたリストのリンクされたリストです。外側のリストの各リンクは、相互のアナグラムである単語のグループです。

プログラムのプロファイルは、実行時間の最大の部分が関数であることを示していますwordLookup。これは、すべてのノードを検索する必要があり、ファイルから 100k ワードを読み込む可能性があるため、非常に長い時間がかかる可能性があるためです。たとえばgprof、40k ワードで読み取る場合の出力は次のとおりです。

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls  us/call  us/call  name
100.31      1.48     1.48    40000    37.12    37.12  wordLookup
  0.00      1.48     0.00    78235     0.00     0.00  newnode
  0.00      1.48     0.00    40000     0.00     0.00  sort_string
  0.00      1.48     0.00    38235     0.00     0.00  wordInsert
  0.00      1.48     0.00     1996     0.00     0.00  swap_words
  0.00      1.48     0.00     1765     0.00     0.00  wordAppend

これを高速化するための私のアイデアは、データ構造を、同じスロット内で互いのすべてのアナグラムをチェーンするハッシュ テーブルに変更することです。

私の教授が言ったことと私がここで読んだことを基に、私のハッシュ関数はこのようなものを考えています。(注: 素数は、最も使用される文字が低い数字になり、最も使用されない文字が高い数字になるように分散されます。)

sort(string)

array alpha_primes = 5,71,37,29,2,53,59,19,11,83,79,31,43,13,7,67,97,23,17,3,41,73,47,89,61,101
hash(String) {
  hash = 1
  for (char in String) {
    hash *= alpha_primes[char-'a'];
  }
  return hash % tablesize
}

アナグラムの各グループがテーブル内に個別のインデックスを持つように値を適切に分散する、この問題のハッシュ テーブル サイズはありますか?

それが不可能な場合は、次のことを行う必要があります。

  • 単語のリストを連鎖させる (リストのリスト)
  • プロービング (線形または二次) ソリューションを使用する
  • これらのシナリオのいずれかについて、比較した場合の利点/欠点は何ですか?
4

1 に答える 1

1

ハッシュが一意であることを保証する方法はありません。衝突の確率は誕生日問題によって計算できます。最善の策は、それを最小限に抑えることです。

2 つのグループが同じ値にハッシュされる確率は、1-e^((-k(k-1))/2n) として概算できます。ここで、k はグループの合計量です (単語とほぼ同じです)。 count)、n はハッシュの検索空間 (2^(ハッシュの長さ)) です。

私の辞書には約 100000 の単語があり、32b ハッシュは非常に優れています (衝突の 2%)。ただし、これほど大きなハッシュ テーブルは 4 GB の RAM を使用します。小さいテーブルを使用すると、衝突が多くなります。チェインまたはプロービングは、時間に大きな違いはありません。

あなたの質問へのコメントで推奨されているように、トライは全体的に小さなデータ構造になります。

于 2013-04-14T00:27:12.833 に答える