Was ist die schnellste Art und Weise eine Anordnung von 7 ganzen Zahlen zu sortieren?

https://stackoverflow.com/questions/1415173

06-07-2019
|

Frage

Dies ist ein Teil eines Programms, das die Vorteile des Poker-Analysen, speziell Texas Hold'em. Ich habe ein Programm, das ich mit glücklich bin, aber es braucht ein paar kleine Optimierungen, perfekt zu sein.

Ich benutze diese Art (unter anderem natürlich):

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

Es gibt zwei Dinge über dieses Array, das wichtig sein kann, wenn die Entscheidung, wie es zu sortieren:

Jeder Artikel ist ein Wert von 0 bis 51. Andere Werte sind möglich.
Es sind keine Duplikate. Nie.

Mit diesen Informationen, was der absolut schnellste Weg, um dieses Array zu sortieren? Ich benutze Delphi, so pascal Code wäre die beste, aber ich kann C und pseudo lesen, wenn auch etwas langsamer: -)

Im Moment habe ich quicksort verwenden, aber das Komische ist, dass dies so gut wie keine schneller als Bubblesort! Mögliche wegen der geringen Anzahl der Elemente. Die Sortier zählt für fast 50% der Gesamtlaufzeit des Verfahrens.

EDIT:

Mason Wheeler gefragt, warum es notwendig ist zu optimieren. Ein Grund dafür ist, dass die Methode 2118760 mal aufgerufen werden.

Grund Poker Informationen: Alle Spieler werden zwei Karten (die Tasche) behandelt und dann fünf Karten auf den Tisch gelegt werden (die drei ersten der Flop genannt werden, ist der nächste an der Reihe und der letzte ist der Fluss Jeder Spieler wählt aus. die fünf besten Karten ihre Hand)

bilden

Wenn ich zwei Karten in der Tasche haben, P1 und P2, werde ich die folgenden Schleifen verwenden, um alle möglichen Kombinationen zu erzeugen:

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;

Während ich dies schreibe ich bemerke noch eines: Die letzten fünf Elemente des Arrays wird immer sortiert werden, so ist es nur eine Frage der die ersten beiden Elemente in der richtigen Position im Array setzen. Das sollte zählt ein wenig vereinfachen.

So ist die neue Frage ist: Was ist die schnellste Art und Weise ist eine Anordnung von 7 Zahlen zu sortieren, wenn die letzten 5 Elemente bereits sortiert sind. Ich glaube, könnte dies mit ein paar gelöst von Wenn und Swaps (?): -)

Lösung

Ich weiß nicht, dass viel über Texas Hold'em: Spielt es eine Rolle, welche Klage P1 und P2 ist, oder tut es nur ganz gleich, ob sie von der gleichen Farbe sind oder nicht? Wenn nur Anzug (P1) == Anzug (P2) die Angelegenheiten, dann könnte man die beiden Fälle trennen, müssen Sie nur 13x12 / 2 verschiedene Möglichkeiten für P1 / P2, und man kann leicht einen Tisch für die beiden Fälle vorauszuberechnen.

Ansonsten würde ich so etwas wie dies vorschlägt:

(* 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 *)

(dies ist nur eine Demonstration für eine Karte P1, würden Sie, dass für P2 erweitern müssen, aber ich denke, das ist einfach. Obwohl es eine Menge Tipparbeit sein wird ...) Auf diese Weise nimmt die Sortierung jederzeit gar nicht. Die generierten Permutationen sind bereits bestellt.

Andere Tipps

Für eine sehr kleine Gruppe, Insertionsort kann in der Regel quicksort schlagen, weil es sehr geringer Overhead.

WRT Ihre bearbeiten, wenn Sie bereits meist in Sortierreihenfolge sind (die letzten 5 Elemente sind bereits sortiert), ist Insertionsort definitiv der Weg zu gehen. In einem fast sortierten Satz von Daten, wird es schlagen quicksort jedes Mal, auch bei großen Mengen. (Vor allem für große Mengen! Dies ist Best-Case-Szenario Insertionsort und quicksort schlimmster Fall).

Sie wissen nicht, wie Sie dies umsetzen, aber was Sie tun können, ist eine Reihe von 52 statt 7 haben, und einfach die Karte in den Steckplatz einsetzen direkt, wenn Sie es bekommen, da es nie Duplikate sein können, auf diese Weise Sie müssen nie das Array sortieren. Dies könnte schneller sein, je nachdem wie sein verwendet.

