무엇이 가장 빠른 방법으로 정렬하의 배열 7 정수가?

https://stackoverflow.com/questions/1415173

06-07-2019
|

문제

이 프로그램의 일부를 분석하는 확률의 포커,구체적으로 텍사스 홀뎀.내 프로그램이 있겠지만,그것은 몇 가지 작은 최적화를 완벽하게 할 수 있습니다.

내가 사용하여 이 유형(다른 사람의 사이에서,의 코스):

  type
    T7Cards = array[0..6] of integer;

두 가지에 대한 이 배열 될 수 있는 중요한 결정할 때 어떻게 정렬:

모든 항목에서 값을 0 51.다른 값을 사용할 수 있습니다.
은 없습니다.지 않습니다.

이 정보는 무엇입 절대적으로 가장 빠른 정렬하는 방법 이 배열?내가 사용하여 델파이,그래서 코드 파스칼은 가장 좋은 것이지만,제가 읽을 수 있는 C 의사,이기는 하지만 조금 더 천천히:-)

순간에 나가 사용하는 퀵,하지만 재미있는 일이 거의 없이보다 빠른 bubblesort!가능하기 때문에 소수의 항목입니다.분류 수의 거의 50%의 전체의 실행 시간의 방법입니다.

편집:

메이슨 윌 왜 그것은 필요한을 최적화 할 수 있습니다.이유 중 하나는 메소드 호출됩니다 2118760 다.

기본적인 포커가 정보:모든 선수는 두 장의 카드(주머니)다음 다섯 개의 카드를 테이블(3 첫 번째는 불 플롭고,다음은 회전과 마지막입니다.각 집어 다섯 최고의 카드를 만들의 손)

가 있는 경우 두 개의 카드는 주머니에,P1and P2,내가 사용하는 다음과 같은 루프를 생성 가능한 모든 조합:

for C1 := 0 to 51-4 do
  if (C1<>P1) and (C1<>P2) then
     for C2 := C1+1 to 51-3 do
       if (C2<>P1) and (C2<>P2) then
         for C3 := C2+1 to 51-2 do
           if (C3<>P1) and (C3<>P2) then
             for C4 := C3+1 to 51-1 do
               if (C4<>P1) and (C4<>P2) then
                 for C5 := C4+1 to 51 do
                   if (C5<>P1) and (C5<>P2) then
                   begin
                     //This code will be executed 2 118 760 times
                     inc(ComboCounter[GetComboFromCards([P1,P2,C1,C2,C3,C4,C5])]);
                   end;

이것을 쓰고 나는 하나 더:지난 다섯 가지 요소의 배열은 항상 정렬,그래서 그것은 단지 질문을 넣어의 첫번째 두 가지 요소에 올바른 위치에 배열입니다.해야 하는 문제를 단순화 하는 비트입니다.

그래서,새로운 질문입니다:무엇이 가장 빠른 방법으로 정렬하는 배열 7 개의 정수를 할 때 지난 5 요소는 이미 정렬됩니다.나는이 해결할 수 있는 몇(?) 의 경우와 스왑:-)

해결책

지에 대해 자세히 알아 Texas Hold'em:그것은 상관없이 소송 P1 및 P2 또는 그것만 해도 그들은 동일한 소송 또는지?는 경우에 맞게만(P1)==장(P2)문제할 수 있는 다음 두 가지를 분리하는 경우,당신은 단지 13x12/2 개의 서로 다른의 가능성에 대한 P1/P2,당신은 쉽게 할 수 있습니 미리 계산에 대한 테이블은 두 가지 경우가 있습니다.

그렇지 않으면 내가 제안하는 것이 무언가 이것을 좋아한다:

(* C1 < C2 < P1 *)
for C1:=0 to P1-2 do 
   for C2:=C1+1 to P1-1 do 
      Cards[0] = C1;
      Cards[1] = C2;
      Cards[2] = P1;
      (* generate C3...C7 *)

