将整数转换为笛卡尔坐标的候选/更快方法？

Question

作为一个有趣的个人项目，我想通过编写PHP & Ajax应用程序来学习另一个PHP MVC框架，并实现翻转棋/奥赛罗游戏。大部分都是直截了当的内容。出于多种原因，我决定不使用多维数组，而是使用一维数组（在这种情况下是64个元素长）以及几种方法来将坐标转换为整数。

因此，我很好奇，是否有其他更快的算法可以将整数转换为坐标点？

function int2coord($i){
    $x = (int)($i/8);
    $y = $i - ($x*8);      
    return array($x, $y);
}

//Not a surprise but this is .003 MS slower on average
function int2coord_2($i){
    $b = base_convert($i, 10, 8);
    $x =  (int) ($b != 0 ? $b/8 : 0); // could also be $b < 8 for condition
    $y = $b % 10;
    return array($x, $y);
}

为了纪念，我写的coord2int方法如下：

function coord2int($x, $y){
   return ($x*8)+$y;
}

更新：
所以在这个奇怪的世界上，结果并不是我期望的，但使用预先计算好的查找表已经被证明是最快的，猜测用内存换速度总是赢家？

• 这里有一个时间表，但由于与SO的样式问题而被删除。

- David

---

你可以使用位移运算符（<< 3 和 >> 3）来进行8的倍数的乘除运算吗？ - Andrew Rollings

我在PHP中没有做过太多的位操作，但它确实具有所有标准的位运算符（AND、XOR、OR + 移位），所以值得一试。 - David

Answer 1

哦，好的！这是二进制的完美例子：

function int2coord($i){
    $x = $i >> 3;
    $y = $i & 0x07;      
    return array($x, $y);
}

事实上，优秀的编译器会发现这种优化并使用它，因此不一定更快。请测试并查看您的编译器/解释器是否执行此操作。

这种方法之所以有效，是因为任何二进制数除以8都相当于将其向右移动3位。现代处理器具有可在一条指令中执行多达32位移位操作的移位寄存器。

反过来也同样简单：

function coord2int($x, $y){
   return ($x << 3)+$y;
}

-亚当

- Adam Davis

---

看起来，使用位移可能获得的任何性能提升都被 PHP 抽象化程度的高度所消耗。 - David

非常有趣。数组操作很可能已经被高度优化，但是对于二进制运算符却没有受到太多关注 - 它们在 PHP 应用程序中可能不经常使用。不知道这是否会在 Zend 优化器下发生改变... - Adam Davis

ZO 真的可以进行优化吗？我发誓它主要是一个运行混淆/加密 PHP 机器码的扩展。 - David

嗯，根据他们最新的营销文献，ZO不再进行优化。他们曾经只有一个产品，并且它确实有性能增强，但听起来他们将其分成了几个产品，只有Zend平台实际上具有性能改进。 - Adam Davis

Answer 2

我现在没有时间自己测量，但我认为预先计算好的查找表在速度上会比你的解决方案更优。代码将类似于：

class Converter  {
    private $_table;

    function __construct() 
    {
        $this->_table = array();
        for ($i=0; $i<64; $i++) {
            $this->_table[$i] = array( (int)($i/8), (int)($i%8) ); 
        }
    }

    function int2coord( $i )
    {
        return $this->_table[$i];
    }
}

$conv = new Converter(); 
$coord = $conv->int2coord( 42 );

当然，这样做会增加很多开销，因此在实践中，只有在您的转换代码非常频繁地被调用时，才需要预先计算所有坐标。

- cg

---

预先计算的查找表目前是最快的，比其他两种方法节省了一半的时间。 - David

我本以为是这样，但很高兴知道！感谢您的测量。 - cg.

我在想表格是否比位移更快。在纯汇编代码中，表格应该更快，但编译器中总会有一些有趣的开销，直到你进行测试才能看到。很高兴看到这个更快。 - Adam Davis

Answer 3

我认为大部分性能都浪费在了最后返回 array(...) 上。相反，我建议：
* 定义两个函数，一个用于 x，一个用于 y
    或者
* 在需要计算的代码中内联位运算

- Ron

Answer 4

我现在无法进行测量，但您应该能够通过以下方式获得一些额外的速度：

function int2coord($i){
  $y = $i%8;
  $x = (int)($i/8);
  return array($x, $y);
}

编辑：不要理我——Adam的位移答案应该更好。

- mwigdahl

Answer 5

function int2coord_3($i){
    return array((int) ($i / 8), ($i % 8));
}

这个稍微快一点，因为没有变量声明和赋值。

- user61975

---

在奇怪的世界里，删除多余的变量会使你的代码跻身前三。 - David