1

Dictionary<Dictionary<char,int>, List<string>>辞書でアナグラムの単語を見つけるためのアルゴリズムを実装したかったのです。

この辞書のカスタムを実装する必要があるのでEqualityComparer、アクセス時間はまだO（1）、つまり大きなO（1）ですか？

2番目の質問、の一部として、EqualityComparer私も実装する必要がありGetHashCode()ます。GetHashCode()を決定する効率的な方法は何Dictionary<Dictionary<char,int>, List<string>>ですか？

私はこの方法を思いついたばかりですが、もっと良い方法はありますか？

public int GetHashCode(Dictionary<char, int> obj)
    {
        unchecked
        {
            int hashCode = 17;
            foreach (var item in obj)
            {
                hashCode += 23 * item.Key.GetHashCode();
            }
            return hashCode;
        }
    }

アドバイスをいただければ幸いです。ありがとう！

4

3 に答える 3

2

のアクセス時間はO（1）にDictionary<TKey, TValue> 近づきますが、正確にはそうではありません。理想的なシナリオ（良好な分散/衝突が少ない）では、O（1）と考えることができます。GetHashCode値の変動が小さいために衝突が多い状況では、アクセス時間が低下し、O（N）に近づく可能性があります。

于 2012-01-15T00:00:17.220 に答える
2

辞書をキーとして使用する代わりに、単語「need」を文字列「d1e2n1」に変換するのはどうですか？この文字列を作成するには、バイナリツリーを使用できます。文字はキーとして使用され、文字数は値として使用されます。二分木はキーによって自動的にソートされますが、辞書の場合はそうではありません。

バイナリ表現をXOR演算と組み合わせることにより、単一のハッシュ値から結合されたハッシュ値を計算できます。C＃を使用すると、次のようになります。

public override int GetHashCode()
{
    // Combine hashcode of a and b
    return a.GetHashCode() ^ b.GetHashCode();
}

ソートされていないリストでエントリを見つけることは、O（n）操作です。バイナリ検索が使用されている場合、ソートされたリスト内のエントリの検索はO（log（n））操作です。

辞書のリストで単語を見つけることは、O（n）演算と同じO（1 + n）演算、またはO（1 + log（n））演算と同じです。 O（log（n））操作。

編集：

可能な実装は次のとおりです。

var anagrams = new Dictionary<string, List<string>>();
foreach (string word in words) {
    string key = GetFrequency(word);
    List<string> list;
    if (anagrams.TryGetValue(key, out list)) {
        list.Add(word);
    } else {
        list = new List<string> { word };
        anagrams.Add(key, list);
    }
}

このメソッドを使用してキーを取得します。

private string GetFrequency(string word)
{
    var dict = new SortedDictionary<char, int>(); // Implemented as binary tree
    foreach (char c in word.ToLower()) {
        int count;
        if (dict.TryGetValue(c, out count)) {
            dict[c] += 1;
        } else {
            dict[c] = 1;
        }
    }
    return dict.Aggregate(new StringBuilder(), (sb, item) => sb.Append(item.Key).Append(item.Value), sb => sb.ToString());
}

単語にこの定義を使用する...

var words = new List<string> { "need", "eden", "team", "meat", "meta", "Nat", "tan" };

このテスト...

foreach (var item in anagrams.OrderBy(x => x.Key)) {
    Console.WriteLine();
    Console.WriteLine(item.Key + ":");
    foreach (string word in item.Value.OrderBy(w => w)) {
        Console.WriteLine("    " + word);
    }
}

...この出力を生成します

a1e1m1t1:
    meat
    meta
    team

a1n1t1:
    Nat
    tan

d1e2n1:
    eden
    need

編集＃2：

これがBenVoigtによって提案された頻度計算です

private string GetFrequencyByBenVoigt(string word)
{
    char[] chars = word.ToLower().ToCharArray();
    Array.Sort(chars);
    return new string(chars);
}

テスト結果は次のようになります

aemt:
    meat
    meta
    team

ant:
    Nat
    tan

deen:
    eden
    need
于 2012-01-14T23:42:29.853 に答える
1

コンテナの内容に基づくハッシュコードO(n)は、コンテナ内のアイテムの数に含まれます。辞書を別のタイプでラップし、ハッシュコードをキャッシュして、一度だけ計算する必要があるようにすることもできます...しかし、辞書よりもそのデータを保存するためのより効率的な方法をいくつか考えることができます。

于 2012-01-14T23:56:54.850 に答える