Es gibt nur 5040 Permutationen von 7 Elementen. Sie können programmaticaly ein Programm generieren, das eine durch die Eingabe in einer minimalen Anzahl von Vergleichen dargestellt findet. Es wird ein großer Baum von if-then-else Anweisungen, die jeweils den Vergleich ein festes Paar von Knoten, zum Beispiel if (a[3]<=a[6]).

Der schwierige Teil ist, zu entscheiden, welche Elemente 2 in einem bestimmten internen Knoten zu vergleichen. Dazu müssen Sie die Ergebnisse der Vergleiche in den Vorfahren Knoten von der Wurzel zu dem bestimmten Knoten berücksichtigen (zB a[0]<=a[1], not a[2]<=a[7], a[2]<=a[5]) und die Menge der möglichen Permutationen, die die Vergleiche befriedigen. Vergleichen des Paars von Elementen, die den Satz in die als gleiche Teile wie möglich spaltet (Minimierung der Größe des größeren Teils).

Wenn Sie die Permutation haben, ist es trivial es in einem minimalen Satz von Swaps zu sortieren.

Da die letzten 5 Artikel bereits sortiert sind, kann der Code geschrieben werden nur die ersten 2 Artikel neu zu positionieren. Da Sie mit Pascal, habe ich geschrieben und getestet, um einen Sortieralgorithmus, der in 2.118.760 mal etwa 62 Millisekunden ausführen kann.

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;

Verwenden min-sort. Suchen nach Minimal- und Maximalelement auf einmal und legt sie in die sich ergebende Array. Wiederholen Sie dreimal. (EDIT: Nein, ich werde nicht versuchen, die Geschwindigkeit theoretisch zu messen: _))

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

Dies ist die schnellste Methode: Da die 5-Karten-Liste bereits sortiert ist, sortieren Sie die Zwei-Karten-Liste (eine Vergleichs- und swap), und dann verschmelzen die beiden Listen, die O (k * (5 + 2) . In diesem Fall (k) wird in der Regel 5 sein. der Schleifentest (1), das vergleichen (2), die Kopie (3), die Eingangsliste increment (4) und die Ausgabeliste Schritt (5) ist, dass 35 + 2.5. Einwurf Schleife Initialisierung und Sie erhalten 41,5 Aussagen, total.

Sie können auch die Schlaufen abrollen, die Ihnen vielleicht 8 Aussagen oder Ausführung speichern würden, aber die ganze Routine etwa 4-5 mal länger das möglicherweise Chaos mit Ihrer Trefferquote Befehls-Cache.

Da P (0 bis 2), C (0 bis 5) und der Kopiervorgang zu H (0 bis 6) mit C () bereits sortiert (aufsteigend):

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

Und beachten Sie, dass dies schneller als die anderen Algorithmus, der „schnellste“, wenn Sie musste wirklich sortieren alle 7 Karten wäre: Verwenden Sie ein Bit-Maske (52) auf map & Bit-Set alle 7 Karten in diesem Bereich von alle möglichen 52 Karten (die Bit-Maske), und scannen Sie dann die Bit-Maske, um für die 7 Bits suchen, eingestellt sind. Das dauert 60-120 Aussagen besten (ist aber immer noch schneller als jeder anderer Sortier Ansatz).

Für sieben Zahlen, den effizientesten Algorithmus, der in Bezug auf die Anzahl von Vergleichen vorhanden ist Ford-Johnson. In der Tat, wikipedia verweist auf ein Papier, leicht auf Google gefunden, dass Ford-Johnson behauptet, die besten für bis zu 47 Nummern. Leider sind Verweise auf Ford-Johnson nicht so leicht zu finden, und der Algorithmus verwendet einige komplexe Datenstrukturen.

Es erscheint auf dem Gebiet der Computerprogrammierung, Band 3, von Donald Knuth, wenn Sie Zugang zu diesem Buch.

Es ist ein Papier, das FJ und eine speichereffiziente Version beschreibt hier .

Auf jeden Fall, weil der Speicher-Overhead dieses Algorithmus, bezweifle ich, wäre es die Mühe wert sein ganzer Zahlen für, wie die Kosten für zwei ganze Zahlen von Vergleich eher günstig ist im Vergleich zu den Kosten der Zuweisung von Speicher und Manipulation von Zeigern.

Nun, Sie erwähnten, dass 5-Karten sind bereits sortiert, und Sie müssen nur zwei einzufügen. Sie können mit Einsetzen dies tun Art am effizientesten wie folgt aus:

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

Wie Sie das tun, hängt von der Datenstruktur abhängen. Mit einer Reihe werden Sie jedes Element tauschen, so Platz P1 am 1., P2 und 7. (geordnete absteigend), und dann P1 bis tauschen, und dann nach unten P2. Mit einer Liste, müssen Sie nur die Zeiger entsprechend zu beheben.

Doch noch einmal, wegen der Besonderheit des Codes, ist es wirklich am besten, wenn Sie nikie Vorschlag folgen und einfach erzeugt die für Schleifen apropriately für jede Variante, bei der P1 und P2 in der Liste angezeigt werden können.

Zum Beispiel, sortieren P1 und P2, so dass P1

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

Sie rufen dann eine Funktion übergeben Po1, Po2, P1, P2, C1, C2, C3, C4, C5, und haben diese Funktion, um alle möglichen Permutationen Rückkehr basierend auf PO1 und PO2 (das sind 36 Kombinationen).

Ich persönlich denke, das ist die schnellst Sie bekommen können. Sie vermeiden völlig etwas bestellen zu müssen, weil die Daten vorbestellt werden. Sie entstehen ohnehin in einigen Vergleichen Sie die beginnt und endet zu berechnen, aber ihre Kosten minimiert, da die meisten von ihnen auf den äußersten Schleifen sein, so dass sie nicht viel wiederholt werden. Und sie können sogar auf Kosten von mehr Code-Duplizierung mehr optimiert werden.

Für 7 Elemente gibt es nur wenige Optionen. Sie können ganz einfach einen Generator schreiben, das Verfahren alle möglichen Kombinationen von 7 Elementen sortieren erzeugt. So etwas wie diese Methode für 3 Elemente:

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]
    ...
}

