c - 퀵정렬 - 힙정렬




고정 길이의 가장 빠른 정렬 6 int 배열 (16)

나는 이것이 오래된 질문이라는 것을 알고있다.

하지만 방금 공유하고자하는 다른 종류의 솔루션을 작성했습니다.
중첩 된 MIN MAX를 사용하여,

그것은 114 개를 사용하기 때문에 빠르지는 않습니다.
75 개로 줄일 수 있습니다 -> pastebin

하지만 그때는 순전히 최대치가 아닙니다.

AVX를 사용하여 여러 정수에서 최소 / 최대를 동시에 수행 할 수 있습니다.

PMINSW 참조

#include <stdio.h>

static __inline__ int MIN(int a, int b){
int result =a;
__asm__ ("pminsw %1, %0" : "+x" (result) : "x" (b));
return result;
}
static __inline__ int MAX(int a, int b){
int result = a;
__asm__ ("pmaxsw %1, %0" : "+x" (result) : "x" (b));
return result;
}
static __inline__ unsigned long long rdtsc(void){
  unsigned long long int x;
__asm__ volatile (".byte 0x0f, 0x31" :
  "=A" (x));
  return x;
}

#define MIN3(a, b, c) (MIN(MIN(a,b),c))
#define MIN4(a, b, c, d) (MIN(MIN(a,b),MIN(c,d)))

static __inline__ void sort6(int * in) {
  const int A=in[0], B=in[1], C=in[2], D=in[3], E=in[4], F=in[5];

  in[0] = MIN( MIN4(A,B,C,D),MIN(E,F) );

  const int
  AB = MAX(A, B),
  AC = MAX(A, C),
  AD = MAX(A, D),
  AE = MAX(A, E),
  AF = MAX(A, F),
  BC = MAX(B, C),
  BD = MAX(B, D),
  BE = MAX(B, E),
  BF = MAX(B, F),
  CD = MAX(C, D),
  CE = MAX(C, E),
  CF = MAX(C, F),
  DE = MAX(D, E),
  DF = MAX(D, F),
  EF = MAX(E, F);

  in[1] = MIN4 (
  MIN4( AB, AC, AD, AE ),
  MIN4( AF, BC, BD, BE ),
  MIN4( BF, CD, CE, CF ),
  MIN3( DE, DF, EF)
  );

  const int
  ABC = MAX(AB,C),
  ABD = MAX(AB,D),
  ABE = MAX(AB,E),
  ABF = MAX(AB,F),
  ACD = MAX(AC,D),
  ACE = MAX(AC,E),
  ACF = MAX(AC,F),
  ADE = MAX(AD,E),
  ADF = MAX(AD,F),
  AEF = MAX(AE,F),
  BCD = MAX(BC,D),
  BCE = MAX(BC,E),
  BCF = MAX(BC,F),
  BDE = MAX(BD,E),
  BDF = MAX(BD,F),
  BEF = MAX(BE,F),
  CDE = MAX(CD,E),
  CDF = MAX(CD,F),
  CEF = MAX(CE,F),
  DEF = MAX(DE,F);

  in[2] = MIN( MIN4 (
  MIN4( ABC, ABD, ABE, ABF ),
  MIN4( ACD, ACE, ACF, ADE ),
  MIN4( ADF, AEF, BCD, BCE ),
  MIN4( BCF, BDE, BDF, BEF )),
  MIN4( CDE, CDF, CEF, DEF )
  );


  const int
  ABCD = MAX(ABC,D),
  ABCE = MAX(ABC,E),
  ABCF = MAX(ABC,F),
  ABDE = MAX(ABD,E),
  ABDF = MAX(ABD,F),
  ABEF = MAX(ABE,F),
  ACDE = MAX(ACD,E),
  ACDF = MAX(ACD,F),
  ACEF = MAX(ACE,F),
  ADEF = MAX(ADE,F),
  BCDE = MAX(BCD,E),
  BCDF = MAX(BCD,F),
  BCEF = MAX(BCE,F),
  BDEF = MAX(BDE,F),
  CDEF = MAX(CDE,F);

  in[3] = MIN4 (
  MIN4( ABCD, ABCE, ABCF, ABDE ),
  MIN4( ABDF, ABEF, ACDE, ACDF ),
  MIN4( ACEF, ADEF, BCDE, BCDF ),
  MIN3( BCEF, BDEF, CDEF )
  );

  const int
  ABCDE= MAX(ABCD,E),
  ABCDF= MAX(ABCD,F),
  ABCEF= MAX(ABCE,F),
  ABDEF= MAX(ABDE,F),
  ACDEF= MAX(ACDE,F),
  BCDEF= MAX(BCDE,F);

  in[4]= MIN (
  MIN4( ABCDE, ABCDF, ABCEF, ABDEF ),
  MIN ( ACDEF, BCDEF )
  );

  in[5] = MAX(ABCDE,F);
}

int main(int argc, char ** argv) {
  int d[6][6] = {
    {1, 2, 3, 4, 5, 6},
    {6, 5, 4, 3, 2, 1},
    {100, 2, 300, 4, 500, 6},
    {100, 2, 3, 4, 500, 6},
    {1, 200, 3, 4, 5, 600},
    {1, 1, 2, 1, 2, 1}
  };

  unsigned long long cycles = rdtsc();
  for (int i = 0; i < 6; i++) {
    sort6(d[i]);
  }
  cycles = rdtsc() - cycles;
  printf("Time is %d\n", (unsigned)cycles);

  for (int i = 0; i < 6; i++) {
    printf("d%d : %d %d %d %d %d %d\n", i,
     d[i][0], d[i][1], d[i][2],
     d[i][3], d[i][4], d[i][5]);
  }
}

편집하다:
Rex Kerr 's에서 영감을 얻은 순위 순서 솔루션, 위의 혼란보다 훨씬 빠름

static void sort6(int *o) {
const int 
A=o[0],B=o[1],C=o[2],D=o[3],E=o[4],F=o[5];
const unsigned char
AB = A>B, AC = A>C, AD = A>D, AE = A>E,
          BC = B>C, BD = B>D, BE = B>E,
                    CD = C>D, CE = C>E,
                              DE = D>E,
a =          AB + AC + AD + AE + (A>F),
b = 1 - AB      + BC + BD + BE + (B>F),
c = 2 - AC - BC      + CD + CE + (C>F),
d = 3 - AD - BD - CD      + DE + (D>F),
e = 4 - AE - BE - CE - DE      + (E>F);
o[a]=A; o[b]=B; o[c]=C; o[d]=D; o[e]=E;
o[15-a-b-c-d-e]=F;
}

다른 스택 오버플로 질문 ( 이 하나 )에 대한 답변 재미있는 하위 문제를 발견했습니다. 6 int의 배열을 정렬하는 가장 빠른 방법은 무엇입니까?

질문은 매우 낮은 수준이므로 :

  • 우리는 라이브러리를 사용할 수 있다고 가정 할 수 없으며 (호출 자체에는 비용이 있습니다), 보통 C
  • 명령 파이프 라인을 비우는 것을 피하기 위해 ( 매우 높은 비용이 드는 경우) 우리는 분기점, 점프 및 다른 모든 종류의 제어 흐름 중단 (예 : && 또는 || 시퀀스 포인트 뒤에 숨겨진 것들)을 최소화해야합니다.
  • 방이 제한되어 있고 레지스터와 메모리 사용을 최소화하는 것이 가장 이상적입니다.

실제로이 질문은 소스 길이를 최소화하는 것이 아니라 실행 시간을 최소화하는 것이 목표 인 일종의 골프입니다. Michael Abrash 와 그 sequels 의해 코드 최적화의 Zen of Books 최적화 책의 제목에 사용 된 'Zening'코드라고 부릅니다.

왜 그것이 흥미로운 지에 관해서는 몇 가지 레이어가 있습니다 :

  • 이 예제는 간단하고 이해하기 쉽고 측정하기가 쉽지 않습니다.
  • 그것은 문제에 대한 좋은 알고리즘의 선택의 효과뿐만 아니라 컴파일러와 기본 하드웨어의 효과를 보여줍니다.

여기 내 참조 (순진하고 최적화되지 않은) 구현 및 테스트 세트가 있습니다.

#include <stdio.h>

