3

モードを見つける必要がある巨大な int 配列があります。

for不要と思われる2 つのループ (1 つはネスト) を使用するメソッドをいくつか見てきました。

ループが 1 つだけのモードを見つけるために考えられる唯一の方法は、Maps を使用することです。

int[] elements = new int[]{....numbers...};
Map<Integer,Integer> map = new .....Map Type....;
for(int number : elements){
    if(map.containsKey(Integer.valueOf(number))){
        map.put(Integer.valueOf(number),map.get(Integer.valueOf(number))+1);
    }else{
        map.put(Integer.valueOf(number),1);
    }
}

マップを使用すると実際にどのような速度の利点が得られるかはわかりません。より良い方法はありますか？

4

3 に答える 3

5

ハッシュ マップを使用する場合、アルゴリズムの実行時の複雑さは O(n) である必要があります。n 個の要素のそれぞれに 1 回アクセスすると、HashMap のルックアップと書き込みは通常 O(1) と見なされます。したがって、合計すると、O(n) である O(n * 1) が得られます。ツリー マップを使用すると、O(n log n) が得られます。

2 つのネストされたループ (O(n²) のように聞こえます) と比較すると、速度の向上は 2 次から線形になり、これは非常に優れています。1000 要素の場合、1,000,000 ではなく 1000 の「ステップ」を実行します。

PSここで線形よりも良くするのはおそらく難しいです-各要素に少なくとも1回アクセスせずにこれを計算する方法を想像することはできません.

于 2013-11-09T13:35:21.163 に答える
0

O(n) よりも高速なアルゴリズムはありません ( big-o 表記については、ウィキペディアのページを参照してください)。少なくとも、一貫性はありません (考えられるすべての入力にわたって)。これは、それ以上速くなれないという意味ではありません。特定の問題サイズを超えると、どんなに速くても、(おそらく小さい) 線形係数以上に速度差を増やし続けることはできません。

これは、要素を調べる順序に関係なく、勝者に関して「ほぼバランスが取れている」配列が与えられた場合、最後に調べた要素がタイブレーカーになる可能性があるためです。すべての要素を調べないアルゴリズムを教えてください。間違った結果を返す入力配列を作成できます。したがって、それらすべてを少なくとも 1 回は調べる必要があります。O(n) の複雑さです。

ハッシュマップの一般的な挿入と検索の複雑さは O(1) です。つまり、平均すると、データのサイズに関係なく、処理に一定の時間がかかります。この定数時間は、たとえば配列の更新/検索よりも数倍大きいことに注意してください（TwoTheの回答を参照）。したがって、定数 (ハッシュマップの実装、マシン、VM などによって異なります) を除いて、投稿したコードよりもはるかに高速になることはありません。その 10% の追加パフォーマンスが本当に必要な場合は、ハードウェア/ソフトウェア/入力データのベンチマークを、意図した展開にできるだけ近い場所に構築し、それを最適化します。

于 2013-11-09T14:02:11.817 に答える