c - 哪个更快——对小数组元素进行排序或相乘?

标签 c algorithm optimization sorting poker

通读 Cactus Kev's Poker Hand Evaluator ,我注意到以下陈述:

At first, I thought that I could always simply sort the hand first before passing it to the evaluator; but sorting takes time, and I didn't want to waste any CPU cycles sorting hands. I needed a method that didn't care what order the five cards were given as.
...
After a lot of thought, I had a brainstorm to use prime numbers. I would assign a prime number value to each of the thirteen card ranks... The beauty of this system is that if you multiply the prime values of the rank of each card in your hand, you get a unique product, regardless of the order of the five cards.
...
Since multiplication is one of the fastest calculations a computer can make, we have shaved hundreds of milliseconds off our time had we been forced to sort each hand before evaluation.


我很难相信这一点。

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 周期)。所以乘法获胜。

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

关于c - 哪个更快——对小数组元素进行排序或相乘?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3135141/

相关文章:

c - 在C中将BSTR转换为CHAR *并将CHAR *转换为BSTR

c - 我们需要从头文件导入的方法的函数原型(prototype)的原因

algorithm - 在固定长度的输入上证明完美的哈希函数

C#委托(delegate)编译器优化

c++ - g++与手动优化进行复数乘法

C++ 数组 [索引] 与索引 [数组]

c - 为什么* str1和*(&str1)的str是C语言中的char数组的名称,为什么没有得出相同的结果?

java - 给定 n 和 k,返回第 k 个排列序列

java - 破解编码面试 : Why does the recursive subset algorithm increase the index rather than decreasing it?

jquery - 通过CSS标签过滤jQuery结果