Natürlich Methode für 7 Elemente wird größer sein, aber es ist nicht so schwer zu erzeugen.

Der folgende Code ist in der Nähe optimal. Es könnte durch Komponieren eine Liste besser gemacht wird durchlaufen werden, während der Baum zu machen, aber ich bin gerade aus der Zeit. Cheers!

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)))
      }
    }
  }
}

In Pseudo-Code:

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;

Es ist eine Anwendung von Bucketsort , die in der Regel schneller sein sollte als alle Vergleichs Sorten, die vorgeschlagen wurden.

Hinweis: Der zweite Teil auch durch Iteration über Bits in linearer Zeit umgesetzt werden kann, aber in der Praxis kann es nicht schneller sein:

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;

Unter der Annahme, dass Sie eine Reihe von Karten am Ende brauchen.

Karte die Originalkarten Bits in einer 64-Bit-Ganzzahl (oder eine beliebige ganze Zahl mit> = 52 Bits).

Wenn während der Zuordnung der Array sortiert ist, kann es nicht ändern.

Partition die Ganzzahl in Nibbles -. Jeweils auf Werte entsprechen 0x0 wird 0xF

Mit den Nibbles als Indizes zu sortier Subarrays entspricht. Sie werden 13 Sätze von 16 Unteranordnungen müssen (oder auch nur 16 Unteranordnungen und eine zweite Indirektion verwenden oder die Bit-ops tun, anstatt die Antwort der Suche, was schneller nach Plattform variiert ist).

Verketten der nicht-leeren Teilanordnungen in die endgültige Anordnung.

Sie könnten größer als Knabbereien verwenden, wenn Sie wollen; Bytes würde 7 Sätze von 256 Arrays geben und macht es wahrscheinlicher, dass der nicht-leere Arrays Verkettungs erfordern.

Dies setzt voraus, dass Zweige sind teuer und im Cache-Array-Zugriffe billig.

#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;
}

Werfen Sie einen Blick auf diese:

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

Sie müssten eine auswählen, die eine stabile schlimmsten Fall Kosten haben wird ...

Eine andere Möglichkeit könnte sein, das Feld zu halten die ganze Zeit sortiert, so dass eine Zugabe einer Karte das Array automatisch sortiert halten würde, dass die Art und Weise Sie das Sortieren überspringen könnte ...

Was JRL bezieht sich auf eine Bucketsort. Da Sie eine endliche diskrete Menge der möglichen Werte haben, können Sie 52 Eimer erklären und nur in O in einem Eimer jedes Element fallen (1) Zeit. Daher Bucketsort ist O (n). Ohne die Garantie einer endlichen Anzahl verschiedenen Elemente, die schnellste theoretische Art ist O (n log n), die Dinge wie Mergesort eine schnelle Art sind. Es ist nur ein Gleichgewicht des besten und die schlimmsten Falles dann.

