7 つの整数の配列を最も速くソートする方法は何ですか?

https://stackoverflow.com/questions/1415173

06-07-2019
|

質問

これは、ポーカー、特にテキサスホールデムのオッズを分析するプログラムの一部です。満足のいくプログラムができましたが、完璧にするにはいくつかの小さな最適化が必要です。

私はこのタイプを使用します (もちろん、他のタイプも含めて):

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

この配列については、並べ替え方法を決定する際に重要となる可能性のあることが 2 つあります。

各項目は 0 ～ 51 の値です。他の値は使用できません。
重複はありません。一度もない。

この情報をもとに、 絶対最速 この配列をソートする方法は?私は Delphi を使用しているので、パスカルコードが最適ですが、少し遅いですが、C と擬似コードを読むことができます :-)

現時点ではクイックソートを使用していますが、面白いことに、これはバブルソートよりもほとんど高速ではありません。品数が少ないので可能です。ソートは、メソッドの合計実行時間のほぼ 50% を占めます。

編集：

Mason Wheeler 氏は、最適化がなぜ必要なのかを尋ねました。理由の 1 つは、メソッドが 2118760 回呼び出されることです。

ポーカーの基本情報:すべてのプレイヤーに 2 枚のカード (ポケット) が配られ、その後 5 枚のカードがテーブルに配られます (最初の 3 枚はフロップと呼ばれ、次がターン、最後のカードがリバーと呼ばれます)。各プレイヤーは自分の手札を構成するために最高の 5 枚のカードを選びます)

ポケットに 2 枚のカード (P1 と 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;

これを書いていて、もう一つ気づいたことがあります。配列の最後の 5 つの要素は常に並べ替えられるため、最初の 2 つの要素を配列内の正しい位置に配置するだけで済みます。これで問題が少し簡素化されるはずです。

したがって、新しい質問は次のとおりです。最後の 5 つの要素がすでにソートされている場合に、7 つの整数の配列を最も速くソートする方法は何ですか。これは、いくつかの (?) if と swap で解決できると思います :-)

解決

テキサスホールデムについてはあまり知りません。P1とP2がどのスーツであるかは問題になりますか、それとも同じスーツであるかどうかだけが問題になりますか？ suit（P1）== suit（P2）のみが重要な場合、2つのケースを分離でき、P1 / P2の可能性は13x12 / 2しかなく、2つのケースのテーブルを簡単に事前計算できます。

それ以外の場合、次のようなものを提案します：

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

（これは1枚のカードP1のデモンストレーションにすぎませんが、P2の場合はそれを展開する必要がありますが、それは簡単だと思います。そうすれば、ソートに時間がかかりません。生成された順列はすでに順序付けられています。

他のヒント

非常に小さなセットの場合、挿入ソートは通常、クイックソートよりも優れています。非常に低いオーバーヘッド。

編集をWRTします。すでにほとんどの並べ替え順（最後の5つの要素は既に並べ替えられている）である場合、挿入ソートが間違いなく実行されます。ほぼソートされたデータのセットでは、大規模なセットであっても、毎回クイックソートに勝ります。（特に大規模なセットの場合！これは挿入ソートのベストケースのシナリオであり、クイックソートの最悪のケースです。）

これをどのように実装しているかはわかりませんが、7の代わりに52の配列を使用し、重複することは決してないので、カードを入手したら直接スロットに挿入するだけです配列を並べ替える必要はありません。これは、使用方法によっては高速になる場合があります。

7つの要素の順列は5040のみです。最小限の比較で入力によって表されるものを見つけるプログラムをプログラムで生成できます。 if-then-else命令の大きなツリーになり、それぞれが固定されたノードのペアを比較します。たとえば、if (a[3]<=a[6])です。

難しい部分は、特定の内部ノードで比較する2つの要素を決定することです。このためには、ルートから特定のノード（たとえば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を使用します。最小要素と最大要素を一度に検索し、結果の配列に配置します。 3回繰り返します。（編集：いいえ、理論的に速度を測定しようとはしません：_））

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枚のカードのリストをソートし（<！> amp; swapを比較）、2つのリストをマージします。これはO（k *（ 5 + 2）。この場合、（k）は通常5になります：ループtest（1）、compare（2）、copy（3）、input-list increment（4）およびoutput list increment（5 ）。それは35 + 2.5です。ループ初期化でスローすると、合計41.5ステートメントが得られます。

ループを展開して、8つのステートメントまたは実行を節約することもできますが、ルーチン全体を約4〜5倍長くし、命令キャッシュヒット率を混乱させる可能性があります。

P（0から2）、C（0から5）を指定し、H（0から6）にコピー C（）が既にソートされている（昇順）：

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