static __inline__ int sort6(int * d){

    char j, i, imin;
    int tmp;
    for (j = 0 ; j < 5 ; j++){
        imin = j;
        for (i = j + 1; i < 6 ; i++){
            if (d[i] < d[imin]){
                imin = i;
            }
        }
        tmp = d[j];
        d[j] = d[imin];
        d[imin] = tmp;
    }
}

static __inline__ unsigned long long rdtsc(void)
{
  unsigned long long int x;
     __asm__ volatile (".byte 0x0f, 0x31" : "=A" (x));
     return x;
}

int main(int argc, char ** argv){
    int i;
    int d[6][5] = {
        {1, 2, 3, 4, 5, 6},
        {6, 5, 4, 3, 2, 1},
        {100, 2, 300, 4, 500, 6},
        {100, 2, 3, 4, 500, 6},
        {1, 200, 3, 4, 5, 600},
        {1, 1, 2, 1, 2, 1}
    };

    unsigned long long cycles = rdtsc();
    for (i = 0; i < 6 ; i++){
        sort6(d[i]);
        /*
         * printf("d%d : %d %d %d %d %d %d\n", i,
         *  d[i][0], d[i][6], d[i][7],
         *  d[i][8], d[i][9], d[i][10]);
        */
    }
    cycles = rdtsc() - cycles;
    printf("Time is %d\n", (unsigned)cycles);
}

원시 결과

변형 수가 많아지면서 here 에서 찾을 수있는 테스트 스위트에서 모든 것을 모았습니다. 사용 된 실제 테스트는 Kevin Stock 덕분에 위에서 보여준 것보다 덜 순진합니다. 자신의 환경에서 컴파일하고 실행할 수 있습니다. 필자는 다른 타겟 아키텍처 / 컴파일러의 동작에 상당히 관심이 있습니다. (OK 얘들 아, 답변에 넣어, 나는 새로운 결과 집합의 모든 기여자를 +1합니다).

1 년 전 Daniel Stutzbach (골프를위한)에 대한 답변을 그 당시 가장 빠른 솔루션의 출처로 사용했습니다 (네트워크 정렬).

Linux 64 비트, gcc 4.6.1 64 비트, Intel Core 2 Duo E8400, -O2

  • qsort 라이브러리 함수에 대한 직접 호출 : 689.38
  • 기본 구현 (삽입 정렬) : 285.70
  • 삽입 정렬 (Daniel Stutzbach) : 142.12
  • 게시 정렬 삽입 : 125.47
  • 순위 순서 : 102.26
  • 레지스터를 이용한 순위 순서 : 58.03
  • 정렬 네트워크 (Daniel Stutzbach) : 111.68
  • 정렬 네트워크 (Paul R) : 66.36
  • Fast Swap으로 네트워크 12 정렬 : 58.86
  • 정렬 네트워크 12 재정렬 된 교환 : 53.74
  • 정렬 네트워크 12 재정렬 된 단순 스왑 : 31.54
  • 재 배열 된 네트워크 (빠른 스왑 포함) : 31.54
  • 재정렬 된 정렬 네트워크 (빠른 스왑 V2 포함) : 33.63
  • 인라인 된 거품 정렬 (Paolo Bonzini) : 48.85
  • 펼쳐진 삽입 정렬 (Paolo Bonzini) : 75.30

Linux 64 비트, gcc 4.6.1 64 비트, Intel Core 2 Duo E8400, -O1

  • qsort 라이브러리 함수에 대한 직접 호출 : 705.93
  • 순진한 구현 (삽입 정렬) : 135.60
  • 삽입 정렬 (Daniel Stutzbach) : 142.11
  • 게시 정렬 삽입 : 126.75
  • 순위 순서 : 46.42
  • 레지스터를 이용한 순위 순서 : 43.58
  • 정렬 네트워크 (Daniel Stutzbach) : 115.57
  • 정렬 네트워크 (Paul R) : 64.44
  • 패스트 스왑을 사용한 네트워크 12 정렬 : 61.98
  • 정렬 네트워크 12 재정렬 된 교환 : 54.67
  • 정렬 네트워크 12 재정렬 된 단순 스왑 : 31.54
  • 빠른 정렬로 재정렬 된 정렬 네트워크 : 31.24
  • 재 배열 된 네트워크 (빠른 스왑 V2 포함) : 33.07
  • 인라인 된 버블 정렬 (Paolo Bonzini) : 45.79
  • 펼쳐진 삽입 정렬 (Paolo Bonzini) : 80.15

놀랍게도 몇몇 프로그램 O2가 O1보다 효율적이기 때문에 나는 -O1과 -O2 결과를 모두 포함했습니다. 특정 최적화에 어떤 효과가 있는지 궁금합니다.

제안 된 솔루션에 대한 의견

삽입 정렬 (Daniel Stutzbach)

예상대로 지점을 최소화하는 것은 실제로 좋은 생각입니다.

정렬 네트워크 (Daniel Stutzbach)

삽입 정렬보다 좋습니다. 주된 효과가 외부 루프를 피하지 못하는지 궁금했습니다. 확인을 위해 삽입되지 않은 삽입 정렬을 시도해 보았습니다. 실제로 동일한 숫자 (코드는 here )를 얻습니다.

정렬 네트워크 (Paul R)

지금까지 최고. 내가 테스트 한 실제 코드는 here . 아직 다른 정렬 네트워크 구현보다 거의 두 배나 빠른 이유를 아직 모릅니다. 매개 변수 전달? 빠른 최대?

네트워크 정렬 12 스왑과 빠른 스왑

다니엘 슈투트바흐 (Daniel Stutzbach)가 제안한 것처럼 12 가지의 스왑 분류 네트워크를 분기없는 빠른 스왑 (코드가 here )과 결합했습니다. 그것은 실제로 더 빠르며, 지금까지는 1 적은 스왑을 사용하여 예상 할 수있는 작은 마진 (대략 5 %)으로 최고입니다.

또한 PPC 아키텍처를 사용하는 단순한 것보다 분기없는 스왑이 4 배 정도 덜 효율적 인 것으로 나타났습니다.

라이브러리 호출 qsort

다른 참조 점을 제공하기 위해 라이브러리 qsort (코드는 here )를 호출하는 것이 좋습니다. 예상대로 훨씬 느립니다 : 10 ~ 30 배 느립니다 ... 새 테스트 스위트에서 명백해진 것처럼 주요 문제는 첫 번째 호출 이후 라이브러리의 초기로드 인 것처럼 보이며 다른 라이브러리와 크게 비교되지 않습니다 번역. 그것은 내 리눅스에서 3 ~ 20 배 정도 느리다. 다른 아키텍트의 테스트에 사용 된 아키텍쳐에서는 (라이브러리 qsort가 좀 더 복잡한 API를 사용하기 때문에) 정말 빨라 보인다.

순위

Rex Kerr은 또 다른 완전히 다른 방법을 제안했습니다. 배열의 각 항목이 최종 위치를 직접 계산하기 때문입니다. 이는 순위 순서를 계산할 때 분기가 필요하지 않으므로 효율적입니다. 이 방법의 단점은 배열의 메모리 용량의 3 배 (순위 순서를 저장하기위한 배열 및 변수의 복사본)가 3 번 걸린다는 것입니다. 성능 결과는 매우 놀랍습니다 (흥미 롭습니다). 32 비트 OS 및 Intel Core2 Quad E8300을 사용하는 참조 아키텍처에서 순환 수는 1000보다 약간 작았습니다 (분기 스왑을 사용한 네트워크 정렬과 같음). 그러나 64 비트 박스 (Intel Core2 Duo)에서 컴파일 및 실행하면 성능이 훨씬 향상되었습니다. 지금까지 가장 빠른 속도가되었습니다. 나는 진정한 이유를 마침내 발견했다. 내 32 비트 상자는 gcc 4.4.1을 사용하고 내 64 비트 상자는 gcc 4.4.3을 사용하며이 마지막 코드는이 특정 코드를 최적화하는 데 훨씬 좋습니다 (다른 제안의 경우 거의 차이가 없었습니다).

업데이트 :

위의 게시 된 그림에서 볼 수 있듯이이 효과는 이후 버전의 gcc와 순위 순서에 의해 여전히 향상되었지만 다른 대안보다 두 배 빠릅니다.

재 배열 된 스왑으로 네트워크 12 정렬

