こんにちは、私は次のようなクラスを持っています
class State
{
int[] some_array;
//some other members
}
ここで、2 つの State オブジェクトが同じかどうかを比較する必要があります。オブジェクトの他のメンバーに関係なく、 2some_array つの状態が同じであると定義します。
これで、何千もの State オブジェクトのリストができました。状態を効率的に取得し、検索によって別の同様の状態がリストに存在することを確認するにはどうすればよいですか?
some_arrayリスト内のすべての状態要素の配列を、指定された状態オブジェクトと比較できます。しかし、これには非常に多くの計算 O(N*some_array のサイズ) が必要になります。最小限の計算でこれを行うにはどうすればよいですか?
注: 1 つのアレイを除くすべての資格は、いずれの場合もほぼ同じです。そのため、ルックアップは配列の非常に深いところまで行くことができます。
可能かどうかはわかりませんが、配列内のコンテンツのハッシュを作成することは、私にとって良い解決策のように思えます。そうすれば、配列全体を反復して個々の値を比較する代わりに、ハッシュを比較するだけで済みます。
順序が重要であると仮定すると、アルゴリズムは O(N)ワースト ケースです。異なる状態で値が異なる傾向にある場合、テストは通常、2 つの候補の要素を比較するときに非常に早い段階で失敗します。データが完全にランダムである場合、2 つの状態を相互に比較するパフォーマンスは O(1) に近づきます...ほとんどの場合、最初の配列要素が異なり、最初の 2 つが同一である確率ははるかに小さくなります。配列内のデータの構造について何か知っている場合 (たとえば、最後に異なる可能性が最も高い場合など)、それを利用できます。もちろん、配列の長さは異なる場合があります。何よりも先にそれを確認してください。
初期化後に配列が変更されない場合は、配列要素のハッシュを事前に計算できます。ただし、私の最初のステートメントが当てはまらない場合を除き (通常、違いを検出する前に配列に深く入り込むことになります)、ハッシュは最適なオプションではない可能性があります。