1

私はいくつかの情報を得たいと思う興味深い問題に遭遇しました。

（いくつかの事前定義された条件に基づいて）一連の数値を生成するプログラムがあります。各セットには最大6つの数値が含まれ、1から100の範囲の整数で一意である必要はありません。

作成されたすべてのセットをなんとかして保存し、まったく同じ番号（順序は関係ありません）の特定のセットが以前に生成されたかどうかをすばやく確認できるようにします。

この場合、プログラムが停止する前に最大100kセットが保存される可能性があるため、速度が優先されます（おそらくそれ以上ですが、ほとんどの場合はそれ以下です）。どのデータ構造を使用すべきか、この問題にどのように取り組むべきかについて、誰かが何かアドバイスはありますか？

私が現在持っているのはこれです：

文字列のHashSetに保存する前に、各セットを並べ替えます。文字列は、区切り文字が付いた、並べ替えられたセット内の各数値です。

たとえば、セット{4、23、67、67、71}は、文字列「4-23-67-67-71」としてエンコードされ、HashSetに格納されます。次に、生成された新しいセットごとに、それを並べ替え、エンコードして、HashSetに存在するかどうかを確認します。

ありがとう！

4

3 に答える 3

2
  1. クラスSetOfIntegersを作成します
  2. 適度に一意のハッシュ値を生成するhashCode（）メソッドを実装します
  3. HashMapを使用して、put（hashValue、instance）などの要素を保存します
  4. containsKey（hashValue）を使用して、同じhashValueがすでに存在するかどうかを確認します

このようにして、セットの並べ替えや変換/フォーマットを回避できます。

于 2012-07-14T14:48:53.240 に答える
2

あなたがそれを細かく砕くと、私にはそのように思えます

  • セットの作成（6つの数値の生成、並べ替え、文字列化）はO（1）で実行されます
  • この文字列がハッシュセットに存在するかどうかのチェックはO（1）です
  • ハッシュセットへの挿入はO（1）です

これをn回実行すると、O（n）が得られます。 とにかくすべての要素に一度触れる必要があるので、これはすでに最適です:)

乱数の範囲によっては、問題が発生する可能性があります。たとえば、1から1の間の数値のみを生成すると仮定すると、明らかに1つの可能な結果（ "1-1-1-1-1-1"）のみが発生し、それ以降は衝突のみが発生します。ただし、可能なシーケンスの数が生成する要素の数よりもはるかに多い限り、問題は発生しません。

1つのヒント：生成された要素の数が事前にわかっている場合は、正しい数の要素でハッシュセットを初期化することをお勧めします（つまり、new HashSet<String>( 100000 ) );

ps今、他の答えがポップアップしているので、微視的なレベルで改善の余地があるかもしれませんが（つまり、言語固有のトリックを使用して）、全体的なアプローチを改善することはできません。

于 2012-07-14T14:44:40.680 に答える
2

セットごとにjava.util.BitSetを使用し、set（int bitIndex）メソッドを使用してセットに整数を追加するだけで、何もソートする必要はありません。新しいBitSetを追加する前に、HashMapで既存のBitSetを確認してください。 、それは本当に非常に高速になります。速度が重要な場合は、その目的で値とtoStringの並べ替えを使用しないでください。

于 2012-07-14T14:57:32.887 に答える