Javaでバケットソートを実装していますが、入力配列がランダムではなく（昇順または降順で）ソートされると、ソート（昇順）が速くなることがわかりました。どうしてこれなの？私が理解しているように、配列を通過し、各要素のインデックスで「集計」配列をインクリメントします。ソートされた入力でなぜ高速になるのかはわかりませんが、約 2 倍高速になるようです。
ありがとう
1 に答える
3
その理由は、空間的な局所性と、並べ替えられた入力セットでのキャッシュ ヒットの増加による可能性が非常に高いです。
入力をソートした場合、同じ近傍にあるバケットが相対的に多数のヒットを取得し、ソートされた入力がより高い範囲に移動すると、バケットの次の近傍がヒットを取得し始めます。
これを説明する簡単な例を考えてみましょう:
それぞれ範囲サイズが 1,000 の 10 個のバケットがあるとします。
[0-999], [1000-1999], ..., [9000-9999]
また、一度に 1 つのバケットへの参照しかキャッシュできないとします (これは不自然な部分ですが、考え方は実際には同じです:
ここで、入力セットが次の間の乱数であるとします[0 - 9999]
- 入力がソートされている場合、各バケットは正確に 1 つの初期キャッシュ ミスを取得し、その後、入力のシーケンスが次のバケットの範囲に移動するまで多数のキャッシュ ヒットが続きます。
- ソートされていない入力があり、最悪の場合、キャッシュは常にミスし、別のバケットをキャッシュにロードし、ソートされていないシーケンスの次の番号がさらに別のバケットを探すため、再びミスするだけです。
于 2013-03-07T04:59:07.850 に答える