Aber lange Antwort kurz, Verwendung Bucketsort.

Wenn Sie die oben genannten Vorschlag wie ein 52-Element-Array zu halten, die immer Ihre Array sortiert hält, dann können Sie eine weitere Liste von 7 Elemente halten könnte, die die 7 gültige Elemente in dem 52-Element-Array verweisen würde. So können wir auch vermeiden, können die 52-Element-Array-Parsing.

Ich denke, für diese wirklich effizient sein, müssten wir eine verkettete Liste Art von Struktur haben, die Operationen werden unterstützt:. InsertAtPosition () und DeleteAtPosition () und effizient an, dass

Es gibt eine Menge von Schleifen in den Antworten. Aufgrund seiner Geschwindigkeit Bedarf und die geringe Größe des Datensatzes würde ich nicht tun ANY Schleifen.

Ich habe es nicht versucht, aber ich vermute, dass die beste Antwort eine vollständig abgerollt Blase Art ist. Es wäre wahrscheinlich auch eine angemessene Menge von Vorteile gewinnt aus in der Montage getan.

Ich frage mich, ob dies der richtige Ansatz ist, though. Wie wollen Sie eine 7 Karten in der Hand analysieren ?? Ich denke, du wirst es auf eine andere Darstellung zur Analyse ohnehin am Ende umzuwandeln. Wäre das nicht ein 4x13 Array eine nützlichere Darstellung sein? (Und es würde die Sortier Frage strittig machen, sowieso.)

In Anbetracht, dass die letzten 5 Elemente sind immer sortiert:


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;

Blase Art ist dein Freund. Andere Arten haben zu viele Köpfe Codes und nicht geeignet für kleine Anzahl von Elementen

Prost

Hier ist Ihr grundlegender O (n) sortieren. Ich bin mir nicht sicher, wie es zu den anderen vergleicht. Es verwendet abgerollt Schleifen.

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;

Wenn Sie für einen sehr geringen Overhead, optimale Art suchen, sollten Sie ein Sortiernetzwerk erstellen. Sie können den Code für ein 7-Integer-Netzwerk erzeugen, um den Bose-Nelson-Algorithmus.

Dies würde guarentee eine feste Anzahl von vergleicht und eine gleiche Anzahl von Swaps im schlimmsten Fall.

Der generierte Code ist hässlich, aber es ist optimal.

Ihre Daten werden in einer sortierten Array und ich nehme an, Sie die neue zwei tauschen, wenn so auch sortiert erforderlich, so ein. wenn Sie es an Ort und Stelle halten wollen, dann eine Form von Insertionsort verwenden; b. wenn Sie es das Ergebnis in einem anderen Array haben wollen tun, um eine Verschmelzung durch Kopieren.

Mit den kleinen Zahlen, binary chop ist übertrieben, und ternärer chop ist ohnehin angebracht: Eine neue Karte wird meist wie in zwei und drei, nämlich. 2 + 3 oder 3 + 2, zwei Karten in Einzel- und Paare, z.B. 2 + 1 + 2.

So der Raum-Zeit-effiziente Ansatz die kleinere neue Karte zu platzieren ist mit einem [1] vergleichen (viz. Überspringt a [0]) und dann nach links oder rechts suchen, die Karte zu finden verdrängen soll, dann tauschen und nach rechts bewegen (Verschiebung statt sprudelnden), mit der größeren neuen Karte zu vergleichen, bis Sie finden, wo es geht. Danach werden Sie vorwärts durch Zweien verlagern (zwei Karten eingeführt wurden). Die Variablen, die neuen Karten (und Swaps) halten sollten Register sein.

Der nachschlagen Ansatz wäre schneller, aber mehr Speicherplatz.

Verwenden Sie ein Sortiernetzwerk, wie in diesem C ++ Code:

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
}

Mit der Funktion oben, wenn Sie wollen, dass es einen Iterator übergeben oder einen Zeiger und verwenden Sie die Funktion unten, wenn Sie es die sieben Argumente eins nach dem anderen übergeben werden soll. BTW, können Vorlagen Compiler wirklich optimierten Code zu erzeugen, um nicht Fahrt des template<> bekommen, wenn Sie C-Code (oder eine andere Sprache des Code) werden sollen.

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
}

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow