14

通过Cactus Kev 的 Poker Hand Evaluator阅读，我注意到以下陈述：

起初，我认为我总是可以先对手进行分类，然后再将其传递给评估者；但是排序需要时间，我不想浪费任何 CPU 周期来排序。我需要一种不关心五张卡片的顺序的方法。
……
经过深思熟虑，我有了一个使用素数的头脑风暴。我会为十三张牌中的每张牌分配一个素数值……这个系统的美妙之处在于，如果你将手中每张牌的素数相乘，你就会得到一个独特的产品，不管顺序如何五张牌中。
...
由于乘法是计算机可以进行的最快计算之一，如果我们在评估之前被迫对每只手进行排序，我们的时间已经减少了数百毫秒。

我很难相信这一点。

Cactus Kev 将每张牌表示为一个 4 字节整数，并通过调用 来评估手牌eval_5cards( int c1, int c2, int c3, int c4, int c5 )。我们可以将卡片表示为一个字节，而将扑克牌表示为一个 5 字节的数组。对这个 5 字节数组进行排序以获得独特的手必须非常快。它比他的方法更快吗？

如果我们保留他的表示形式（卡片为 4 字节整数）怎么办？对 5 个整数的数组进行排序是否比将它们相乘更快？如果不是，可以进行哪些低级优化来加快对少量元素的排序？

谢谢！

大家好回答；我正在对排序与乘法的性能进行基准测试，以获得一些硬性能统计数据。

4

11 回答 11

6

未经测试，我对他的论点表示同情。与排序（即n log n. 具体来说，最优排序网络需要 9 次比较。然后，评估者必须至少查看排序数组的每个元素，这是另外 5 次操作。

于 2010-06-28T18:37:08.730 回答
6

当然，这在很大程度上取决于您计算机的 CPU，但典型的 Intel CPU（例如 Core 2 Duo）可以在 3 个 CPU 时钟周期内将两个 32 位数字相乘。要使排序算法击败它，该算法需要比 3 * 4 = 12 个 CPU 周期更快，这是一个非常严格的约束。没有一个标准的排序算法可以肯定地在少于 12 个周期内完成。单独比较两个数字将花费一个 CPU 周期，结果的条件分支也将花费一个 CPU 周期，然后无论您做什么都将至少花费一个 CPU 周期（交换两张卡实际上至少需要 4 个 CPU 周期）。所以乘法获胜。

当然，这并没有考虑从一级或二级缓存甚至内存中获取卡值的延迟；但是，这种延迟适用于任何一种情况，即乘法和排序。

于 2010-06-28T18:43:49.567 回答
5

排序本质上并不比乘法难。在纸面上，它们大致相同，并且您还需要一个复杂的乘法算法来使大型乘法与大型排序竞争。此外，当所提出的乘法算法可行时，还可以使用桶排序，它渐近更快。

然而，一手牌并不是一个渐近的问题。这只是 5 张牌，他只关心这张牌的 13 个数值中的一个。即使乘法在原则上很复杂，但实际上它是用微码实现的，而且速度非常快。他正在做的工作。

现在，如果您对理论问题感兴趣，还有一个使用加法而不是乘法的解决方案。任何一个值只能有 4 张卡，因此您也可以分配值 1,5,25,...,5^12 并将它们相加。它仍然适合 32 位算术。还有其他具有其他数学属性的基于加法的解决方案。但这真的没关系，因为微编码算术比计算机所做的任何其他事情都要快得多。

于 2010-06-28T19:24:58.180 回答
2

使用优化的决策树可以对 5 个元素进行排序，这比使用通用排序算法要快得多。

然而，事实仍然是排序意味着很多分支（就像之后必要的比较一样）。分支对于现代流水线 CPU 架构来说真的很糟糕，尤其是那些以相似的可能性去往任何方向的分支（从而破坏了分支预测逻辑）。这比乘法与比较的理论成本要高得多，使乘法更快。

但是，如果您可以构建定制硬件来进行分类，它最终可能会更快。

于 2010-06-28T18:46:37.557 回答
1

