変数のリスト [a, b, a, c, a, a, d, b, c, d, a] があり、順序が重要であり、それらの名前を整数に変更する必要がある場合、最適なアルゴリズムは何ですか?私が使用できること？
自明なアルゴリズムは次のようになります。
- 空のハッシュ テーブル HT を作成します。
- リスト内の各変数について、
- インデックスが作成されていない場合は、新しいインデックスを割り当てて、(変数、インデックス) を HT に入れます。
- インデックスがある場合は、インデックスを使用します。
上記の場合、解は [1, 2, 1, 3, 1, 1, 4, 2, 3, 4, 1] になります。
私は、'n' ハッシュ ルックアップとそれに伴う複雑さに関心があります。非常に長いリスト (より明確な変数を含む) の場合、パフォーマンスが非常に悪くなる可能性があります。これを処理するためのより良いアルゴリズムを持っている人はいますか?
この例では ASCII 文字を使用していますが、リストの要素は任意の文字列にすることができ、リストの長さは任意の長さ (> 100k) にすることができることに注意してください。