排序7个整数数组的最快方法是什么？

Question

这是分析扑克几率的程序的一部分,特别是德州扑克.我有一个我很满意的程序,但它需要一些小的优化才能完美.

我使用这种类型(当然还有其他类型):

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

在决定如何对其进行排序时,此数组有两件事可能很重要:

1. 每个项目都是0到51之间的值.没有其他值可以.
2. 没有重复.决不.

有了这些信息,对这个数组进行排序的绝对最快的方法是什么？我使用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和交换来解决:-)

Answer 1

对于一个非常小的集合,插入排序通常可以击败快速排序,因为它具有非常低的开销.

WRT你的编辑,如果你已经大部分按排序顺序(最后5个元素已经排序),插入排序肯定是要走的路.在几乎排序的数据集中,每次都会击败快速排序,即使对于大型集合也是如此.(特别是对于大型集合!这是插入排序的最佳情况和quicksort的最坏情况.)

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,但我认为这很简单.虽然它会打字很多......)这样,排序不需要任何时间一点都不 生成的排列已经被排序.