GCC 4.4.3을 사용한 Rex Kerr 제안의 놀라운 효율성은 내가 궁금해하게 만들었습니다. 얼마나 많은 메모리 사용량을 가진 프로그램이 분기없는 정렬 네트워크보다 더 빠를 수 있을까요? 필자의 가설은 쓰기 후에 읽은 종류의 종속성이 적어서 x86의 슈퍼 스칼라 명령 스케줄러를보다 효율적으로 사용할 수 있다는 것입니다. 저에게 아이디어를주었습니다 : 스왑을 재정렬하여 쓰기 의존성 이후의 읽기를 최소화하십시오. 더 간단하게 말하면 : 당신이 SWAP(1, 2); SWAP(0, 2); 을 할 때 SWAP(1, 2); SWAP(0, 2); SWAP(1, 2); SWAP(0, 2); 공통 메모리 셀에 대한 액세스이기 때문에 두 번째 스왑을 수행하기 전에 첫 번째 스왑이 완료 될 때까지 기다려야합니다. SWAP(1, 2); SWAP(4, 5); 할 때 SWAP(1, 2); SWAP(4, 5); SWAP(1, 2); SWAP(4, 5); 프로세서는 두 가지를 동시에 실행할 수 있습니다. 나는 그것을 시도하고 그것은 예상대로 작동, 정렬 네트워크가 약 10 % 빠르게 실행됩니다.

간단한 스왑으로 네트워크 12 정렬

원래 Steinar H. Gunderson이 제안한 1 년 후, 우리는 컴파일러를 능숙하게 처리하지 말고 스왑 코드를 간단하게 유지해야한다고 제안했습니다. 결과 코드가 약 40 % 더 빠릅니다. 실제로 좋은 생각입니다. 그는 또한 x86 인라인 어셈블리 코드를 사용하여 손으로 최적화 된 스왑을 제안했는데, 이는 여전히 더 많은 사이클을 절약 할 수 있습니다. 가장 놀라운 것은 프로그래머의 심리학에 관한 것입니다. 1 년 전에는 그 버전의 스왑을 사용하지 않았다고합니다. 테스트에 사용 된 코드가 here . 다른 사람들은 C의 빠른 스왑을 작성하는 다른 방법을 제안했지만 괜찮은 컴파일러를 가진 간단한 것과 동일한 성능을 내고 있습니다.

"최고의"코드는 다음과 같습니다.

static inline void sort6_sorting_network_simple_swap(int * d){
#define min(x, y) (x<y?x:y)
#define max(x, y) (x<y?y:x) 
#define SWAP(x,y) { const int a = min(d[x], d[y]); \
                    const int b = max(d[x], d[y]); \
                    d[x] = a; d[y] = b; }
    SWAP(1, 2);
    SWAP(4, 5);
    SWAP(0, 2);
    SWAP(3, 5);
    SWAP(0, 1);
    SWAP(3, 4);
    SWAP(1, 4);
    SWAP(0, 3);
    SWAP(2, 5);
    SWAP(1, 3);
    SWAP(2, 4);
    SWAP(2, 3);
#undef SWAP
#undef min
#undef max
}

