16

わかりました、これが私の状況です：

重複を含む可能性のある状態の配列があります。重複を取り除くには、それらをすべてセットに追加します。

しかし、セットを作成するとき、初期容量と負荷率を定義したいのですが、それらをどのように設定すればよいですか?

グーグルから、私は思いついた：

String[] allStates = getAllStates();
Set<String> uniqueStates = new HashSet<String>(allStates.length, 0.75);

これの問題は、allStates に 1 ～ 5000 の州を含めることができることです。そのため、セットの容量は 5000 を超えますが、最大で 50 しか含まれません。

したがって、セットの最大サイズを状態の最大数に設定し、負荷係数を 1 に設定することもできます。

私の質問は本当に次のとおりだと思います：

  • セットにいくつのアイテムを入れるかわからない場合、初期容量をどのように設定する必要がありますか?
  • 格納できる最大数が 50 の場合に、何に設定されるかは本当に重要ですか?
  • 私はそれについて心配する必要がありますか？
4

7 に答える 7

17

州の数が 50 を超えないことがわかっていると仮定すると (米国の州のことですか?)、

Set<String> uniqueStates = new HashSet<String>(allStates.length, 0.75);

引用は間違いなく間違っています。安全のために、初期容量を 50 / 0.75 = 67、または 68 にすることをお勧めします。

また、あなたはおそらくこれを過度に考えすぎていることを指摘する必要があると感じています. 配列リストのサイズを 16 から 64 に 2 回変更しても、プログラムの最もパフォーマンスが重要な部分で正しくない限り、パフォーマンスに顕著な影響はありません。

したがって、最良の答えはおそらく使用することです：

new HashSet<String>();

そうすれば、1 年後に戻ってきて、なぜそのような奇妙なコンストラクター引数を選択したのかについて困惑することはありません。

于 2009-02-19T13:14:26.750 に答える
7

これらの値を指定する必要がないコンストラクターを使用すると、妥当なデフォルトが選択されます。

于 2009-02-19T11:45:18.323 に答える
3

最初に言っておきますが、あなたの場合は間違いなく考えすぎです。しかし、おそらく、それを正しくしたい状況があります。だからここに私が理解していることがあります：

1) HashSet に保持できるアイテムの数 = 初期容量 x 負荷率。したがって、n個のアイテムを保持できるようにしたい場合は、Zarkonnenが行ったことを実行し、nを負荷係数で割る必要があります.

2) 内部的には、初期容量はOracle チュートリアルごとに 2 の累乗に切り上げられます。

3) Tom Hawtin - tacklineで指摘されているように、過度の衝突を防ぐために、負荷係数は .80 以下にする必要があります。

デフォルト値 (初期容量 = 16、負荷係数 = .75) をそのまま受け入れると、セットのサイズが 3 倍になることになります。(最初の最大サイズ = 12、最初の増加で容量 32 と最大サイズ 24 (32 * .75)、2 回目の増加で容量 64 と最大サイズ 48 (64 * .75)、3 回目の増加で容量 128 と最大サイズ 96 (128) * .75))

最大サイズを 50 に近づけながら、セットをできるだけ小さくするには、初期容量を 64 (2 のべき乗)、負荷係数を 0.79 以上にすることを検討してください。64 * .79 = 50.56 なので、50 州すべてを取得できます。32 < 初期容量 < 64 を指定すると、初期容量が 64 に切り上げられるため、最初に 64 を指定するのと同じです。初期容量 <= 32 を指定すると、サイズが増加します。初期容量が 64 を超えていない限り、0.79 未満の負荷係数を使用すると、サイズも増加します。

したがって、初期容量 = 64、負荷率 = .79 を指定することをお勧めします。

于 2014-05-29T18:27:30.003 に答える
1

安全な賭けは、小さすぎるサイズに行くことです.

サイズ変更は指数関数的成長アルゴリズムによって改善されるため (数週間前のスタックオーバーフロー ポッドキャストを参照)、小さくしてもそれほどコストはかかりません。セットがたくさんある場合 (幸運なことに)、サイズが大きすぎるとパフォーマンスに影響します。

負荷率は難しいものです。デフォルトのままにしておくことをお勧めします。私は理解しています：約0.70f以下では、配列が大きくなりすぎて遅くなります。0.80f を超えると、多くのキー クラッシュが発生し始めます。おそらく、プロービング アルゴリズムは、バケット アルゴリズムよりも低い負荷係数を必要とします。

また、「初期容量」は、ほとんどの人が考えているように見えるものとは少し異なるものを意味することに注意してください. 配列内のエントリ数を参照します。要素数の正確な容量を取得するには、目的の負荷係数で割ります (そして適切に丸めます)。

于 2009-02-19T12:12:55.060 に答える
0

これを最適化する場合（そしてそれを行うのが適切な場合もあります）、決定の一部は、アレイに期待される重複の数によって異なります。

  • 重複が非常に多い場合は、初期容量を小さくする必要があります。大きくてまばらなハッシュテーブルは、反復するときに不適切です。

  • 重複があまり多くないと予想される場合は、サイズを変更せずにアレイ全体が収まるような初期容量が必要になります。

後者が欲しいと思いますが、これを追求するなら検討する価値があります。

于 2012-12-28T17:22:12.293 に答える
0

よく推測してください。難しいルールはありません。10 ～ 20 の州がある可能性が高いとわかっている場合は、その数 (20) から始めます。

于 2009-02-19T11:46:03.610 に答える