Какой самый быстрый способ сортировки массива из 7 целых чисел?
Это часть программы, которая анализирует шансы покера, в частности техасский холдем. У меня есть программа, которой я доволен, но она требует небольшой оптимизации, чтобы быть идеальной.
Я использую этот тип (среди прочего, конечно):
type
T7Cards = array[0..6] of integer;
В этом массиве есть две вещи, которые могут быть важны при выборе способа его сортировки:
- Каждый элемент имеет значение от 0 до 51. Другие значения невозможны.
- Там нет дубликатов. Никогда.
С этой информацией, какой самый быстрый способ сортировки этого массива? Я использую Delphi, так что код на Паскале был бы лучшим, но я могу читать C и псевдо, хотя и немного медленнее:-)
На данный момент я использую быструю сортировку, но самое забавное, что это почти не быстрее, чем пузырьковая сортировка! Возможно из-за небольшого количества предметов. Сортировка составляет почти 50% от общего времени работы метода.
РЕДАКТИРОВАТЬ:
Мейсон Уилер спросил, почему нужно оптимизировать. Одна из причин заключается в том, что метод будет вызываться 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 и обменов:-)
22 ответа
Я не так много знаю о Техасском Холдеме: имеет ли значение, какие масти 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, но я думаю, что это просто. Хотя это будет много печатать...) Таким образом, сортировка не займет много времени совсем. Сгенерированные перестановки уже упорядочены.
Для очень маленького набора сортировка вставки обычно может превзойти быструю сортировку, потому что у нее очень низкие накладные расходы.
WRT ваше редактирование, если вы уже в основном в порядке сортировки (последние 5 элементов уже отсортированы), сортировка вставкой определенно подходит. В почти отсортированном наборе данных он будет превосходить быструю сортировку каждый раз, даже для больших наборов. (Особенно для больших наборов! Это лучший вариант сценария вставки и худший случай быстрой сортировки.)
Не знаю, как вы это реализуете, но то, что вы могли бы сделать, это иметь массив 52 вместо 7 и просто вставить карту в ее слот непосредственно, когда вы ее получите, поскольку никогда не может быть дубликатов, таким образом, у вас никогда не будет отсортировать массив. Это может быть быстрее в зависимости от того, как его использовать.
Поскольку последние 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;
Есть только 5040 перестановок из 7 элементов. Вы можете программно сгенерировать программу, которая найдет ту, которая представлена вашим вводом, за минимальное количество сравнений. Это будет большое дерево if-then-else инструкции, каждая из которых сравнивает фиксированную пару узлов, например if (a[3]<=a[6]),
Сложная часть решает, какие 2 элемента сравнивать в конкретном внутреннем узле. Для этого вы должны принять во внимание результаты сравнений в узлах-предках от корневого до определенного узла (например, a[0]<=a[1], not a[2]<=a[7], a[2]<=a[5]) и множество возможных перестановок, которые удовлетворяют сравнения. Сравните пару элементов, которые разбивают множество на равные части, насколько это возможно (минимизируйте размер большей части).
Если у вас есть перестановка, сортировать ее за минимальный набор перестановок тривиально.
Используйте 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 карт уже отсортирован, сортируйте список из двух карт (сравнение и своп), а затем объедините два списка, то есть 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) и копирование в 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 операторов (но все же быстрее, чем любой другой подход к сортировке).
Для семи чисел наиболее эффективным алгоритмом, который существует в отношении числа сравнений, является алгоритм Форда-Джонсона. На самом деле, википедия ссылается на газету, которую легко найти в 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 Затем вы вызываете функцию, передающую Po1, Po2, P1, P2, C1, C2, C3, C4, C5, и эта функция возвращает все возможные перестановки, основанные на Po1 и Po2 (это 36 комбинаций). Лично я думаю, что это самое быстрое, что вы можете получить. Вы полностью избегаете необходимости что-либо заказывать, потому что данные будут предварительно заказаны. В любом случае, вы берете на себя некоторые сравнения, чтобы вычислить начало и конец, но их стоимость сведена к минимуму, так как большинство из них будут на самых внешних циклах, поэтому они не будут повторяться много. И они могут быть даже более оптимизированы за счет большего дублирования кода.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
Код ниже близок к оптимальному. Это можно было бы сделать лучше, составив список, который нужно просмотреть при создании дерева, но сейчас у меня нет времени. Ура!
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.
Используйте полубайты в качестве индексов для соответствующих отсортированных подмассивов. Вам понадобится 13 наборов из 16 под-массивов (или просто 16 под-массивов, использующих второе перенаправление, или выполняйте битовые операции, а не ищите ответ; что быстрее зависит от платформы).
Объединить непустые вложенные массивы в окончательный массив.
Вы можете использовать больше, чем грызть, если хотите; байты дают 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;
}
Используйте сеть сортировки, как в этом коде 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
}
Используйте функцию выше, если вы хотите передать ей итератор или указатель, и используйте функцию ниже, если вы хотите передать ей семь аргументов один за другим. Кстати, использование шаблонов позволяет компиляторам генерировать действительно оптимизированный код, поэтому не стоит 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
}
Для 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 элементов будет больше, но его не так сложно создать.
Если вы ищете очень низкие издержки, оптимальную сортировку, вы должны создать сеть сортировки. Вы можете сгенерировать код для сети из 7 целых чисел, используя алгоритм Бозе-Нельсона.
Это гарантировало бы фиксированное количество сравнений и равное количество обменов в худшем случае.
Сгенерированный код некрасив, но он оптимален.
Пузырьковая сортировка - ваш друг. Другие виды имеют слишком много служебных кодов и не подходят для небольшого количества элементов
ура
Ваши данные находятся в отсортированном массиве, и я предполагаю, что вы меняете две новые, если это необходимо, так что также сортируются, поэтому a. если вы хотите сохранить его на месте, используйте форму вставки; б. если вы хотите получить результат, то в другом массиве выполните слияние путем копирования.
С небольшими числами бинарная рубка излишня, а троичная рубка уместна в любом случае: одна новая карта будет в основном разделена на две и три, а именно. 2+3 или 3+2, две карты на одиночные и парные, например, 2+1+2.
Таким образом, наиболее эффективный с точки зрения времени и времени способ размещения меньшей новой карты - это сравнить с [1] (то есть пропустить [0]), а затем выполнить поиск влево или вправо, чтобы найти карту, которую следует сместить, затем поменять местами и переместить вправо. (смещается, а не пузырится), сравнивая с новой картой большего размера, пока вы не найдете, куда она идет. После этого вы двинетесь вперёд (две карты были вставлены). Переменные, содержащие новые карты (и свопы), должны быть регистрами.
Подход поиска будет быстрее, но использует больше памяти.
То, на что ссылается JRL - это сортировка сегмента. Поскольку у вас есть конечный дискретный набор возможных значений, вы можете объявить 52 сегмента и просто отбросить каждый элемент в блок за O(1) раз. Следовательно, сортировка ведра O(n). Без гарантии конечного числа различных элементов самая быстрая теоретическая сортировка - это O(n log n), а такие вещи, как сортировка слиянием - быстрая сортировка. Тогда это просто баланс лучших и худших сценариев.
Но длинный ответ короткий, используйте сортировку ведра.
Учитывая, что последние 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;
Если вам нравится упомянутое выше предложение сохранить массив из 52 элементов, который всегда сохраняет ваш массив отсортированным, то, возможно, вы можете сохранить другой список из 7 элементов, который будет ссылаться на 7 допустимых элементов в массиве из 52 элементов. Таким образом, мы даже можем избежать анализа массива из 52 элементов.
Я думаю, для того, чтобы это было действительно эффективно, нам нужно иметь структуру типа связанного списка, которая будет поддерживать операции: InsertAtPosition() и DeleteAtPosition() и быть эффективной при этом.
Взгляните на это:
http://en.wikipedia.org/wiki/Sorting_algorithm
Вам нужно будет выбрать тот, который будет иметь стабильную стоимость в худшем случае...
Другим вариантом может быть сохранение сортировки массива все время, поэтому добавление карты сохранит сортировку массива автоматически, так что вы можете перейти к сортировке...
Вот ваш основной вид 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;
В ответах много петель. Учитывая его требования к скорости и крошечный размер набора данных, я не буду делать никаких циклов.
Я не пробовал это, но я подозреваю, что лучший ответ - полностью развернутая пузырьковая сортировка. Это также, вероятно, получит значительное количество преимуществ от сборки.
Интересно, если это правильный подход, все же. Как вы собираетесь анализировать 7-карточную руку? Я думаю, что вы все равно преобразуете его в другое представление для анализа. Разве массив 4x13 не будет более полезным представлением? (И это все равно сделает вопрос сортировки спорным.)