"부드러운"2D 배열의 항목을 가장 빨리 정렬하는 방법

Question

부드러운 2D 배열에서 값을 정렬하는 가장 빠른 방법은 무엇입니까?

• 약 60 내지 80 픽셀
• 단일 채널
• 단일 또는 배정도 부동
• 행 주요 스토리지 메모리에 순차
• 값 :

  입력 작은 필터링 된 이미지 혼합 된 부호가있다.

• 10 픽셀 너비의 영역을 가진 조각이 "부드러운"

출력은 원래 배열을 정렬하는 인덱스와 함께 정렬 된 값의 플랫 (약 4800 값) 배열입니다.

Answer 1

플랫 어레이에서 numpy의 정렬 루틴을 사용하여 일부 이미지에서 빠르고 더러운 벤치 마크를 수행했습니다. 이것은 수백 개의 무작위 이미지와 인간 얼굴의 수백 이미지에 대해 평균화됩니다. 둘 다 단 정밀도입니다.

On random images... 
quicksort took 0.000153 seconds per image. 
mergesort took 0.000170 seconds per image. 
heapsort took 0.000241 seconds per image. 
On real images... 
quicksort took 0.000136 seconds per image. 
mergesort took 0.000143 seconds per image. 
heapsort took 0.000230 seconds per image. 

모든 알고리즘은 기존 부분 정렬, 특히 quicksort의 이점을 얻는 것처럼 보입니다. Numpy는 정렬 된 목록 병합 기능을 갖고 있지 않으므로 행을 미리 정렬 할 수는 없습니다.

Answer 2

timsort가 있지만 여러 곳에서 느린 비교를하는 응용 프로그램을위한 것입니다. NumPy와 DEVS 분명히 심지어 그것을 구현하는 귀찮게하지 않기로 결정 :

http://mail.scipy.org/pipermail/scipy-dev/2009-May/011929.html

Answer 3

하나는 개별적으로 행을 머지 소트하고 정렬 된 행을 병합 할 수 있습니다.

적어도 2D 배열의 특수한 구조, 즉 단조로운 실행은 일반적으로 배열의 가장자리에서 시작되고 중지된다는 사실을 이용합니다. 또 다른 몇 가지 수준의 병렬 처리가 제공됩니다.

Answer 4

나는 in-place quicksort로 시작할 것입니다. 부동 소수점 비교는 대부분의 프로세서에서 빠르며 (확실히 mergesort에 필요한 할당보다 훨씬 빠름).

Answer 5

데이터에서 "실행"을 이용하기 때문에 Timsort가 이길 것으로 기대합니다.

Quicksort는 일반적으로 빠르지 만 최악의 시나리오를 밟을 위험이 있습니다. 예 : 이미 정렬 된 입력이 주어지면 quickshort의 일부 버전은 O (n^2)입니다. 누군가가 당신에게 잘못된 그라디언트로 채워진 이미지를 주었을 때 그다지 친절하지 않을 것입니다 ......

여기 약간 미친 아이디어가 있습니다. Z 순서 지정 패스 (Wikipedia link)를 사용해보십시오. 두 가지 차원에서 인접한 유사한 색상을 활용할 수 있습니다.