우리가 테스트 세트를 믿는다면 (그렇습니다. 아주 가난합니다. 단순한 이점은 우리가 측정하는 것을 이해하기 쉽고 간단하며, 결과 코드의 평균 사이클 수가 40 사이클 미만입니다. 6 개의 테스트가 실행됩니다. 그것은 각각의 스왑을 평균 4 사이클에 두었습니다. 나는 그것을 놀라 울 정도로 빨리 부른다. 다른 모든 개선이 가능합니까?


내가 일 년 늦게 파티에 온 것 같지만, 여기 우리가 간다 ...

gcc 4.5.2에 의해 생성 된 어셈블리를 살펴보면 실제로로드 할 필요가없는 모든 스왑마다로드 및 저장 작업이 수행되는 것을 관찰했습니다. 6 개의 값을 레지스터에로드하고 정렬 한 다음 다시 메모리에 저장하는 것이 좋습니다. 나는 가게에서의 하중을 거기에 가능한 가깝게되도록 명령했다. 레지스터는 처음에 필요하고 마지막으로 사용되었다. Steinar H. Gunderson의 SWAP 매크로도 사용했습니다. 업데이트 : Paolo Bonzini의 SWAP 매크로로 전환했습니다. gcc가 Gunderson과 비슷한 것으로 변환하지만 gcc는 명시 적 어셈블리로 제공되지 않았기 때문에 지침을 더 잘 정렬 할 수 있습니다.

더 나은 주문이있을 수 있지만, 최고의 실적으로 주어진 순서가 바뀐 스왑 네트워크와 동일한 스왑 주문을 사용했습니다. 좀 더 시간이 있으면 순열을 만들고 테스트 할 것입니다.

테스트 코드를 4000 개가 넘는 배열을 고려하여 변경하고 각각을 정렬하는 데 필요한 평균주기 수를 보여줍니다. i5-650에서는 원래 재정렬 정렬 네트워크가 ~ 65.3 cycles / sort (-O1 사용, -O2 및 -O3 초과)보다 34.1 cycles / sort (-O3 사용)가되었습니다.

#include <stdio.h>

static inline void sort6_fast(int * d) {
#define SWAP(x,y) { int dx = x, dy = y, tmp; tmp = x = dx < dy ? dx : dy; y ^= dx ^ tmp; }
    register int x0,x1,x2,x3,x4,x5;
    x1 = d[1];
    x2 = d[2];
    SWAP(x1, x2);
    x4 = d[4];
    x5 = d[5];
    SWAP(x4, x5);
    x0 = d[0];
    SWAP(x0, x2);
    x3 = d[3];
    SWAP(x3, x5);
    SWAP(x0, x1);
    SWAP(x3, x4);
    SWAP(x1, x4);
    SWAP(x0, x3);
    d[0] = x0;
    SWAP(x2, x5);
    d[5] = x5;
    SWAP(x1, x3);
    d[1] = x1;
    SWAP(x2, x4);
    d[4] = x4;
    SWAP(x2, x3);
    d[2] = x2;
    d[3] = x3;

#undef SWAP
#undef min
#undef max
}

static __inline__ unsigned long long rdtsc(void)
{
    unsigned long long int x;
    __asm__ volatile ("rdtsc; shlq $32, %%rdx; orq %%rdx, %0" : "=a" (x) : : "rdx");
    return x;
}

void ran_fill(int n, int *a) {
    static int seed = 76521;
    while (n--) *a++ = (seed = seed *1812433253 + 12345);
}

#define NTESTS 4096
int main() {
    int i;
    int d[6*NTESTS];
    ran_fill(6*NTESTS, d);

    unsigned long long cycles = rdtsc();
    for (i = 0; i < 6*NTESTS ; i+=6) {
        sort6_fast(d+i);
    }
    cycles = rdtsc() - cycles;
    printf("Time is %.2lf\n", (double)cycles/(double)NTESTS);

    for (i = 0; i < 6*NTESTS ; i+=6) {
        if (d[i+0] > d[i+1] || d[i+1] > d[i+2] || d[i+2] > d[i+3] || d[i+3] > d[i+4] || d[i+4] > d[i+5])
            printf("d%d : %d %d %d %d %d %d\n", i,
                    d[i+0], d[i+1], d[i+2],
                    d[i+3], d[i+4], d[i+5]);
    }
    return 0;
}

필자 는 테스트 스위트수정하여 정렬 당 클록을보고하고 더 많은 테스트를 실행 (cmp 함수가 정수 오버플로도 처리하도록 업데이트 됨)하여 몇 가지 다른 아키텍처의 결과를 얻었습니다. AMD CPU에서 테스트를 시도했지만 rdtsc는 X6 1100T에서 신뢰할 수 없습니다.

Clarkdale (i5-650)
==================
Direct call to qsort library function      635.14   575.65   581.61   577.76   521.12
Naive implementation (insertion sort)      538.30   135.36   134.89   240.62   101.23
Insertion Sort (Daniel Stutzbach)          424.48   159.85   160.76   152.01   151.92
Insertion Sort Unrolled                    339.16   125.16   125.81   129.93   123.16
Rank Order                                 184.34   106.58   54.74    93.24    94.09
Rank Order with registers                  127.45   104.65   53.79    98.05    97.95
Sorting Networks (Daniel Stutzbach)        269.77   130.56   128.15   126.70   127.30
Sorting Networks (Paul R)                  551.64   103.20   64.57    73.68    73.51
Sorting Networks 12 with Fast Swap         321.74   61.61    63.90    67.92    67.76
Sorting Networks 12 reordered Swap         318.75   60.69    65.90    70.25    70.06
Reordered Sorting Network w/ fast swap     145.91   34.17    32.66    32.22    32.18

Kentsfield (Core 2 Quad)
========================
Direct call to qsort library function      870.01   736.39   723.39   725.48   721.85
Naive implementation (insertion sort)      503.67   174.09   182.13   284.41   191.10
Insertion Sort (Daniel Stutzbach)          345.32   152.84   157.67   151.23   150.96
Insertion Sort Unrolled                    316.20   133.03   129.86   118.96   105.06
Rank Order                                 164.37   138.32   46.29    99.87    99.81
Rank Order with registers                  115.44   116.02   44.04    116.04   116.03
Sorting Networks (Daniel Stutzbach)        230.35   114.31   119.15   110.51   111.45
Sorting Networks (Paul R)                  498.94   77.24    63.98    62.17    65.67
Sorting Networks 12 with Fast Swap         315.98   59.41    58.36    60.29    55.15
Sorting Networks 12 reordered Swap         307.67   55.78    51.48    51.67    50.74
Reordered Sorting Network w/ fast swap     149.68   31.46    30.91    31.54    31.58

Sandy Bridge (i7-2600k)
=======================
Direct call to qsort library function      559.97   451.88   464.84   491.35   458.11
Naive implementation (insertion sort)      341.15   160.26   160.45   154.40   106.54
Insertion Sort (Daniel Stutzbach)          284.17   136.74   132.69   123.85   121.77
Insertion Sort Unrolled                    239.40   110.49   114.81   110.79   117.30
Rank Order                                 114.24   76.42    45.31    36.96    36.73
Rank Order with registers                  105.09   32.31    48.54    32.51    33.29
Sorting Networks (Daniel Stutzbach)        210.56   115.68   116.69   107.05   124.08
Sorting Networks (Paul R)                  364.03   66.02    61.64    45.70    44.19
Sorting Networks 12 with Fast Swap         246.97   41.36    59.03    41.66    38.98
Sorting Networks 12 reordered Swap         235.39   38.84    47.36    38.61    37.29
Reordered Sorting Network w/ fast swap     115.58   27.23    27.75    27.25    26.54

Nehalem (Xeon E5640)
====================
Direct call to qsort library function      911.62   890.88   681.80   876.03   872.89
Naive implementation (insertion sort)      457.69   236.87   127.68   388.74   175.28
Insertion Sort (Daniel Stutzbach)          317.89   279.74   147.78   247.97   245.09
Insertion Sort Unrolled                    259.63   220.60   116.55   221.66   212.93
Rank Order                                 140.62   197.04   52.10    163.66   153.63
Rank Order with registers                  84.83    96.78    50.93    109.96   54.73
Sorting Networks (Daniel Stutzbach)        214.59   220.94   118.68   120.60   116.09
Sorting Networks (Paul R)                  459.17   163.76   56.40    61.83    58.69
Sorting Networks 12 with Fast Swap         284.58   95.01    50.66    53.19    55.47
Sorting Networks 12 reordered Swap         281.20   96.72    44.15    56.38    54.57
Reordered Sorting Network w/ fast swap     128.34   50.87    26.87    27.91    28.02

며칠 전에 Google에서이 질문에 대한 비틀 거리기가 발생했습니다. 고정 길이 배열을 6 개의 정수로 빠르게 정렬해야하기 때문입니다. 그러나 내 경우에는 정수가 8 비트 (32 개가 아닌)이고 C 만 사용한다는 엄격한 요구 사항이 없습니다. 누군가에게 도움이 될 수 있기 때문에 어쨌든 내 결과를 공유 할 것이라고 생각했습니다 ...

SSE를 사용하여 비교 및 ​​스왑 작업을 가능한 범위까지 벡터화하는 어셈블리에서 네트워크 종류의 변형을 구현했습니다. 배열을 완전히 정렬하려면 6 개의 "통과"가 필요합니다. 나는 PADDB (vectorized add)와 어떤 경우에는 PAND (bitwise AND) 명령어만을 사용하여 PSHUFB (벡터화 된 스왑)에 대한 매개 변수를 셔플하기 위해 PCMPGTB (벡터화 된 비교)의 결과를 직접 변환하는 새로운 메커니즘을 사용했습니다.

이 접근법은 진정한 분기없는 기능을 만들어내는 부작용도 가지고있었습니다. 무엇이든 점프 지침이 없습니다.

이 구현 현재 질문에서 가장 빠른 옵션으로 표시된 구현 ( "단순한 스왑으로 네트워크 12 정렬")보다 약 38 % 더 빠릅니다 . 비교 테스트를 공정하게 만들기 위해 테스트 중에 char 배열 요소를 사용하도록 구현을 수정했습니다.

이 접근 방식은 최대 16 개의 요소까지 모든 배열 크기에 적용될 수 있습니다. 나는 대안에 비해 상대적인 속도 이점이 더 큰 배열에 대해 더 커질 것으로 기대한다.

이 코드는 SSSE3을 사용하는 x86_64 프로세서의 MASM으로 작성되었습니다. 이 함수는 "새로운"Windows x64 호출 규칙을 사용합니다. 여기있어...

PUBLIC simd_sort_6

.DATA

ALIGN 16

pass1_shuffle   OWORD   0F0E0D0C0B0A09080706040503010200h
pass1_add       OWORD   0F0E0D0C0B0A09080706050503020200h
pass2_shuffle   OWORD   0F0E0D0C0B0A09080706030405000102h
pass2_and       OWORD   00000000000000000000FE00FEFE00FEh
pass2_add       OWORD   0F0E0D0C0B0A09080706050405020102h
pass3_shuffle   OWORD   0F0E0D0C0B0A09080706020304050001h
pass3_and       OWORD   00000000000000000000FDFFFFFDFFFFh
pass3_add       OWORD   0F0E0D0C0B0A09080706050404050101h
pass4_shuffle   OWORD   0F0E0D0C0B0A09080706050100020403h
pass4_and       OWORD   0000000000000000000000FDFD00FDFDh
pass4_add       OWORD   0F0E0D0C0B0A09080706050403020403h
pass5_shuffle   OWORD   0F0E0D0C0B0A09080706050201040300h
pass5_and       OWORD 0000000000000000000000FEFEFEFE00h
pass5_add       OWORD   0F0E0D0C0B0A09080706050403040300h
pass6_shuffle   OWORD   0F0E0D0C0B0A09080706050402030100h
pass6_add       OWORD   0F0E0D0C0B0A09080706050403030100h

.CODE

simd_sort_6 PROC FRAME

    .endprolog

    ; pxor xmm4, xmm4
    ; pinsrd xmm4, dword ptr [rcx], 0
    ; pinsrb xmm4, byte ptr [rcx + 4], 4
    ; pinsrb xmm4, byte ptr [rcx + 5], 5
    ; The benchmarked 38% faster mentioned in the text was with the above slower sequence that tied up the shuffle port longer.  Same on extract
    ; avoiding pins/extrb also means we don't need SSE 4.1, but SSSE3 CPUs without SSE4.1 (e.g. Conroe/Merom) have slow pshufb.
    movd    xmm4, dword ptr [rcx]
    pinsrw  xmm4,  word ptr [rcx + 4], 2  ; word 2 = bytes 4 and 5


    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass1_shuffle]
    pcmpgtb xmm5, xmm4
    paddb xmm5, oword ptr [pass1_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass2_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass2_and]
    paddb xmm5, oword ptr [pass2_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass3_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass3_and]
    paddb xmm5, oword ptr [pass3_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass4_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass4_and]
    paddb xmm5, oword ptr [pass4_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass5_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass5_and]
    paddb xmm5, oword ptr [pass5_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass6_shuffle]
    pcmpgtb xmm5, xmm4
    paddb xmm5, oword ptr [pass6_add]
    pshufb xmm4, xmm5

    ;pextrd dword ptr [rcx], xmm4, 0    ; benchmarked with this
    ;pextrb byte ptr [rcx + 4], xmm4, 4 ; slower version
    ;pextrb byte ptr [rcx + 5], xmm4, 5
    movd   dword ptr [rcx], xmm4
    pextrw  word ptr [rcx + 4], xmm4, 2  ; x86 is little-endian, so this is the right order

    ret

simd_sort_6 ENDP

END

