0

Javaでは、正の異なる数のリストがあります。

各数値はハッシュセットのキーとして使用され、IntIntHashSet fs以下csのコードでいくつかの条件値を取得するために使用されます。次に、条件（ifステートメント）を確認し、trueの場合は要素を交換します。

int[] list = // given list of positive different ints like [14, 2, 7, 19, 20, 3]
int l = list.length;
if (l > 1) {
    int elI, elJ, fI, fJ, swap;
    for (int i = 0; i < l; i++) {
        boolean swapped = false;
        for (int j = 1; j < l; j++) {
            elI = list[j - 1];
            elJ = list[j];
            fI = fs.get(elI);
            fJ = fs.get(elJ);
            if (fI > fJ || (fI == fJ && cs.get(elI) > cs.get(elJ))) {
                swap = list[j];
                list[j] = list[j - 1];
                list[j - 1] = swap;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

よくわかりませんが、バブルソートのように見えます。私は時間のかかるプログラムを書いていますが、この部分は可能な限り最適化する必要があります。

主な質問： QuickSortのような別のソートアプローチを使用する方が速いでしょうか？

2番目の質問：一時変数なしでxorswapスワップメソッドを使用する方が速いでしょうか？

[編集]：何千もの数字を含む非常に長いリストがあるかもしれません。上記のものは例のために単純です。

4

2 に答える 2

1

部分的にソートされた配列と小さなデータセットの場合、バブルソートが効率的な方法です。クイックソートは、大規模な（巨大な）データセットに対してのみ効率的です。あなたはバブルソートを実装しているようです。これは小さなデータセットには十分でしょう。

さまざまな並べ替えアルゴリズムの効率については、こちらを確認してください。

于 2012-09-25T22:41:58.500 に答える
0

Javaを使用すると、Javaを広範囲にベンチマークしてプロファイリングするまでわかりません。

小さなセットでうまく機能するコードの中には、大きなセットではうまく機能しないものもあります。いつ最適化されるか、およびどの前提条件であるかによって異なります。XORをマシンコードで効率的にエンコードする方法を認識したり、これを別の方法でエンコードしたりする場合があります。クライアントVMとサーバーVMの間でも異なる場合があります。

実際のところ、sortJavaでのコレクションの方法は、JDK6からJDK7に置き換えられました（IIRC QuicksortからTimSort、Python IIRCからのハイブリッドインプレースマージソート）。

ちょうど最近、論理的にはもっと速くなければならない状況と戦ってきましたが、ベンチマークはその逆を示しました。これは、ホットスポットが異なるためにJIT最適化が異なる方法で実行されることによってのみ説明できます。そして、効率の悪いコードは明らかに、より良い最適化を引き起こしました。

于 2012-09-25T22:42:34.920 に答える