(* C1 < P1 < C2 *)
for C1:=0 to P1-1 do 
   for C2:=P1+1 to 51 do 
      Cards[0] = C1;
      Cards[1] = P1;
      Cards[2] = C2;
      (* generate C3...C7 *)

(* P1 < C1 < C2 *)
for C1:=P1+1 to 51 do 
   for C2:=C1+1 to 51 do 
      Cards[0] = P1;
      Cards[1] = C1;
      Cards[2] = C2;
      (* generate C3...C7 *)

(이것은 단지에 대한 데모를 하나의 카드 P1,당신이 확장하는 대한 P2,그러나 내가 생각하는 간단합니다.하지만 그것은 것이 많이 입력하면...) 는 방법으로 정렬하지 않는 어떤 시간에서 모두.생성된 설정을 보여 줍니다 이미 주문했다.

다른 팁

아주 작은 세트의 경우 삽입 정렬 오버 헤드가 매우 낮기 때문에 일반적으로 QuickSort를 이길 수 있습니다.

편집, 이미 정렬 순서가 대부분 (마지막 5 가지 요소가 이미 정렬 된 경우)이라면 삽입 정렬은 확실히 이동하는 방법입니다. 거의 분류 된 데이터 세트에서는 대규모 세트의 경우 심지어 매번 Quicksort를 이길 수 있습니다. (특히 큰 세트의 경우! 이것은 삽입 정렬의 최고 사례 시나리오와 QuickSort의 최악의 경우입니다.)

당신이 이것을 어떻게 구현하고 있는지 모르지만, 당신이 할 수있는 일은 7 대신 52의 배열을 가지고 있고, 절대 복제 할 수 없기 때문에 그것을 얻을 수 없을 때 직접 슬롯에 카드를 삽입하는 것입니다. 배열을 정렬합니다. 사용 방법에 따라 더 빠를 수 있습니다.

7 개의 요소의 5040 순열 만 있습니다. 프로그래밍 방식은 최소한의 비교로 입력으로 표시되는 프로그램을 찾는 프로그램을 생성 할 수 있습니다. 그것은 큰 나무가 될 것입니다 if-then-else 예를 들어 고정 노드 쌍을 비교하는 지침 if (a[3]<=a[6]).

까다로운 부분은 특정 내부 노드에서 비교할 두 가지 요소를 결정하는 것입니다. 이를 위해서는 루트에서 특정 노드로의 조상 노드의 비교 결과를 고려해야합니다 (예 : a[0]<=a[1], not a[2]<=a[7], a[2]<=a[5]) 및 비교를 만족시키는 가능한 순열 세트. 세트를 가능한 한 동일한 부분으로 나누는 요소 쌍을 비교하십시오 (더 큰 부분의 크기를 최소화하십시오).

순열이 있으면 최소한의 스왑 세트로 정렬하는 것은 사소한 일입니다.

마지막 5 개의 항목은 이미 정렬되었으므로 코드는 처음 2 개 항목을 재배치하기 위해 작성할 수 있습니다. Pascal을 사용하고 있기 때문에 약 62 밀리 초 안에 2,118,760 회 실행할 수있는 정렬 알고리즘을 작성하고 테스트했습니다.

procedure SortT7Cards(var Cards: T7Cards);
const
  CardsLength = Length(Cards);
var
  I, J, V: Integer;
  V1, V2: Integer;
begin
  // Last 5 items will always be sorted, so we want to place the first two into
  // the right location.
  V1 := Cards[0];
  V2 := Cards[1];
  if V2 < V1 then
  begin
    I := V1;
    V1 := V2;
    V2 := I;
  end;

  J := 0;
  I := 2;
  while I < CardsLength do
  begin
    V := Cards[I];
    if V1 < V then
    begin
      Cards[J] := V1;
      Inc(J);
      Break;
    end;
    Cards[J] := V;
    Inc(J);
    Inc(I);
  end;
  while I < CardsLength do
  begin
    V := Cards[I];
    if V2 < V then
    begin
      Cards[J] := V2;
      Break;
    end;
    Cards[J] := V;
    Inc(J);
    Inc(I);
  end;
  if J = (CardsLength - 2) then
  begin
    Cards[J] := V1;
    Cards[J + 1] := V2;
  end
  else if J = (CardsLength - 1) then
  begin
    Cards[J] := V2;
  end;
