Какой самый быстрый способ сортировки массива из 7 целых чисел?

Question

Это часть программы, которая анализирует шансы покера, в частности техасский холдем. У меня есть программа, которой я доволен, но для совершенства нужны небольшие оптимизации.

Я использую этот тип (среди прочего, конечно):

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

Есть две вещи в этом массиве, которые могут быть важны при решении, как его отсортировать:

1. Каждый элемент имеет значение от 0 до 51. Другие значения невозможны.
2. Дубликатов нет. Никогда.

Имея эту информацию, какой самый быстрый способ сортировать этот массив? Я использую Delphi, поэтому код на Паскале будет лучшим, но я могу читать C и псевдо, хотя и немного медленнее: -)

В данный момент я использую быструю сортировку, но забавно то, что это почти не быстрее, чем пузырьковая сортировка! Возможно из-за небольшого количества предметов. Сортировка составляет почти 50% от общего времени выполнения метода.

EDIT:

Мейсон Уилер спросил, почему необходимо оптимизировать. Одна из причин заключается в том, что метод будет вызываться 2118760 раз.

Основная информация о покере: всем игрокам сдаются по две карты (в кармане), а затем на стол сдаются пять карт (первые три называются флопом, следующие - тёрн, а последние - ривер. пять лучших карт, из которых состоят их руки)

Если у меня в кармане две карты, 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;

Когда я пишу это, я замечаю еще одну вещь: последние пять элементов массива всегда будут отсортированы, так что это просто вопрос размещения первых двух элементов в правильном положении в массиве. Это должно немного упростить дело.

Итак, новый вопрос: каков самый быстрый способ сортировки массива из 7 целых чисел, когда последние 5 элементов уже отсортированы. Я полагаю, что это можно решить с помощью пары (?) If и перестановок: -)

Answer 1

Для очень маленького набора сортировка вставки обычно может превзойти быструю сортировку, поскольку она имеет очень низкие накладные расходы.

ЗАПИШИТЕ ваше редактирование, если вы уже в основном в порядке сортировки (последние 5 элементов уже отсортированы), сортировка вставкой - определенно лучший способ. В почти отсортированном наборе данных он будет превосходить быструю сортировку каждый раз, даже для больших наборов. (Особенно для больших наборов! Это лучший вариант сценария вставки и худший случай быстрой сортировки.)

Answer 2

Не знаю, как вы это реализуете, но вы могли бы получить массив из 52 вместо 7, и просто вставить карту в слот напрямую, когда вы ее получите, поскольку в этом случае дубликатов быть не может. вам никогда не придется сортировать массив. Это может быть быстрее в зависимости от того, как его использовать.

Answer 3

Я не так много знаю о техасском холдеме: имеет ли значение, какие масти 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, но я думаю, что это просто. Хотя будет много печатать ...) Таким образом, сортировка не занимает много времени. Сгенерированные перестановки уже упорядочены.

Answer 4

Есть только 5040 перестановок из 7 элементов. Вы можете программно сгенерировать программу, которая найдет ту, которая представлена ​​вашими данными, за минимальное количество сравнений. Это будет большое дерево if-then-else инструкций, каждая из которых сравнивает фиксированную пару узлов, например if (a[3]<=a[6]).

Сложная задача - решить, какие 2 элемента сравнить в конкретном внутреннем узле. Для этого вы должны принять во внимание результаты сравнений в узлах-предках от корня до конкретного узла (например, a[0]<=a[1], not a[2]<=a[7], a[2]<=a[5]) и набор возможных перестановок, которые удовлетворяют сравнениям. Сравните пару элементов, которые разбивают множество на равные части, насколько это возможно (минимизируйте размер большей части).

Если у вас есть перестановка, сортировать ее за минимальный набор перестановок тривиально.

Answer 5

Поскольку последние 5 элементов уже отсортированы, код может быть написан только для изменения положения первых 2 элементов. Поскольку вы используете Pascal, я написал и протестировал алгоритм сортировки, который может выполняться 2118760 раз за 62 миллисекунды.

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 6

Для семи чисел наиболее эффективным алгоритмом, который существует в отношении числа сравнений, является алгоритм Форда-Джонсона. На самом деле, Википедия ссылается на статью, которую легко найти в Google, в которой говорится, что Ford-Johnson - лучший на 47 номеров. К сожалению, ссылки на Форд-Джонсона не так просто найти, и алгоритм использует некоторые сложные структуры данных.

Он появляется в книге «Искусство компьютерного программирования», том 3, Дональда Кнута, если у вас есть доступ к этой книге.

Есть статья, в которой описывается FJ и более эффективная версия памяти здесь .

В любом случае, из-за нехватки памяти в этом алгоритме, я сомневаюсь, что оно будет стоить вашего времени для целых чисел, так как стоимость сравнения двух целых чисел довольно низкая по сравнению со стоимостью выделения памяти и манипулирования указателями.

Теперь вы упомянули, что 5 карт уже отсортированы, и вам просто нужно вставить две. Вы можете сделать это с помощью сортировки вставкой наиболее эффективно, как это:

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 и просто сгенерируете циклы for для каждого варианта, в котором P1 и P2 могут появиться в списке .

Например, отсортировать P1 и P2 так, чтобы 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

Затем вы вызываете функцию, передающую Po1, Po2, P1, P2, C1, C2, C3, C4, C5, и эта функция возвращает все возможные перестановки, основанные на Po1 и Po2 (это 36 комбинаций).

Лично я думаю, что это самое быстрое, что вы можете получить. Вы полностью избегаете необходимости что-либо заказывать, потому что данные будут предварительно заказаны. В любом случае, вы берете на себя некоторые сравнения, чтобы вычислить начало и конец, но их стоимость сведена к минимуму, так как большинство из них будет на самых внешних циклах, поэтому они не будут повторяться много. И они могут быть даже более оптимизированы за счет большего дублирования кода.

Answer 7

Используйте 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

Answer 8

Это самый быстрый метод: поскольку список из 5 карт уже отсортирован, отсортируйте список из двух карт (сравнение и обмен), а затем объедините два списка, что равно 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) и копирование в 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

И обратите внимание, что это быстрее, чем другой алгоритм, который был бы «самым быстрым», если бы вам пришлось действительно отсортировать все 7 карт: используйте битовую маску (52), чтобы отобразить и установить все 7 карт в этом диапазоне все возможные 52 карты (битовая маска), а затем отсканируйте битовую маску в поисках 7 установленных битов. В лучшем случае это занимает 60-120 операторов (но все же быстрее, чем любой другой подход к сортировке).

Answer 9

Код ниже близок к оптимальному. Это можно было бы сделать лучше, составив список, который нужно просмотреть при создании дерева, но сейчас у меня нет времени. Ура!

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 10

Для 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 элементов будет больше, но его не так сложно сгенерировать.