排序7个整数数组的最快方法是什么？
https://stackoverflow.com/questions/1415173
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
这是分析扑克赔率的程序的一部分，特别是德州扑克。我有一个我很满意的程序，但它需要一些小的优化才能完美。
我使用这种类型（当然还有其他类型）：
type
T7Cards = array[0..6] of integer;
在决定如何对数组进行排序时，这个数组有两件事可能很重要：
- 每个项目都是0到51之间的值。没有其他值可以。
- 没有重复。从不。
有了这些信息，绝对最快的排序这个数组的方法是什么？我使用Delphi，所以pascal代码将是最好的，但我可以读取C和伪，虽然有点慢： - ）
目前我使用quicksort，但有趣的是，这几乎不比bubblesort快！可能因为项目数量很少。排序几乎占该方法总运行时间的50％。
编辑：
Mason Wheeler问为什么有必要进行优化。一个原因是该方法将被称为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;
在我写这篇文章时，我注意到了一件事：数组的最后五个元素将始终被排序，因此这只是将前两个元素放在数组中正确位置的问题。这应该简化一些事情。
所以，新的问题是：当最后5个元素已经排序时，对7个整数数组进行排序的最快方法是什么。我相信这可以通过几个（？）if和交换来解决： - ）
解决方案
我不太了解德州扑克：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个元素已经排序），插入排序肯定是要走的路。在几乎排序的数据集中，每次都会击败快速排序，即使对于大型集合也是如此。 （特别是对于大型集合！这是插入类型的最佳情况和quicksort的最坏情况。）
不知道你是如何实现这一点的，但你可以做的是有一个52而不是7的数组，并且当你得到它时直接将卡插入其插槽中，因为它永远不会有重复，这样你永远不必排序数组。这可能会更快，具体取决于其使用方式。
7个元素只有5040个排列。您可以通过编程方式生成一个程序，在最少数量的比较中找到输入所代表的程序。它将是一个if-then-else指令的大树，每个都比较一对固定的节点，例如if (a[3]<=a[6])。
棘手的部分是确定在特定内部节点中要比较哪两个元素。为此，您必须考虑从根到特定节点（例如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。一次搜索最小和最大元素并将它们放入结果数组中。重复三次。 （编辑：不，我不会尝试在理论上测量速度：_））
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卡列表已经排序，请对双卡列表进行排序（比较<！> amp; swap），然后合并两个列表，即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个语句（但仍然比任何其他排序方法更快）。
对于七个数字，与比较次数相关的最有效算法是Ford-Johnson's。事实上，维基百科引用了一篇很容易在Google上找到的论文，声称福特 - 约翰逊是最好的最多47个号码。不幸的是，对Ford-Johnson的引用并不容易找到，算法使用了一些复杂的数据结构。
如果您可以访问该书，它将出现在Donald Knuth的“计算机编程艺术”第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，第2和第7（从高到低排序），然后交换P1，然后P2向下。使用列表，您只需要根据需要修复指针。
然而，再一次，由于您的代码的特殊性，如果您遵循 nikie 建议并且只是适当地为每个变量生成for循环，其中P1和P2可以出现在列表中。
例如，对P1和P2进行排序，使P1 <！> lt; 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种组合）的所有可能的排列。
就我个人而言，我认为这是你能得到的最快的。您完全避免订购任何东西，因为数据将被预订。无论如何，你都需要进行一些比较来计算开始和结束，但是它们的成本最小化，因为它们中的大多数将位于最外层的循环上，所以它们不会重复太多。而且它们甚至可以以更多代码重复为代价进行更优化。
对于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;
这是桶排序的应用程序，通常应该比任何比较更快所建议的种类。
注意：第二部分也可以通过在线性时间内迭代比特来实现，但实际上它可能不会更快：
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。
使用半字节作为相应排序子数组的索引。您需要13组16个子阵列（或者只需要16个子阵列并使用第二个间接，或者执行位操作而不是查找答案;更快的速度因平台而异）。
将非空子数组连接到最终数组中。
如果你愿意，可以使用大于半字节的数字; bytes将提供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;
}
看看这个：
http://en.wikipedia.org/wiki/Sorting_algorithm
您需要选择一个具有稳定最差案例成本的人......
另一种选择可能是保持数组整个时间排序，所以添加一张卡会使数组自动排序，这样你就可以跳到排序...
JRL所指的是一种桶式排序。由于您有一组有限的离散可能值，因此您可以声明52个桶，并在O（1）时间内将每个元素放入存储桶中。因此桶排序是O（n）。如果没有有限数量的不同元素的保证，最快的理论排序是O（n log n），像合并排序这样的东西是快速排序的。这只是最佳和最差情况的平衡。
但是很长的答案很短，请使用铲斗排序。
如果你喜欢上面提到的建议来保持一个52元素数组，它始终保持你的数组排序，那么你可以保留另一个7元素列表，这些元素将引用52元素数组中的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 + 3或3 + 2， 两张牌成单打和成对，例如2 + 1 + 2。
因此，放置较小的新卡的最有时空效率的方法是与[1]（即跳过[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
}
如果要传递迭代器或指针，请使用上面的函数，如果要逐个传递七个参数，请使用下面的函数。顺便说一句，使用模板允许编译器生成真正优化的代码，因此除非您需要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
}