そして、これは<！> quot; fastest <！> quot;となる他のアルゴリズムよりも高速であることに注意してください。 7枚すべてのカードを本当にソートする必要がある場合：ビットマスク（52）を使用して<！> ampをマップします。すべての可能な52のカードの範囲に7つのカードすべてをビット設定し（ビットマスク）、ビットマスクをスキャンして、設定されている7ビットを探します。せいぜい60〜120のステートメントが必要です（ただし、他の並べ替え方法よりも高速です）。

7 つの数値の場合、比較の数に関して存在する最も効率的なアルゴリズムはフォードジョンソンのアルゴリズムです。実際には、ウィキペディアこれは、Google で簡単に見つけられる、最大 47 個の番号についてはフォード・ジョンソン法が最適であると主張する論文を参照しています。残念ながら、Ford-Johnson への参照はそれほど簡単に見つかるわけではなく、アルゴリズムではいくつかの複雑なデータ構造が使用されています。

この本を入手できる場合は、Donald Knuth 著の『The Art Of Computer Programming』第 3 巻に掲載されています。

FJ とよりメモリ効率の高いバージョンについて説明した論文がありますここ.

いずれにせよ、そのアルゴリズムのメモリオーバーヘッドのせいで、2 つの整数を比較するコストはメモリの割り当てやポインタの操作に比べてかなり安いため、整数については時間をかける価値があるとは思えません。

さて、すでに 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 がリストに現れる可能性があるすべてのバリエーションに対して適切に for ループを生成するだけです。

たとえば、P1 < P2 になるように P1 と P2 を並べ替えます。リスト上の P1 と P2 の 0 から 6 までの位置を Po1 と Po2 とします。次に、これを実行します。

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;

これは、バケットソートのアプリケーションであり、一般にどの比較よりも高速です提案されたソート。

注： 2番目の部分は、線形時間でビットを反復処理することで実装することもできますが、実際には高速ではない場合があります。

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ビット整数（または<！> gt; = 52ビットの整数）のビットにマッピングします。

初期マッピング中に配列がソートされる場合、変更しないでください。

整数をニブルに分割-それぞれが値0x0〜0xfに対応します。

対応するソートされたサブ配列のインデックスとしてニブルを使用します。 16個のサブアレイの13セットが必要になります（または16個のサブアレイのみで2番目の間接参照を使用するか、回答を調べるのではなくビット操作を実行します。高速化はプラットフォームによって異なります）。

空でないサブ配列を最終的な配列に連結します。

必要に応じて、ニブルより大きいサイズを使用できます。バイトは256セットの7セットを提供し、空でないアレイの連結が必要になる可能性が高くなります。

これは、ブランチが高価であり、キャッシュされた配列アクセスが安価であると想定しています。

#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（）の操作をサポートする構造のリンクリストタイプが必要であり、それで効率的である必要があります。

答えには多くのループがあります。彼の速度要件とデータセットの小さなサイズを考えると、 Any ループは実行しません。

試したことはありませんが、ベストアンサーは完全に展開されたバブルソートだと思います。また、おそらくアセンブリで行われることからかなりの利点が得られます。

これは正しいアプローチなのかしら。 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）ソートです。私はそれが他のものと比較する方法がわかりません。展開されたループを使用します。

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整数ネットワークのコードを生成できます。

これにより、最悪の場合、固定数の比較と同数のスワップが保証されます。

生成されたコードはいですが、最適です。

あなたのデータはソートされた配列にあり、必要に応じて新しい2つをスワップすると仮定します。 a。所定の位置に保持する場合は、挿入ソートの形式を使用します。 b。別の配列で結果を取得するには、コピーしてマージします。

小さな数値では、バイナリチョップは過剰になり、とにかく3進チョップが適切です。 1枚の新しいカードは、2枚と3枚に分割されることがほとんどです。 2 + 3または3 + 2 2枚のカードをシングルとペアに、例えば2 + 1 + 2。

より小さな新しいカードを配置するための最も時間空間効率の良いアプローチは、a [1]（つまりa [0]をスキップ）と比較し、左または右を検索して、置換する必要があるカードを見つけてから、交換することですそして、右に移動し（バブリングではなくシフト）、より大きな新しいカードと比較して、どこに行くかを見つけます。この後、2つ前にシフトします（2枚のカードが挿入されています）。新しいカード（およびスワップ）を保持する変数はレジスタである必要があります。

ルックアップアプローチは高速ですが、より多くのメモリを使用します。

この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つの引数を1つずつ渡す場合は下の関数を使用します。ところで、テンプレートを使用すると、コンパイラは本当に最適化されたコードを生成できるため、Cコード（または他の言語のコード）が必要でない限り、template<>に乗らないでください。

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