end;

Min-Sort를 사용하십시오. 최소 및 최대 요소를 한 번에 검색하고 결과 배열로 배치하십시오. 세 번 반복하십시오. (편집 : 아니요, 이론적으로 속도를 측정하려고하지 않을 것입니다 : _)

var
cards,result: array[0..6] of integer;
i,min,max: integer;

begin
   n=0;
   while (n<3) do begin
      min:=-1;
      max:=52;
      for i from 0 to 6 do begin
          if cards[i]<min then min:=cards[i]
          else if cards[i]>max then max:=cards[i]
      end
      result[n]:=min;
      result[6-n]:=max;
      inc(n);
   end
   for i from 0 to 6 do 
       if (cards[i]<52) and (cards[i]>=0) then begin
           result[3] := cards[i];
           break;
       end
    { Result is sorted here! }
end

이것은 가장 빠른 방법입니다. 5 카드 목록이 이미 정렬되었으므로 2 카드 목록 (비교 및 스왑)을 정렬 한 다음 O (k * (5+2)의 두 목록을 병합합니다. CASE (k)는 일반적으로 5 : 루프 테스트 (1), 비교 (2), 사본 (3), 입력 목록 증분 (4) 및 출력 목록 증분 (5)입니다. 35 + 2.5입니다. 루프 초기화를 던지면 총 41.5 문장을받습니다.

또한 8 개의 진술이나 실행을 절약 할 수있는 루프를 풀 수 있지만 전체 루틴을 약 4-5 배 더 오래 만들어 명령 캐시 적중률을 엉망으로 만들 수 있습니다.

p (0 ~ 2), c (0 ~ 5)가 주어지고 c ()가 이미 정렬 된 (오름차순)로 h (0 ~ 6)로 복사합니다.

If P(0) > P(1) Then
    // Swap:
    T = P(0)
    P(0) = P(1)
    P(1) = T
    // 1stmt + (3stmt * 50%) = 2.5stmt
End

P(2), C(5) = 53    \\ Note these are end-of-list flags
k = 0     \\ P() index
J = 0     \\ H() index
i = 0     \\ C() index
// 4 stmt

Do While (j) < 7 
    If P(k) < C(I) then
        H(j) = P(k)
        k = k+1
    Else
        H(j) = C(i)
        j = j+1
    End if
    j = j+1
    // 5stmt * 7loops = 35stmt
Loop

그리고 이것은 7 장의 카드를 모두 정렬 해야하는 경우 "가장 빠른"다른 알고리즘보다 빠릅니다. 비트 마스크 (52)를 사용하여 7 장의 카드를 모두 가능한 모든 범위의 52 범위에 비트 세팅하십시오. 카드 (비트 마스크)를 한 다음 비트 마스크를 스캔하여 설정된 7 비트를 찾으십시오. 60-120의 진술을 기껏해야하지만 다른 분류 접근법보다 여전히 빠릅니다).

7 개의 숫자의 경우 비교 횟수와 관련하여 존재하는 가장 효율적인 알고리즘은 Ford-Johnson입니다. 사실로, 위키 백과 Google에서 쉽게 찾을 수있는 논문은 Ford-Johnson이 최대 47 개의 숫자를 위해 최고라고 주장합니다. 불행히도, 포드 존슨에 대한 언급은 찾기가 쉽지 않으며 알고리즘은 일부 복잡한 데이터 구조를 사용합니다.

이 책에 액세스 할 수 있다면 Donald Knuth의 Computer Programming Art, Volume 3에 나타납니다.

FJ와 더 메모리 효율적인 버전을 설명하는 논문이 있습니다. 여기.

어쨌든, 해당 알고리즘의 메모리 오버 헤드로 인해 두 정수를 비교하는 비용은 메모리를 할당하고 포인터를 조작하는 비용에 비해 다소 저렴하기 때문에 정수의 가치가있을 것입니다.