이것을 실행 가능한 개체로 컴파일하여 C 프로젝트에 연결할 수 있습니다. Visual Studio에서이 작업을 수행하는 방법에 대한 지침은 이 문서를 참조하십시오 . 다음 C 프로토 타입을 사용하여 C 코드에서 함수를 호출 할 수 있습니다.

void simd_sort_6(char *values);

모든 최적화를 위해서는 항상 테스트, 테스트, 테스트하는 것이 가장 좋습니다. 최소한 네트워크 정렬과 삽입 정렬을 시도 할 것입니다. 내가 도박을했다면, 나는 과거 경험에 기초한 삽입 정렬에 돈을 넣었습니다.

입력 데이터에 대해 아십니까? 일부 알고리즘은 특정 종류의 데이터에서 더 잘 수행됩니다. 예를 들어, 삽입 정렬은 정렬 된 또는 거의 정렬 된 데이터에서 더 잘 수행되므로 거의 평균적으로 정렬 된 데이터가 평균 이상이면 더 나은 선택이됩니다.

게시 한 알고리즘은 삽입 정렬과 비슷하지만 더 많은 비교 비용으로 스왑 수를 최소화 한 것처럼 보입니다. 스왑보다 비교가 훨씬 비쌉니다. 분기 때문에 명령 파이프 라인이 정지 될 수 있기 때문입니다.

다음은 삽입 정렬 구현입니다.

static __inline__ int sort6(int *d){
        int i, j;
        for (i = 1; i < 6; i++) {
                int tmp = d[i];
                for (j = i; j >= 1 && tmp < d[j-1]; j--)
                        d[j] = d[j-1];
                d[j] = tmp;
        }
}

다음은 정렬 네트워크를 구축하는 방법입니다. 먼저, 이 사이트 를 사용하여 적절한 길이의 네트워크에 대한 최소 SWAP 매크로 세트를 생성하십시오. 함수로 마무리하면 다음과 같습니다.

static __inline__ int sort6(int * d){
#define SWAP(x,y) if (d[y] < d[x]) { int tmp = d[x]; d[x] = d[y]; d[y] = tmp; }
    SWAP(1, 2);
    SWAP(0, 2);
    SWAP(0, 1);
    SWAP(4, 5);
    SWAP(3, 5);
    SWAP(3, 4);
    SWAP(0, 3);
    SWAP(1, 4);
    SWAP(2, 5);
    SWAP(2, 4);
    SWAP(1, 3);
    SWAP(2, 3);
#undef SWAP
}

테스트 코드는 매우 나쁩니다. 그것은 초기 배열을 오버플로합니다. (컴파일러 경고를 읽지 않는 사람들이 있습니까?) printf는 잘못된 요소를 출력합니다. rdtsc는 아무 이유없이 .byte를 사용합니다. 단 하나의 실행 (!) 만 있습니다. 최종 결과는 실제로 정확합니다 (그래서 미묘하게 잘못된 것으로 "최적화"하는 것은 매우 쉽습니다), 포함 된 테스트는 매우 초보적입니다 (음수가 아님)? 컴파일러가 전체 코드를 불필요한 코드로 버리는 것을 막을 수있는 방법은 없습니다.

즉, 비트 네트워크 솔루션을 향상시키는 것도 매우 쉽습니다. 단순히 min / max / SWAP 항목을 다음과 같이 변경하십시오.

#define SWAP(x,y) { int tmp; asm("mov %0, %2 ; cmp %1, %0 ; cmovg %1, %0 ; cmovg %2, %1" : "=r" (d[x]), "=r" (d[y]), "=r" (tmp) : "0" (d[x]), "1" (d[y]) : "cc"); }

나를 위해 약 65 % 더 빠릅니다 (데비안 gcc 4.4.5, -O2, amd64, Core i7).


XOR 스왑은 스와핑 기능에 유용 할 수 있습니다.

void xorSwap (int *x, int *y) {
     if (*x != *y) {
         *x ^= *y;
         *y ^= *x;
         *x ^= *y;
     }
 }

if는 코드에서 너무 많은 분기를 야기 할 수 있지만, 모든 int가 고유하다는 보장이 있다면 이는 유용 할 수 있습니다.


나는 테스트 스위트를 PPC 아키텍처 머신으로 포팅했다. 코드를 건드릴 필요가 없었고, 테스트 반복을 증가 시켰으며, mods로 결과를 오염시키지 않고 x86 특정 rdtsc를 대체하기 위해 8 가지 테스트 케이스를 사용했다.

qsort 라이브러리 함수에 대한 직접 호출 : 101

순진한 구현 (삽입 정렬) : 299

삽입 정렬 (Daniel Stutzbach) : 108

게시 정렬 삽입 : 51

정렬 네트워크 (Daniel Stutzbach) : 26

정렬 네트워크 (Paul R) : 85

패스트 스왑으로 네트워크 12 정렬 : 117

네트워크 정렬 12 재정렬 된 교환 : 116

계급 : 56


내가 제공 한 스왑 매크로가 정말 마음에 드는 동안 :

#define min(x, y) (y ^ ((x ^ y) & -(x < y)))
#define max(x, y) (x ^ ((x ^ y) & -(x < y)))
#define SWAP(x,y) { int tmp = min(d[x], d[y]); d[y] = max(d[x], d[y]); d[x] = tmp; }

나는 좋은 컴파일러가 만들 수있는 개선 사항을 본다.

#define SWAP(x,y) { int tmp = ((x ^ y) & -(y < x)); y ^= tmp; x ^= tmp; }

우리는 min과 max가 어떻게 작동 하는지를 기록하고 공통적 인 하위 식을 명시 적으로 끌어 낸다. 이렇게하면 min 및 max 매크로가 완전히 제거됩니다.


정렬 알고리즘의 세 가지 다른 클래스를 나타내는 세 가지 일반적인 정렬 방법은 다음과 같습니다.

Insertion Sort: Θ(n^2)

Heap Sort: Θ(n log n)

Count Sort: Θ(3n)

그러나 가장 빠른 정렬 알고리즘에 대한 Stefan Nelsson의 토론을 확인하십시오 . 그곳에서 그는 C로 구현을O(n log log n) 체크 아웃 하는 해결책을 논의합니다 .

이 세미 선형 정렬 알고리즘은 1995 년 논문에서 발표되었습니다.

A. Andersson, T. Hagerup, S. Nilsson 및 R. Raman. 선형 시간으로 정렬 하시겠습니까? Compute 이론에 관한 제 27 차 ACM 심포지엄, 427-436, 1995 년 논문집.


'정렬 된 목록'정렬을 시도하십시오. :) 두 개의 배열을 사용하십시오. 크고 작은 배열에 가장 빠릅니다.
연결하면 삽입 위치 만 확인합니다. 비교할 필요가없는 다른 큰 값 (cmp = ab> 0).
4 개 숫자의 경우 시스템 4-5 cmp (~ 4.6) 또는 3-6 cmp (~ 4.9)를 사용할 수 있습니다. 기포 종류는 6 cmp (6)를 사용하십시오. 많은 수의 코드가 느린 코드의 경우 cmp가 많습니다.
이 코드는 5 cmp (MSL 정렬 아님)를 사용합니다.
if (cmp(arr[n][i+0],arr[n][i+1])>0) {swap(n,i+0,i+1);} if (cmp(arr[n][i+2],arr[n][i+3])>0) {swap(n,i+2,i+3);} if (cmp(arr[n][i+0],arr[n][i+2])>0) {swap(n,i+0,i+2);} if (cmp(arr[n][i+1],arr[n][i+3])>0) {swap(n,i+1,i+3);} if (cmp(arr[n][i+1],arr[n][i+2])>0) {swap(n,i+1,i+2);}

Principial MSL 9 8 7 6 5 4 3 2 1 0 89 67 45 23 01 ... concat two sorted lists, list length = 1 6789 2345 01 ... concat two sorted lists, list length = 2 23456789 01 ... concat two sorted lists, list length = 4 0123456789 ... concat two sorted lists, list length = 8

js 코드

