정렬 된 입력으로 버킷 정렬이 더 빨리 실행되는 이유는 무엇입니까?

Question

Java에서 버킷 정렬을 구현하고 있는데 입력 배열이 무작위가 아닌 오름차순 또는 내림차순으로 정렬 될 때 정렬 (오름차순)이 빠르다는 것을 알았습니다. 왜 이런거야? 내가 알기로는 배열을 통해 각 요소의 인덱스에서 "집계"배열을 증가시킵니다. 정렬 된 입력이 더 빨리 실행되는 이유를 알 수는 없지만 속도가 약 두 배 빨라진 것 같습니다.

감사

Answer 1

이유 때문에 공간 지역에 매우 가능성이 높은 캐시 정렬 된 입력 세트 안타.

입력을 정렬 한 경우 상대적으로 동일한 동네의 버킷에 많은 수의 히트가 발생하며 정렬 된 입력이 높은 범위로 이동하면 버킷의 다음 이웃에서 히트가 시작됩니다.

이를 설명하기 위해 간단한 예를 생각해

[0-999], [1000-1999], ..., [9000-9999] 

그리고 당신은 (한 번에 하나의 버킷에 대한 참조를 캐시 할 수 있다고 가정 :

당신이 범위의 크기 1,000 각각 10 양동이가 있다고 가정 이것은 인위적인 부분이지만 아이디어는 실제로 동일합니다

지금 귀하의 의견 세트를 가정 임의의 숫자는

,369 [0 - 9999] 사이

• 입력이 정렬되면 각 버킷은 정확히 하나의 초기 캐시 실패를 가져오고, 입력의 시퀀스가 ​​다음 버킷의 범위로 이동할 때까지 많은 캐시 적중 횟수가 발생합니다.
• 정렬되지 않은 입력이 있고 최악의 경우 캐시가 항상 누락되어 다른 버킷을 캐시에로드하고 정렬되지 않은 시퀀스의 다음 번호가 다른 버킷을 찾게되므로 다시 놓칠 수 있습니다.