哪个更快 - 排序或乘以一小部分元素？
https://stackoverflow.com/questions/3135141
-
01-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
阅读 仙人掌凯夫的扑克手评估员, ，我注意到以下陈述：
起初，我认为在将手传递给评估者之前，我总是可以首先先对手进行分类。但是分类需要时间，我不想浪费任何CPU周期分类。我需要一种不在乎给出的五张订单的方法。
...
经过深思熟虑，我进行了头脑风暴来使用质数。我会为13张卡中的每一个分配一个质数值...该系统的优点是，如果您将每张卡的等级的质量值乘以您的手中，则无论订单如何五张卡片。
...
由于乘法是计算机可以进行的最快计算之一，因此，如果我们在评估之前被迫分类数百毫秒的时间。
我很难相信这一点。
仙人掌Kev将每张卡表示为4字节整数，并通过致电评估手 eval_5cards( int c1, int c2, int c3, int c4, int c5 ). 。我们可以将卡表示为一个字节，将扑克手作为5字节阵列。对这个5字节阵列进行排序以获得独特的手必须很快。比他的方法快吗？
如果我们保持他的代表性（作为4字节整数）怎么办？排序5个整数的数组比乘以它们更快吗？如果没有，可以做些什么样的低级优化来使对少数元素进行排序的速度更快？
谢谢！
好的回答每个人；我正在努力测试分类与乘法的性能，以获取一些硬性能统计。
解决方案
排序在本质上比乘数字更难。从表面上看，它们大致相同，您还需要一个复杂的乘法算法来使大型乘法与大型竞争。此外，当提出的乘法算法是可行的时，您也可以使用铲斗排序，渐近地更快。
但是，扑克手并不是渐近问题。它只有5张卡片，他只关心卡的13个数值之一。即使乘法原则上是复杂的，实际上它是在微码中实现的，并且非常快。他在做什么。
现在，如果您对理论问题感兴趣，那么也有一个使用添加而不是乘法的解决方案。任何一个值只能有4张卡，因此您可以同样分配值1,5,25，...，5^12并添加它们。它仍然适合32位算术。还有其他基于其他数学属性的基于添加的解决方案。但这确实没关系，因为微编码的算术比计算机所做的任何事情都要快得多。
其他提示
当然，这在很大程度上取决于计算机的CPU，但是典型的Intel CPU（例如Core 2 Duo）可以在3个CPU时钟周期内乘以两个32位数字。为了使某种算法击败它，算法需要比3 * 4 = 12 CPU周期更快，这是一个非常紧密的约束。肯定不会在少于12个周期中进行标准排序算法。仅两个数字的比较将需要一个CPU周期，结果上的条件分支也将花费一个CPU周期，然后您所做的任何事情至少将需要一个CPU周期（交换两张卡实际上将至少需要4个CPU周期）。如此繁殖的胜利。
当然，这并没有考虑到从1或第二级缓存甚至内存中获取卡值的延迟。但是，此延迟适用于任何一种情况，乘以和排序。
没有测试，我对他的论点表示同情。与排序相比，您可以在4个乘法中执行此操作 n log n. 。具体而言，最佳 排序网络 需要9个比较。然后，评估者必须至少查看排序阵列的每个元素，这是另外5个操作。
可以使用优化的决策树对5个元素进行排序，该元素比使用通用分类算法要快得多。
但是，事实仍然是，排序意味着很多分支（以及以后必要的比较）。分支是 真的 对现代管道的CPU体系结构不利，尤其是具有类似可能性的两种方式的分支（从而击败了分支预测逻辑）。这比乘法与比较的理论成本要多得多，使乘法更快。
但是，如果您可以构建自定义硬件进行分类，则 可能 最终更快。
这不应该真正相关，但他是正确的。排序比乘以更长的时间。
真正的问题是他对由此产生的质量数字做了什么，以及这是有帮助的（因为考虑到它，我期望花费比分类更长的时间。
很难想到任何分类操作比乘以同一组数字更快的分类操作。在处理器级别，乘法仅仅是 load, load, multiply, load, multiply, ..., ，也许对累加器的操纵也可能被扔进去。它是线性的，很容易管道，没有与相关的分支错误预测成本进行比较。每个值平均应乘以2个指令。除非倍数指令慢慢慢，否则很难想象更快的速度。
值得一提的一件事是，即使您的CPU的倍数指令慢慢（或不存在...），您也可以使用查找表来进一步加快速度。
经过深思熟虑，我进行了头脑风暴来使用质数。我会为13张卡中的每一个分配一个质数值...该系统的优点是，如果您将每张卡的等级的质量值乘以您的手中，则无论订单如何五张卡片。
这是非置换数字系统的一个示例。
我找不到与理论的链接。我研究了作为应用代数的一部分，该代数的某个位置周围的某个位置和加密。 （由于我已经用母语研究了所有这些，我可能会错过术语。）
如果我们保持他的代表性（作为4字节整数）怎么办？排序5个整数的数组比乘以它们更快吗？
RAM是一种外部资源，与CPU相比通常更慢。由于交换操作，对5个INT进行排序总是必须去RAM。在这里添加排序函数本身的开销，乘法停止看起来不错。
我认为，在现代CPU上，整数乘法几乎总是比排序更快，因为可以在不同的Alus上同时执行几个乘法，而只有一辆总线将CPU连接到RAM。
如果没有，可以做些什么样的低级优化来使对少数元素进行排序的速度更快？
5个整数可以很快使用 气泡排序: ：Qsort将使用更多的内存（用于递归），而优化的气泡排序将完全从D-CACH中使用。
正如其他人指出的那样，单独的排序并不比乘以5个值更快。但是，这忽略了他的其余解决方案。在拆除了5元素排序之后，他继续对4888个值的数组进行二进制搜索 - 至少12个比较，比所需的类型还要多！
请注意，我并不是说有一个更好的解决方案涉及分类 - 我个人没有给出足够的思考 - 仅仅分类只是问题的一部分。
他也不必使用素数。如果他只是简单地用4位编码每张卡的值，他需要20位代表一只手，给出0至2^20 = 1048576的范围，约1/100使用使用素数，并且足够小（尽管仍然遭受了缓存相干性问题）来生产一个查找表。
当然，一个更有趣的变体是要拿7张卡片，例如在德克萨斯·霍尔德姆（Texas Holdem）等游戏中发现的那样，并找到可以用它们制作的最好的5张纸牌。
乘法更快。
任何给定数组的乘法始终比对数组进行排序始终更快，假定乘法会产生有意义的结果，并且查找表是无关紧要的，因为该代码旨在评估扑克手，因此您需要对查找进行查找无论如何，排序的设置。