function sortListMerge_2a(cmp)	
{
var step, stepmax, tmp, a,b,c, i,j,k, m,n, cycles;
var start = 0;
var end   = arr_count;
//var str = '';
cycles = 0;
if (end>3)
	{
	stepmax = ((end - start + 1) >> 1) << 1;
	m = 1;
	n = 2;
	for (step=1;step<stepmax;step<<=1)	//bounds 1-1, 2-2, 4-4, 8-8...
		{
		a = start;
		while (a<end)
			{
			b = a + step;
			c = a + step + step;
			b = b<end ? b : end;
			c = c<end ? c : end;
			i = a;
			j = b;
			k = i;
			while (i<b && j<c)
				{
				if (cmp(arr[m][i],arr[m][j])>0)
					{arr[n][k] = arr[m][j]; j++; k++;}
				else	{arr[n][k] = arr[m][i]; i++; k++;}
				}
			while (i<b)
				{arr[n][k] = arr[m][i]; i++; k++;
}
			while (j<c)
				{arr[n][k] = arr[m][j]; j++; k++;
}
			a = c;
			}
		tmp = m; m = n; n = tmp;
		}
	return m;
	}
else
	{
	// sort 3 items
	sort10(cmp);
	return m;
	}
}


나는 아주 늦다는 것을 알고 있지만 몇 가지 다른 해결책을 실험 해보고자했습니다. 먼저, 붙여 넣기 작업을 정리하고 컴파일 한 다음 저장소에 저장합니다. 나는 다른 사람들이 시도하지 않으려 고 막 다른 골목으로 몇 가지 바람직하지 못한 해결책을 지켰다. 이 중 첫 번째 해결책은 x1> x2가 한 번 계산되도록하는 것입니다. 최적화 후 다른 단순한 버전보다 빠르지 않습니다.

이 연구의 내 자신의 응용 프로그램은 2-8 항목을 정렬하기위한 것이므로 순위 순서 정렬의 루핑 버전을 추가 했으므로 다양한 인수가 있으므로 루프가 필요합니다. 이것은 또한 정렬 네트워크 솔루션을 무시한 이유이기도합니다.

테스트 코드는 복제본이 올바르게 처리되었는지 테스트하지 않았기 때문에 기존 솔루션이 모두 정확했지만 중복 사례가 올바르게 처리되었는지 확인하기 위해 테스트 코드에 특별한 경우를 추가했습니다.

그런 다음 AVX 레지스터에 완전히 삽입 된 정렬을 작성했습니다. 내 컴퓨터에서는 다른 삽입 정렬보다 25 % 빠르지 만 순위 순서보다 100 % 느립니다. 나는 이것을 실험을 위해 순전히 수행했으며, 삽입 정렬의 분기로 인해 더 나은 것으로 기대하지는 않았습니다.

static inline void sort6_insertion_sort_avx(int* d) {
    __m256i src = _mm256_setr_epi32(d[0], d[1], d[2], d[3], d[4], d[5], 0, 0);
    __m256i index = _mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7);
    __m256i shlpermute = _mm256_setr_epi32(7, 0, 1, 2, 3, 4, 5, 6);
    __m256i sorted = _mm256_setr_epi32(d[0], INT_MAX, INT_MAX, INT_MAX,
            INT_MAX, INT_MAX, INT_MAX, INT_MAX);
    __m256i val, gt, permute;
    unsigned j;
     // 8 / 32 = 2^-2
#define ITER(I) \
        val = _mm256_permutevar8x32_epi32(src, _mm256_set1_epi32(I));\
        gt =  _mm256_cmpgt_epi32(sorted, val);\
        permute =  _mm256_blendv_epi8(index, shlpermute, gt);\
        j = ffs( _mm256_movemask_epi8(gt)) >> 2;\
        sorted = _mm256_blendv_epi8(_mm256_permutevar8x32_epi32(sorted, permute),\
                val, _mm256_cmpeq_epi32(index, _mm256_set1_epi32(j)))
    ITER(1);
    ITER(2);
    ITER(3);
    ITER(4);
    ITER(5);
    int x[8];
    _mm256_storeu_si256((__m256i*)x, sorted);
    d[0] = x[0]; d[1] = x[1]; d[2] = x[2]; d[3] = x[3]; d[4] = x[4]; d[5] = x[5];
#undef ITER
}

그런 다음 AVX를 사용하여 순위 순서 정렬을 작성했습니다. 이것은 다른 순위 주문 솔루션의 속도와 일치하지만 더 빠르지는 않습니다. 여기서 문제는 AVX로만 인덱스를 계산할 수 있다는 것입니다. 그런 다음 인덱스 테이블을 만들어야합니다. 이는 계산이 소스 기반이 아닌 대상 기반이기 때문입니다. 소스 기반 인덱스에서 대상 기반 인덱스로 변환을 참조하십시오.

static inline void sort6_rank_order_avx(int* d) {
    __m256i ror = _mm256_setr_epi32(5, 0, 1, 2, 3, 4, 6, 7);
    __m256i one = _mm256_set1_epi32(1);
    __m256i src = _mm256_setr_epi32(d[0], d[1], d[2], d[3], d[4], d[5], INT_MAX, INT_MAX);
    __m256i rot = src;
    __m256i index = _mm256_setzero_si256();
    __m256i gt, permute;
    __m256i shl = _mm256_setr_epi32(1, 2, 3, 4, 5, 6, 6, 6);
    __m256i dstIx = _mm256_setr_epi32(0,1,2,3,4,5,6,7);
    __m256i srcIx = dstIx;
    __m256i eq = one;
    __m256i rotIx = _mm256_setzero_si256();
#define INC(I)\
    rot = _mm256_permutevar8x32_epi32(rot, ror);\
    gt = _mm256_cmpgt_epi32(src, rot);\
    index = _mm256_add_epi32(index, _mm256_and_si256(gt, one));\
    index = _mm256_add_epi32(index, _mm256_and_si256(eq,\
                _mm256_cmpeq_epi32(src, rot)));\
    eq = _mm256_insert_epi32(eq, 0, I)
    INC(0);
    INC(1);
    INC(2);
    INC(3);
    INC(4);
    int e[6];
    e[0] = d[0]; e[1] = d[1]; e[2] = d[2]; e[3] = d[3]; e[4] = d[4]; e[5] = d[5];
    int i[8];
    _mm256_storeu_si256((__m256i*)i, index);
    d[i[0]] = e[0]; d[i[1]] = e[1]; d[i[2]] = e[2]; d[i[3]] = e[3]; d[i[4]] = e[4]; d[i[5]] = e[5];
}

이 레포는 https://github.com/eyepatchParrot/sort6/ 에서 확인할 수 있습니다.https://github.com/eyepatchParrot/sort6/


벤치마킹을하지 않고 실제 컴파일러 생성 어셈블리를보고 min / max를 최적화하지 마십시오. 조건부 이동 명령어로 GCC를 min으로 최적화하면 33 %의 속도 향상을 얻습니다.

#define SWAP(x,y) { int dx = d[x], dy = d[y], tmp; tmp = d[x] = dx < dy ? dx : dy; d[y] ^= dx ^ tmp; }

(테스트 코드에서 280 대 420 사이클). 가장 큰 것은? : 다소 차이가 있지만 노이즈가 거의 없어졌지만 위의 내용은 조금 더 빠릅니다. 이 스왑은 GCC와 Clang 모두에서 빠릅니다.

컴파일러는 레지스터 할당과 앨리어스 분석에서 탁월한 작업을 수행하여 효과적으로 d [x]를 로컬 변수로 이동하고 끝에있는 메모리로만 다시 복사합니다. 실제로 지역 변수 (예 :)를 사용하여 작업 한 것보다 훨씬 효과적 d0 = d[0], d1 = d[1], d2 = d[2], d3 = d[3], d4 = d[4], d5 = d[5]입니다. 나는 당신이 강한 최적화를 가정하면서도 min / max에서 컴파일러보다 현저히 노력하고 있기 때문에 이것을 쓰고있다. :)

그건 그렇고, 나는 Clang과 GCC를 시도했다. 그들은 동일한 최적화를 수행하지만 스케줄링 차이로 인해 두 가지 결과에 약간의 차이가 있습니다. 실제로 더 빠르거나 느린 것을 말할 수 없습니다. GCC는 정렬 네트워크에서 더 빠르며, Clang은 2 차 정렬에서 더 빠릅니다.

완결성을 위해 전개되지 않은 버블 정렬 및 삽입 정렬도 가능합니다. 버블 정렬은 다음과 같습니다.

SWAP(0,1); SWAP(1,2); SWAP(2,3); SWAP(3,4); SWAP(4,5);
SWAP(0,1); SWAP(1,2); SWAP(2,3); SWAP(3,4);
SWAP(0,1); SWAP(1,2); SWAP(2,3);
SWAP(0,1); SWAP(1,2);
SWAP(0,1);

다음은 삽입 정렬입니다.