이제 5 장의 카드가 이미 정렬되어 있다고 언급했으며 2 장을 삽입하면됩니다. 다음과 같이 가장 효율적으로 삽입 정렬 로이 작업을 수행 할 수 있습니다.

Order the two cards so that P1 > P2
Insert P1 going from the high end to the low end
(list) Insert P2 going from after P1 to the low end
(array) Insert P2 going from the low end to the high end

그렇게하는 방법은 데이터 구조에 따라 다릅니다. 배열을 사용하면 각 요소를 교체 할 수 있으므로 P1을 1, P2 및 7 일 (높음에서 낮은 순서)에 넣은 다음 P1을 위로 스왑 한 다음 P2 다운하십시오. 목록을 사용하면 포인터를 적절하게 수정하면됩니다.

그러나 다시 한 번, 코드의 특수성 때문에, 당신이 따르는 것이 가장 좋습니다. 니키 P1과 P2가 목록에 나타날 수있는 모든 변형에 대해 제안하고 FE For 루프를 적극적으로 생성하십시오.

예를 들어, p1 <p2를 위해 p1 및 p2를 정렬하십시오. PO1과 PO2를 목록에서 P1 및 P2의 0에서 6로 만들어 봅시다. 그런 다음 이것을하십시오 :

Loop Po1 from 0 to 5
Loop Po2 from Po1 + 1 to 6
If (Po2 == 1) C1start := P2 + 1; C1end := 51 - 4
If (Po1 == 0 && Po2 == 2) C1start := P1+1; C1end := P2 - 1
If (Po1 == 0 && Po2 > 2) C1start := P1+1; C1end := 51 - 5
If (Po1 > 0) C1start := 0; C1end := 51 - 6
for C1 := C1start to C1end
  // Repeat logic to compute C2start and C2end
  // C2 can begin at C1+1, P1+1 or P2+1
  // C2 can finish at P1-1, P2-1, 51 - 3, 51 - 4 or 51 -5
  etc

그런 다음 PO1, PO2, P1, P2, C1, C2, C3, C4, C5를 전달하는 함수를 호출 하고이 기능이 PO1 및 PO2 (36 조합)를 기반으로 가능한 모든 순열을 반환하도록합니다.

개인적으로, 나는 그것이 당신이 얻을 수있는 가장 빠른 것 같아요. 데이터가 사전 주문되기 때문에 아무것도 주문하지 않아도됩니다. 어쨌든 일부 비교에서 시작과 끝을 계산하기 위해 발생하지만 대부분의 비용은 가장 바깥 쪽 루프에 있으므로 비용이 최소화되므로 많이 반복되지 않습니다. 또한 더 많은 코드 복제 비용으로 더 최적화 될 수 있습니다.

7 가지 요소의 경우 옵션이 거의 없습니다. 7 가지 요소의 가능한 모든 조합을 정렬하는 방법을 생성하는 생성기를 쉽게 작성할 수 있습니다. 3 가지 요소에 대한이 방법과 같은 것 :

if a[1] < a[2] {
    if a[2] < a[3] {
        // nothing to do, a[1] < a[2] < a[3]
    } else {
         if a[1] < a[3] {
             // correct order should be a[1], a[3], a[2]
             swap a[2], a[3]
         } else {
             // correct order should be a[3], a[1], a[2]
             swap a[2], a[3]
             swap a[1], a[3]
         }
    }
} else {
    // here we know that a[1] >= a[2]
    ...
}

물론 7 가지 요소에 대한 방법은 더 커지지 만 생성하기가 어렵지는 않습니다.

아래 코드는 최적에 가깝습니다. 나무를 만드는 동안 횡단 할 목록을 작성하여 더 잘 만들 수는 있지만 지금은 시간이 없습니다. 건배!

object Sort7 {
  def left(i: Int) = i * 4
  def right(i: Int) = i * 4 + 1
  def up(i: Int) = i * 4 + 2
  def value(i: Int) = i * 4 + 3

