Rud*_*ger 14 c sorting algorithm poker optimization
通过Cactus Kev的扑克手评估员阅读,我注意到以下声明:
起初,我认为在将它传递给评估者之前,我总是可以先简单地对手进行排序; 但排序需要时间,我不想浪费任何CPU周期整理手.我需要一种不关心五张牌的顺序的方法.
......
经过深思熟虑,我有一个头脑风暴来使用素数.我会给十三个卡片等级中的每一个分配一个素数值......这个系统的优点在于,如果你将每张卡片的等级的主要值乘以你手中,你将获得一个独特的产品,无论订单如何五张牌.
...
由于乘法是计算机可以进行的最快计算之一,如果我们在评估之前被迫对每只手进行排序,我们已经减少了数百毫秒的时间.
我很难相信这一点.
Cactus Kev将每张卡片表示为4字节整数,并通过调用来评估指针eval_5cards( int c1, int c2, int c3, int c4, int c5 ).我们可以将卡表示为一个字节,将扑克手表示为5字节数组.对这个5字节数组进行排序以获得一个独特的手必须非常快.它比他的方法快吗？
如果我们保持他的表示(卡片为4字节整数)怎么办？可以对5个整数的数组进行排序比乘以它们更快吗？如果没有,可以采用何种低级优化来更快地对少量元素进行排序？
谢谢!
大家好的答案; 我正在对排序与乘法的性能进行基准测试,以获得一些硬性能统计数据.
当然,它在很大程度上取决于您的计算机的CPU,但典型的Intel CPU(例如Core 2 Duo)可以在3个CPU时钟周期内乘以两个32位数.对于要击败它的排序算法,算法需要比3*4 = 12个CPU周期更快,这是一个非常严格的约束.没有一种标准排序算法可以在少于12个周期内完成.单独比较两个数字将占用一个CPU周期,结果上的条件分支也将占用一个CPU周期,无论你做什么,至少需要一个CPU周期(交换两个卡实际上至少需要4个CPU周期).所以倍增胜利.
当然,这不是考虑延迟来从第一级或第二级缓存甚至是内存中获取卡值; 但是,这种延迟适用于案例,乘法和排序.
排序本质上并不比数字乘法更难.从理论上讲,它们大致相同,而且你还需要一种复杂的乘法算法来使大型乘法与大型竞争相提并论.此外,当提出的乘法算法可行时,您也可以使用桶式排序,这种方法渐进式更快.
然而,扑克牌不是渐近问题.它只有5张牌,他只关心卡的13个数值中的一个.即使乘法原则上复杂,实际上它也是用微码实现的,并且速度非常快.他正在做什么.
现在,如果你对理论问题感兴趣,还有一个使用加法而不是乘法的解决方案.任何一个值只能有4张卡,所以您也可以分配值1,5,25,...,5 ^ 12并添加它们.它仍适用于32位算术.还有其他基于加法的解决方案与其他数学属性.但它确实没关系,因为微编码算法比计算机正在做的任何其他事情都要快得多.
| 归档时间： |
|
| 查看次数： |
1103 次 |
| 最近记录： |