//#define ITER(x) { if (t < d[x]) { d[x+1] = d[x]; d[x] = t; } }
//Faster on x86, probably slower on ARM or similar:
#define ITER(x) { d[x+1] ^= t < d[x] ? d[x] ^ d[x+1] : 0; d[x] = t < d[x] ? t : d[x]; }
static inline void sort6_insertion_sort_unrolled_v2(int * d){
    int t;
    t = d[1]; ITER(0);
    t = d[2]; ITER(1); ITER(0);
    t = d[3]; ITER(2); ITER(1); ITER(0);
    t = d[4]; ITER(3); ITER(2); ITER(1); ITER(0);
    t = d[5]; ITER(4); ITER(3); ITER(2); ITER(1); ITER(0);

이 삽입 유형은 Daniel Stutzbach 's보다 빠르며, ITER는 3 개의 명령어 (SWAP의 경우 4 개)만으로 수행 할 수 있기 때문에 특히 GPU 또는 예측이있는 컴퓨터에서 유용합니다. 예를 들어 다음은 t = d[2]; ITER(1); ITER(0);ARM 어셈블리 의 행입니다.

    MOV    r6, r2
    CMP    r6, r1
    MOVLT  r2, r1
    MOVLT  r1, r6
    CMP    r6, r0
    MOVLT  r1, r0
    MOVLT  r0, r6

여섯 가지 요소의 경우 삽입 정렬은 정렬 네트워크와 경쟁적입니다 (12 스왑과 15 반복은 4 명령 / 스왑 대 3 명령 / 반복의 균형을 유지함). 버블 종류는 물론 더 느립니다. 그러나 삽입 유형은 O (n ^ 2)이고 정렬 네트워크는 O (n log n)이기 때문에 크기가 커지면 사실이 아니다.


삽입 정렬이 합리적으로 여기에 경쟁력이 있다면, 나는 shellsort를 시도하는 것이 좋습니다. 나는 6 가지 요소가 아마 너무 적어서 최고 중 하나는 아닐지 모르지만, 시도해 볼만한 가치가 있을지도 모른다.

예제 코드, 테스트되지 않은 코드, undebugged 코드 등. inc = 4 및 inc - = 3 시퀀스를 최적화하여 최적 (예 : inc = 2, inc - = 1)을 찾습니다.

static __inline__ int sort6(int * d) {
    char j, i;
    int tmp;
    for (inc = 4; inc > 0; inc -= 3) {
        for (i = inc; i < 5; i++) {
            tmp = a[i];
            j = i;
            while (j >= inc && a[j - inc] > tmp) {
                a[j] = a[j - inc];
                j -= inc;
            }
            a[j] = tmp;
        }
    }
}

나는 이것이 이길 것이라고 생각하지 않지만 누군가가 10 가지 요소를 정렬하는 것에 관한 질문을 게시하면 누가 알겠습니까?

Wikipedia에 따르면 , Pratt, V (1979) 는 정렬 네트워크와 결합 할 수도 있습니다 . Shellsort 및 정렬 네트워크 (컴퓨터 과학의 뛰어난 논문). 화환. ISBN 0-824-04406-1


앞으로도 내 손을 시험해보고이 예제를 통해 배우고 싶지만, 1.5 GHz PPC Powerbook G4 (1 GB DDR RAM 장착)의 첫 번째 타이밍부터 살펴 보겠습니다. (나는 타이밍을 위해 http://www.mcs.anl.gov/~kazutomo/rdtsc.html 에서 PPC를 위해 유사한 rdtsc와 유사한 타이머를 빌렸다 .) 나는 몇 번 프로그램을 돌렸고 절대적인 결과는 다양했지만 일관되게 가장 빠른 테스트는 "Insertion Sort (Daniel Stutzbach)"이고 "Insertion Sort Unrolled"는 가장 가까운 테스트입니다.

다음은 마지막 세트입니다.

**Direct call to qsort library function** : 164
**Naive implementation (insertion sort)** : 138
**Insertion Sort (Daniel Stutzbach)**     : 85
**Insertion Sort Unrolled**               : 97
**Sorting Networks (Daniel Stutzbach)**   : 457
**Sorting Networks (Paul R)**             : 179
**Sorting Networks 12 with Fast Swap**    : 238
**Sorting Networks 12 reordered Swap**    : 236
**Rank Order**                            : 116

이 질문은 꽤 오래되었지만 요즘 같은 문제를 해결해야합니다. 즉, 작은 배열을 정렬하는 빠른 방법입니다. 내 지식을 공유하는 것이 좋은 생각이라고 생각했습니다. 정렬 네트워크를 사용하여 처음 시작한 동안 필자는 6 개의 값의 모든 순열을 정렬하기 위해 수행 된 비교의 총 수는 정렬 네트워크보다 작고 삽입 정렬보다 작은 다른 알고리즘을 찾았습니다. 나는 스왑의 수를 세지 않았다. 나는 그것이 대략 같다고 생각할 것입니다 (어쩌면 조금 더 높을 수도 있습니다).

알고리즘 sort6은 알고리즘을 사용하는 알고리즘 sort4을 사용합니다 sort3. 다음은 가벼운 C ++ 폼의 구현입니다 (원본은 템플릿 무겁기 때문에 임의의 임의 액세스 반복자 및 적절한 비교 함수에서 작동 할 수 있습니다).

3 개의 값 정렬하기

다음 알고리즘은 삽입되지 않은 삽입 정렬입니다. 두 번의 스왑 (6 개의 과제)이 수행되어야 할 때, 대신 4 개의 과제를 사용합니다 :

void sort3(int* array)
{
    if (array[1] < array[0]) {
        if (array[2] < array[0]) {
            if (array[2] < array[1]) {
                std::swap(array[0], array[2]);
            } else {
                int tmp = array[0];
                array[0] = array[1];
                array[1] = array[2];
                array[2] = tmp;
            }
        } else {
            std::swap(array[0], array[1]);
        }
    } else {
        if (array[2] < array[1]) {
            if (array[2] < array[0]) {
                int tmp = array[2];
                array[2] = array[1];
                array[1] = array[0];
                array[0] = tmp;
            } else {
                std::swap(array[1], array[2]);
            }
        }
    }
}

정렬에 가능한 모든 순열에 대해 하나 이상의 분기가 있으므로 2 ~ 3 개의 비교를 사용하고 최대 4 개의 할당을 사용하여 세 개의 값을 정렬하기 때문에 조금 복잡해 보입니다.

4 개의 값 정렬하기

이 한 번의 호출 sort3은 배열의 마지막 요소를 사용하여 삽입되지 않은 삽입 정렬을 수행합니다.

void sort4(int* array)
{
    // Sort the first 3 elements
    sort3(array);

    // Insert the 4th element with insertion sort 
    if (array[3] < array[2]) {
        std::swap(array[2], array[3]);
        if (array[2] < array[1]) {
            std::swap(array[1], array[2]);
            if (array[1] < array[0]) {
                std::swap(array[0], array[1]);
            }
        }
    }
}

이 알고리즘은 3 ~ 6 번의 비교와 최대 5 회의 스왑을 수행합니다. 삽입 정렬을 쉽게 풀 수 있지만 마지막 정렬을 위해 다른 알고리즘을 사용합니다 ...

6 개의 값 정렬하기

이것은 이중 삽입 정렬 이라고 불리는 전개되지 않은 버전을 사용합니다 . 그 이름은 그다지 훌륭하지 않지만, 꽤 기술적인데, 어떻게 작동하는지 여기 있습니다 :

  • 배열의 첫 번째 요소와 마지막 요소를 제외한 모든 요소를 ​​정렬합니다.
  • 첫 번째 요소가 마지막 요소보다 크면 배열의 첫 번째 요소와 요소를 서로 바꿉니다.
  • 정면에서 정렬 된 순서에 첫 번째 요소를 삽입 한 다음 뒤에서 마지막 요소를 삽입하십시오.

스왑 후 첫 번째 요소는 항상 마지막 요소보다 작습니다. 즉, 정렬 된 시퀀스에 요소를 삽입 할 때 최악의 경우 두 요소를 삽입하기 위해 N 개를 초과하지 않습니다. 예를 들어 첫 번째 요소가 세 번째 위치에 삽입 된 경우 마지막 요소는 네 번째 위치보다 아래에 삽입 할 수 없습니다.

void sort6(int* array)
{
    // Sort everything but first and last elements
    sort4(array+1);

    // Switch first and last elements if needed
    if (array[5] < array[0]) {
        std::swap(array[0], array[5]);
    }

    // Insert first element from the front
    if (array[1] < array[0]) {
        std::swap(array[0], array[1]);
        if (array[2] < array[1]) {
            std::swap(array[1], array[2]);
            if (array[3] < array[2]) {
                std::swap(array[2], array[3]);
                if (array[4] < array[3]) {
                    std::swap(array[3], array[4]);
                }
            }
        }
    }

    // Insert last element from the back
    if (array[5] < array[4]) {
        std::swap(array[4], array[5]);
        if (array[4] < array[3]) {
            std::swap(array[3], array[4]);
            if (array[3] < array[2]) {
                std::swap(array[2], array[3]);
                if (array[2] < array[1]) {
                    std::swap(array[1], array[2]);
                }
            }
        }
    }
}

6 가지 값의 모든 순열에 대한 나의 테스트는이 알고리즘이 항상 6 ~ 13 번의 비교를 수행한다는 것을 보여줍니다. 나는 수행 된 스왑의 수를 계산하지 않았지만 최악의 경우에는 11보다 높을 것이라고 기대하지 않습니다.

나는이 질문이 실제 문제를 더 이상 나타내지 않을지라도이 도움이되기를 바랍니다 :)

편집 : 제공된 벤치 마크에 넣은 후, 그것은 흥미로운 대안의 대부분보다 더 천천히입니다. 그것은 언롤 드 삽입 정렬보다 조금 나은 경향이 있지만, 그것은 꽤 많이 있습니다. 기본적으로 정수에 가장 적합한 것은 아니지만 값 비싼 비교 연산이있는 유형에 대해서는 흥미로울 수 있습니다.


필자는 최소한 내 시스템에서, 아래 정의 된 기능 sort6_iterator()과 기능 sort6_iterator_local()은 위의 현재 기록 보유자보다 빠르고, 자주 눈에 띄게 빨라 졌음을 발견했습니다.

#define MIN(x, y) (x<y?x:y)
#define MAX(x, y) (x<y?y:x)

template<class IterType> 
inline void sort6_iterator(IterType it) 
{
#define SWAP(x,y) { const auto a = MIN(*(it + x), *(it + y)); \
  const auto b = MAX(*(it + x), *(it + y)); \
  *(it + x) = a; *(it + y) = b; }

  SWAP(1, 2) SWAP(4, 5)
  SWAP(0, 2) SWAP(3, 5)
  SWAP(0, 1) SWAP(3, 4)
  SWAP(1, 4) SWAP(0, 3)
  SWAP(2, 5) SWAP(1, 3)
  SWAP(2, 4)
  SWAP(2, 3)
#undef SWAP
}