  val a = new Array[Int](7 * 4)
  def reset = {
    0 until 7 foreach { 
      i => {
        a(left(i)) = -1
        a(right(i)) = -1
        a(up(i)) = -1
        a(value(i)) = scala.util.Random.nextInt(52)
      }
    }
  }

  def sortN(i : Int) {
    var index = 0
    def getNext = if (a(value(i)) < a(value(index))) left(index) else right(index)
    var next = getNext
    while(a(next) != -1) {
      index = a(next)
      next = getNext
    }
    a(next) = i
    a(up(i)) = index
  }

  def sort = 1 until 7 foreach (sortN(_))

  def print {
    traverse(0)
    def traverse(i: Int): Unit = {
      if (i != -1) {
        traverse(a(left(i)))
        println(a(value(i)))
        traverse(a(right(i)))
      }
    }
  }
}

의사 코드 :

int64 temp = 0;
int index, bit_position;

for index := 0 to 6 do
   temp |= 1 << cards[index];

for index := 0 to 6 do
begin
   bit_position = find_first_set(temp);
   temp &= ~(1 << bit_position);
   cards[index] = bit_position;
end;

응용 프로그램입니다 버킷 정렬, 이는 일반적으로 제안 된 비교 종류보다 빠르야합니다.

메모: 두 번째 부분은 선형 시간에 비트를 반복하여 구현할 수도 있지만 실제로는 더 빠르지 않을 수 있습니다.

index = 0;
for bit_position := 0 to 51 do
begin
   if (temp & (1 << bit_position)) > 0 then
   begin
      cards[index] = bit_position;
      index++;
   end;
end;

끝에 카드 배열이 필요하다고 가정합니다.

원래 카드를 64 비트 정수 (또는> = 52 비트의 정수)로 비트로 매핑하십시오.

초기 매핑 중에 배열이 정렬되면 변경하지 마십시오.

정수를 니블에 분할 - 각각은 0x0에서 0xf 값에 해당합니다.

니블을 해당 정렬 된 하위 배열에 지수로 사용하십시오. 16 세트의 16 세트 세트 (또는 16 개의 서브 사업과 두 번째 간접)가 필요하거나 답을 찾는 대신 비트 OPS를 수행해야합니다. 더 빠른 것은 플랫폼마다 다릅니다).

비어 있지 않은 하위 배열을 최종 배열로 연결하십시오.

원하는 경우 니블보다 크게 사용할 수 있습니다. 바이트는 7 세트의 256 배열을 제공하고 비어 있지 않은 배열에 연결이 필요할 가능성이 높아집니다.

이것은 가지가 비싸고 캐시 된 배열이 저렴하다고 가정합니다.

#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>

// for general case of 7 from 52, rather than assuming last 5 sorted
uint32_t card_masks[16][5] = {
    { 0, 0, 0, 0, 0 },
    { 1, 0, 0, 0, 0 },
    { 2, 0, 0, 0, 0 },
    { 1, 2, 0, 0, 0 },
    { 3, 0, 0, 0, 0 },
    { 1, 3, 0, 0, 0 },
    { 2, 3, 0, 0, 0 },
    { 1, 2, 3, 0, 0 },
    { 4, 0, 0, 0, 0 },
    { 1, 4, 0, 0, 0 },
    { 2, 4, 0, 0, 0 },
    { 1, 2, 4, 0, 0 },
    { 3, 4, 0, 0, 0 },
    { 1, 3, 4, 0, 0 },
    { 2, 3, 4, 0, 0 },
    { 1, 2, 3, 4, 0 },
};

void sort7 ( uint32_t* cards) {
    uint64_t bitset = ( ( 1LL << cards[ 0 ] ) | ( 1LL << cards[ 1LL ] ) | ( 1LL << cards[ 2 ] ) | ( 1LL << cards[ 3 ] ) | ( 1LL << cards[ 4 ] ) | ( 1LL << cards[ 5 ] ) | ( 1LL << cards[ 6 ] ) ) >> 1;

    uint32_t*   p    = cards;
    uint32_t    base = 0;

    do {
        uint32_t* card_mask = card_masks[ bitset & 0xf ];

        // you might remove this test somehow, as well as unrolling the outer loop
        // having separate arrays for each nibble would save 7 additions and the increment of base
        while ( *card_mask )
            *(p++) = base + *(card_mask++);

        bitset >>= 4;
        base += 4;
    } while ( bitset );
}