这不应该是真正相关的，但他是正确的。排序比乘法花费更长的时间。

真正的问题是他对得到的素数做了什么，以及这有什么帮助（因为考虑到它，我预计需要比排序更长的时间。

于 2010-06-28T18:38:02.083 回答
1

很难想象任何排序操作比乘以相同的一组数字更快。在处理器级别，乘法只是load, load, multiply, load, multiply, ...，可能需要对累加器进行一些操作。它是线性的，易于流水线化，无法与相关的分支错误预测成本进行比较。每个要相乘的值平均应该有大约 2 条指令。除非乘法指令非常缓慢，否则很难想象更快的排序。

于 2010-06-28T18:41:31.577 回答
1

值得一提的是，即使您的 CPU 的乘法指令非常慢（或不存在......），您也可以使用查找表来进一步加快速度。

于 2010-06-28T19:24:14.783 回答
1

经过深思熟虑，我有了一个使用素数的头脑风暴。我会为十三张牌中的每一张牌分配一个素数值......这个系统的美妙之处在于，如果你将手中每张牌的素数相乘，无论顺序如何，你都会得到一个独特的产品五张牌中。

这是一个非位置数字系统的例子。

我找不到理论的链接。作为应用代数的一部分，我研究了它，在欧拉的整体和加密的某个地方。（我可能对术语有误，因为我已经用我的母语学习了所有这些。）

如果我们保留他的表示形式（卡片为 4 字节整数）怎么办？对 5 个整数的数组进行排序是否比将它们相乘更快？

RAM 是一种外部资源，通常比 CPU 慢。由于交换操作，对 5 个整数进行排序总是必须进入 RAM。在这里加上排序函数本身的开销，乘法就不再那么糟糕了。

我认为在现代 CPU 上，整数乘法几乎总是比排序快，因为可以在不同的 ALU 上同时执行多个乘法，而只有一条总线将 CPU 连接到 RAM。

如果不是，可以进行哪些低级优化来加快对少量元素的排序？

使用冒泡排序可以很快地对 5 个整数进行排序：qsort 将使用更多内存（用于递归），而优化良好的冒泡排序将完全从 d-cache 工作。

于 2010-06-28T20:02:37.823 回答
0

正如其他人指出的那样，单独排序并不比乘以 5 个值更快。然而，这忽略了他的解决方案的其余部分。在鄙视 5 元素排序之后，他继续对 4888 个值的数组进行二进制搜索 - 至少 12 次比较，比排序要求的要多！

请注意，我并不是说有更好的解决方案涉及排序——我个人还没有充分考虑——只是排序只是问题的一部分。

他也不必使用素数。如果他简单地将每张牌的值编码为 4 位，他需要 20 位来表示一手牌，给出 0 到 2^20 = 1048576 的范围，大约是使用素数产生的范围的 1/100，并且足够小（尽管仍然存在缓存一致性问题）来生成一个查找表。

当然，一个更有趣的变体是拿 7 张牌，例如德州扑克等游戏中的牌，然后找出最好的 5 张牌。

于 2010-06-28T20:48:44.157 回答
0

乘法速度更快。

任何给定数组的乘法总是比对数组进行排序更快，假设乘法会产生有意义的结果，并且查找表是无关紧要的，因为代码旨在评估扑克手，因此您需要在无论如何排序。

于 2010-06-29T03:05:57.500 回答
0

一个现成的德州扑克 7 张和 5 张牌评估器的示例可以在此处找到文档并在此处进一步解释。欢迎在其中找到的电子邮件地址提供所有反馈。

您不需要排序，并且在评估 7 张牌时，通常（约 97% 的时间）只需 6 次加法和几次位移即可逃脱。该算法使用一个生成的查找表，它占用大约 9MB 的 RAM，并且是在几乎瞬间生成的。便宜的。所有这些都是在 32 位内完成的，并且“内联”7 张卡片评估器非常适合在我的笔记本电脑上每秒评估大约 50m 随机生成的手牌。

哦，乘法比排序快。

于 2011-03-24T05:54:37.290 回答