이 함수는 std::vector타이밍 코드에서 반복자를 전달했습니다 . 반복기를 사용하면 반복자가 참조하는 메모리에 대해 발생할 수있는 일과 수행 할 수없는 것에 대해 g ++에 확실한 확신을 줄 수 있다고 생각합니다. 그렇지 않으면 g ++이 정렬 코드를 더 잘 최적화 할 수 있습니다. 내가 정확히 기억도 일부 이유 왜 그렇게 많은 std같은 알고리즘,std::sort(), 일반적으로 그런 성적으로 좋은 성능을 가짐). 그러나, 정렬 기능에 대한 호출이 이루어진 컨텍스트 (즉, 주변 코드)가 성능에 상당한 영향을 주었던 것으로 나타 났는데, 이것은 인라인 된 후 최적화 된 함수 때문일 수 있습니다. 예를 들어, 프로그램이 충분히 단순하다면 정렬 함수를 포인터와 반복자를 전달하는 것과 반복자를 전달하는 것 사이에 성능 차이가 거의 없다. 그렇지 않으면 반복자를 사용하면 대개 성능이 눈에 띠게 향상되고 절대 성능이 현저히 저하되지 않습니다. 나는 g ++이 충분히 간단한 코드를 전역 적으로 최적화 할 수 있기 때문에 이것이 가능한지 의심 스럽다.

또한, sort6_iterator()일부 일관 다음 정렬 함수 상회 (함수가 호출되는 상황에 따라, 다시) 시간 :

template<class IterType> 
inline void sort6_iterator_local(IterType it) 
{
#define SWAP(x,y) { const auto a = MIN(data##x, data##y); \
  const auto b = MAX(data##x, data##y); \
  data##x = a; data##y = b; }
//DD = Define Data
#define DD1(a)   auto data##a = *(it + a);
#define DD2(a,b) auto data##a = *(it + a), data##b = *(it + b);
//CB = Copy Back
#define CB(a) *(it + a) = data##a;

  DD2(1,2)    SWAP(1, 2)
  DD2(4,5)    SWAP(4, 5)
  DD1(0)      SWAP(0, 2)
  DD1(3)      SWAP(3, 5)
  SWAP(0, 1)  SWAP(3, 4)
  SWAP(1, 4)  SWAP(0, 3)   CB(0)
  SWAP(2, 5)  CB(5)
  SWAP(1, 3)  CB(1)
  SWAP(2, 4)  CB(4)
  SWAP(2, 3)  CB(2)        CB(3)
#undef CB
#undef DD2
#undef DD1
#undef SWAP
}

정의 참고 SWAP()로하여 다음 몇 가지 가 약간 더 성능이나 성능 무시할 차이 결과 대부분의 시간 비록 약간 더 나은 성능 회 결과를.

#define SWAP(x,y) { const auto a = MIN(data##x, data##y); \
  data##y = MAX(data##x, data##y); \
  data##x = a; }

gcc -O3가 계속해서 최적화 할 때 정렬 알고리즘을 원할 경우, 입력을 전달하는 방법에 따라 다음 두 알고리즘 중 하나를 시도하십시오.

template<class T> inline void sort6(T it) {
#define SORT2(x,y) {if(data##x>data##y){auto a=std::move(data##y);data##y=std::move(data##x);data##x=std::move(a);}}
#define DD1(a)   register auto data##a=*(it+a);
#define DD2(a,b) register auto data##a=*(it+a);register auto data##b=*(it+b);
#define CB1(a)   *(it+a)=data##a;
#define CB2(a,b) *(it+a)=data##a;*(it+b)=data##b;
  DD2(1,2) SORT2(1,2)
  DD2(4,5) SORT2(4,5)
  DD1(0)   SORT2(0,2)
  DD1(3)   SORT2(3,5)
  SORT2(0,1) SORT2(3,4) SORT2(2,5) CB1(5)
  SORT2(1,4) SORT2(0,3) CB1(0)
  SORT2(2,4) CB1(4)
  SORT2(1,3) CB1(1)
  SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}

또는

template<class T> inline void sort6(T& e0, T& e1, T& e2, T& e3, T& e4, T& e5) {
#define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);}
#define DD1(a)   register auto data##a=e##a;
#define DD2(a,b) register auto data##a=e##a;register auto data##b=e##b;
#define CB1(a)   e##a=data##a;
#define CB2(a,b) e##a=data##a;e##b=data##b;
  DD2(1,2) SORT2(1,2)
  DD2(4,5) SORT2(4,5)
  DD1(0)   SORT2(0,2)
  DD1(3)   SORT2(3,5)
  SORT2(0,1) SORT2(3,4) SORT2(2,5) CB1(5)
  SORT2(1,4) SORT2(0,3) CB1(0)
  SORT2(2,4) CB1(4)
  SORT2(1,3) CB1(1)
  SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}

register키워드 를 사용하는 이유는 이 값이 레지스터에 필요하다는 것을 아는 몇 가지 이유 중 하나이기 때문입니다. 없으면 register컴파일러는 대부분이 시간을 알아낼 것입니다. 그러나 때로는 그렇지 않습니다. 이 register키워드를 사용하면 이 문제를 해결하는 데 도움이됩니다. 그러나 일반적으로 register키워드를 사용하지 마십시오 . 속도를 높이기보다는 코드가 느려질 수 있기 때문입니다.

또한 템플릿 사용에 유의하십시오. 이것은 inline키워드를 사용 하더라도 템플릿 함수는 바닐라 C 함수보다 gcc에서 훨씬 더 적극적으로 최적화되었으므로 (gcc가 바닐라 C 함수의 함수 포인터를 처리 할 필요가 있지만 템플릿 함수는 필요하지 않기 때문에) 목적에 따라 수행됩니다.





gpgpu