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

Question

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

私はこのタイプを使用します（もちろん、とりわけ）：

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

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

1. すべての項目は 0 から 51 までの値です。他の値は使用できません。
2. 重複はありません。一度もない。

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

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

編集：

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

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

ポケットに P1 と P2 の 2 枚のカードがある場合、次のループを使用して、考えられるすべての組み合わせを生成します。

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;

これを書いているとき、もう 1 つのことに気付きました。配列の最後の 5 つの要素は常にソートされるため、最初の 2 つの要素を配列の正しい位置に配置するだけの問題です。それは問題を少し単純化するはずです。

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

Answer 1

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

編集を WRT します。すでにほとんどが並べ替え順になっている場合 (最後の 5 つの要素が既に並べ替えられている場合)、挿入並べ替えが確実に適しています。ほぼソートされたデータセットでは、大規模なセットであっても、毎回クイックソートを打ち負かします. (特に大きなセットの場合! これは挿入ソートの最良のシナリオであり、クイックソートの最悪のシナリオです。)

Answer 2

これをどのように実装しているかはわかりませんが、7 ではなく 52 の配列を使用して、重複することは決してないため、カードを取得したときにそのスロットにカードを直接挿入することができます。配列をソートします。使い方によってはこちらの方が早いかもしれません。

Answer 3

私はテキサス ホールデムについてあまり知りません。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 用に展開する必要がありますが、それは簡単だと思います。多くのタイピングが必要になりますが...) そうすれば、並べ替えに時間がかかりません。まったく。生成された順列は既に順序付けられています。

Answer 4

最後の 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;

Answer 5

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

注意が必要なのは、特定の内部ノードでどの 2 つの要素を比較するかを決定することです。a[0]<=a[1], not a[2]<=a[7], a[2]<=a[5]このためには、ルートから特定のノード (たとえば) までの祖先ノードでの比較の結果と、比較を満たす可能な順列のセットを考慮する必要があります。セットをできるだけ均等な部分に分割する要素のペアを比較します (大きい部分のサイズを最小化します)。

順列を取得したら、それを最小限のスワップ セットに並べ替えるのは簡単です。

Answer 6

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

その本にアクセスできる場合は、DonaldKnuthによるTheArt Of Computer Programming、Volume3に掲載されています。

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を下に交換します。リストを使用すると、必要に応じてポインタを修正する必要があります。

ただし、もう一度言いますが、コードの特殊性のため、nikieの提案に従い、P1とP2がリストに表示される可能性のあるすべてのバリエーションに対して適切に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の組み合わせ）に基づいて可能なすべての順列を返すようにします。

個人的には、それが最速だと思います。データは事前​​注文されるため、何も注文する必要はありません。とにかく開始と終了を計算するためにいくつかの比較が発生しますが、それらのほとんどは最も外側のループにあるため、コストは最小限に抑えられ、あまり繰り返されません。また、コードの重複を増やすことで、さらに最適化することもできます。

Answer 7

最小ソートを使用します。最小要素と最大要素を一度に検索し、それらを結果の配列に配置します。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

Answer 8

これが最速の方法です: 5 枚のカードのリストは既に並べ替えられているため、2 枚のカードのリストを並べ替え (比較と入れ替え)、次に 2 つのリストをマージします。これは O(k * (5+2) です。通常、ケース (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 枚すべてのカードを真にソートする必要がある場合に「最速」となる他のアルゴリズムよりも高速であることに注意してください。bit-mask(52) を使用して、7 枚すべてのカードを可能なすべての 52 の範囲にマップおよびビットセットします。カード (ビットマスク) をスキャンし、ビットマスクを順番にスキャンして、設定されている 7 ビットを探します。これには、せいぜい 60 ～ 120 個のステートメントが必要です (ただし、他のどのソート方法よりも高速です)。

Answer 9

擬似コード:

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;

Answer 10

最後にカードの配列が必要だと仮定します。

元のカードを 64 ビット整数 (または 52 ビット以上の任意の整数) のビットにマップします。

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

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

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

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

必要に応じて、ニブルより大きいものを使用できます。bytes は、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;
}

Answer 11

以下のコードは最適に近いものです。ツリーの作成中にトラバースするリストを作成することで改善できますが、今は時間がありません。乾杯！

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

Answer 12

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要素のメソッドは大きくなりますが、生成するのはそれほど難しくありません。

Answer 13

最後の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;

Answer 14

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

試したことはありませんが、最良の答えは完全に展開されたバブルソートだと思います。また、アセンブリで行われることで、かなりの利点が得られるでしょう。

しかし、これが正しいアプローチであるかどうかは疑問です。7 カード ハンドをどのように分析しますか?? とにかく、分析のためにそれを他の表現に変換することになると思います。4x13 配列の方がより便利な表現ではないでしょうか? （そして、とにかく、ソートの問題を無意味にします。）

Answer 15

オーバーヘッドが非常に低く、最適な並べ替えを探している場合は、並べ替えネットワークを作成する必要があります。Bose-Nelson アルゴリズムを使用して、7 つの整数ネットワークのコードを生成できます。

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

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

Answer 16

これを見てください：

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

安定した最悪の場合のコストを持つものを選択する必要があります...

もう1つのオプションは、配列を常にソートしたままにすることです。そのため、カードを追加すると配列が自動的にソートされたままになり、ソートにスキップできます...

Answer 17

JRLが言及しているのはバケットソートです。可能な値の有限の離散セットがあるため、52 個のバケットを宣言し、バケット内の各要素を O(1) 時間でドロップできます。したがって、バケットの並べ替えは O(n) です。有限数の異なる要素の保証がなければ、最速の理論的ソートは O(n log n) であり、マージソートやクイックソートのようなものです。それは、最良のシナリオと最悪のシナリオのバランスにすぎません。

しかし、簡単に言えば、バケットソートを使用してください。

Answer 18

バブルソートはあなたの友達です。他のソートにはオーバーヘッド コードが多すぎて、少数の要素には適していません

乾杯

Answer 19

配列を常にソートしたままにする 52 要素の配列を保持するという上記の提案が気に入った場合は、52 要素配列の 7 つの有効な要素を参照する 7 つの要素の別のリストを保持することができます。このようにして、52 要素の配列の解析を回避することさえできます。

これが本当に効率的であるためには、InsertAtPosition() と DeleteAtPosition() という操作をサポートするリンクされたリスト型の構造が必要であり、効率的である必要があると思います。