void print_cards ( uint32_t* cards ) {
    printf ( "[ %d %d %d %d %d %d %d ]\n", cards[0], cards[1], cards[2], cards[3], cards[4], cards[5], cards[6] );
}

int main ( void ) {
    uint32_t cards[7] = { 3, 9, 23, 17, 2, 42, 52 };

    print_cards ( cards );
    sort7 ( cards );
    print_cards ( cards );

    return 0;
}

이것을 살펴보십시오 :

http://en.wikipedia.org/wiki/sorting_algorithm

당신은 최악의 비용이 안정된 것을 선택해야 할 것입니다 ...

또 다른 옵션은 배열을 전체 시간에 정렬하게 유지하는 것이므로 카드를 추가하면 배열을 자동으로 정렬하여 정렬로 건너 뛸 수 있습니다 ...

JRL이 언급하는 것은 버킷 종류입니다. 유한 한 개별 값 세트가 있으므로 52 개의 버킷을 선언하고 각 요소를 O (1) 시간에 버킷에 삭제할 수 있습니다. 따라서 버킷 정렬은 O (n)입니다. 유한 한 수의 다른 요소를 보장하지 않으면 가장 빠른 이론적 정렬은 O (n log n)입니다. 그것은 최고의 시나리오와 최악의 시나리오의 균형 일뿐입니다.

그러나 긴 대답 짧은 대답은 버킷 정렬을 사용하십시오.

위에서 언급 한 제안이 마음에 들면 항상 배열을 정렬하게 유지하는 52 요소 배열을 유지하는 경우 52 요소 배열에서 7 개의 유효한 요소를 참조 할 7 가지 요소 목록을 유지할 수 있습니다. 이런 식으로 우리는 52 요소 배열을 구문 분석하는 것을 피할 수 있습니다.

이것이 정말로 효율적이 되려면 insertatposition () 및 deleteatPosition ()을 지원하는 링크 된 목록 유형의 구조가 필요합니다.

답에 많은 루프가 있습니다. 그의 속도 요구 사항과 데이터 세트의 작은 크기를 감안할 때 어느 루프.

나는 그것을 시도하지 않았지만 가장 좋은 대답은 완전히 풀리지 않은 거품 종류라고 생각합니다. 또한 어셈블리에서 이루어지면 상당한 양의 이점을 얻을 것입니다.

그래도 이것이 올바른 접근법인지 궁금합니다. 7 카드 핸드를 어떻게 분석 할 건가요 ?? 어쨌든 분석을 위해 다른 표현으로 변환 할 것이라고 생각합니다. 4x13 배열이 더 유용한 표현이되지 않습니까? (그리고 어쨌든 분류 문제를 겪게 될 것입니다.)

마지막 5 가지 요소가 항상 정렬된다는 점을 고려하십시오.


for i := 0 to 1 do begin
  j := i;
  x := array[j];
  while (j+1 <= 6) and (array[j+1] < x) do begin
    array[j] := array[j+1];
    inc(j);
  end;
  array[j] := X;
end;

버블 정렬은 당신의 친구입니다. 다른 종류에는 오버 헤드 코드가 너무 많고 소수의 요소에 적합하지 않습니다.

건배

다음은 기본 O (N) 정렬입니다. 나는 그것이 다른 사람들과 어떻게 비교되는지 잘 모르겠습니다. Unrolled Loops를 사용합니다.

char card[7]; // the original table of 7 numbers in range 0..51
char table[52]; // workspace

// clear the workspace
memset(table, 0, sizeof(table));

// set the 7 bits corresponding to the 7 cards
table[card[0]] = 1;
table[card[1]] = 1;
...
table[card[6]] = 1;

// read the cards back out
int j = 0;
if (table[0]) card[j++] = 0;
if (table[1]) card[j++] = 1;
...
if (table[51]) card[j++] = 51;

매우 낮은 오버 헤드, 최적 종류를 찾고 있다면 정렬 네트워크를 만들어야합니다. Bose-Nelson 알고리즘을 사용하여 7 정수 네트워크의 코드를 생성 할 수 있습니다.

이것은 최악의 경우 고정 된 수의 비교와 같은 수의 스왑을 보장 할 것입니다.

생성 된 코드는 추악하지만 최적입니다.

귀하의 데이터는 정렬 된 배열에 있으며 필요한 경우 새 두 가지를 교체한다고 가정하므로 a. 제자리에 유지하려면 삽입 정렬 형태를 사용하십시오. 비. 당신이 그것을 원한다면, 다른 배열에서 결과는 복사하여 병합을 수행합니다.

적은 숫자를 사용하면 바이너리 홉이 과도하고 3 배의 chop은 적절합니다. 하나의 새 카드는 대부분 2와 3으로 나뉘어집니다. 즉. 2+3 또는 3+2, 싱글과 쌍으로의 2 장, 예를 들어 2+1+2.

따라서 작은 새 카드를 배치하기위한 가장 시간 공간 효율적인 접근 방식은 [1] (즉, [0]을 건너 뛰는 다음 왼쪽 또는 오른쪽을 검색하여 대체 해야하는 카드를 찾은 다음 오른쪽을 바꾸고 이동하는 것입니다. (버블 링보다는 변화), 어디로 가는지 찾을 때까지 더 큰 새 카드와 비교하십시오. 이 후에는 TWOS (두 장의 카드가 삽입 됨)로 전진 할 것입니다. 새 카드 (및 스왑)를 보유한 변수는 레지스터 여야합니다.

조회 접근 방식은 더 빠르지 만 더 많은 메모리를 사용합니다.

이 C ++ 코드와 같이 정렬 네트워크를 사용하십시오.

template<class T> 
inline void sort7(T data) {
#define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);}
//DD = Define Data, create a local copy of the data to aid the optimizer.
#define DD1(a)   register auto data##a=*(data+a);
#define DD2(a,b) register auto data##a=*(data+a);register auto data##b=*(data+b);
//CB = Copy Back
#define CB1(a)   *(data+a)=data##a;
#define CB2(a,b) *(data+a)=data##a;*(data+b)=data##b;
  DD2(1,2) SORT2(1,2)
  DD2(3,4) SORT2(3,4)
  DD2(5,6) SORT2(5,6)
  DD1(0) SORT2(0,2)
  SORT2(3,5) 
  SORT2(4,6) 
  SORT2(0,1)
  SORT2(4,5) 
  SORT2(2,6) CB1(6)
  SORT2(0,4) 
  SORT2(1,5)
  SORT2(0,3) CB1(0) 
  SORT2(2,5) CB1(5)
  SORT2(1,3) CB1(1) 
  SORT2(2,4) CB1(4)
  SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}

반복자 또는 포인터를 전달하려면 위의 기능을 사용하고 7 개의 인수를 하나씩 전달하려면 아래 기능을 사용하십시오. BTW, 템플릿을 사용하여 컴파일러는 실제로 최적화 된 코드를 생성 할 수 있으므로 template<> C 코드 (또는 다른 언어 코드)를 원하지 않는 한.

template<class T>
inline void sort7(T& e0, T& e1, T& e2, T& e3, T& e4, T& e5, T& e6) {
#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(3,4) SORT2(3,4)
  DD2(5,6) SORT2(5,6)
  DD1(0) SORT2(0,2)
  SORT2(3,5)
  SORT2(4,6)
  SORT2(0,1)
  SORT2(4,5)
  SORT2(2,6) CB1(6)
  SORT2(0,4)
  SORT2(1,5)
  SORT2(0,3) CB1(0)
  SORT2(2,5) CB1(5)
  SORT2(1,3) CB1(1)
  SORT2(2,4) CB1(4)
  SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow