將整數轉換爲笛卡爾座標的替代/更快方法？

作爲一個有趣的項目幫助我學習另一個PHP MVC框架，我一直在寫Reversi/Othello作爲一個PHP的& Ajax應用程序，大多是直截了當的東西。我決定不使用多維數組有多種原因，而是有一個線性數組（本例中爲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的樣式問題。

來源

2009-02-03 David

你可以使用的比特，移位運算符除以8乘以？（<< 3 and >> 3） – 2009-02-03 14:38:10

我沒有在PHP中做過多的位操作，但它確實有所有的標準位操作符（AND，XOR，OR +移位），所以值得一試。 – David 2009-02-03 14:43:48

我現在沒有時間來測量這個問題，但我會懷疑預先計算的查找表會在速度上超過您的解決方案。該守則將是這個樣子：

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);

當然，這確實增加了不少過頭，這樣在實踐中你只會打擾預先計算所有座標，如果你轉換的代碼被稱爲非常常。

來源

2009-02-03 14:39:58

預先計算的查找表迄今爲止是另外兩個時間的一半中最快的。 – David 2009-02-03 15:28:02

我會這麼想，但很高興知道！感謝測量。 – 2009-02-03 15:51:44

哦，是的！這是二進制的一個很好的例子：

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

現實情況是，一個好的編譯器會發現這個優化，並使用它，所以它不是一定會更快。測試並看看你的編譯器/解釋器是否這樣做。

它的工作原理是任何二進制除以8與右移三位相同。現代處理器具有桶式移位器，可以在一條指令中實現高達32位的移位。

反向一樣簡單：

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

- 亞當

來源

2009-02-03 14:42:47

我現在不在測量的位置，但你應該能夠勉強維持一些額外的速度與此：

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

編輯：不理我 - 亞當的錯誤答案應該是優越的。

來源

2009-02-03 14:42:59 mwigdahl

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

這是一個快一點，因爲沒有VAR聲明和做作。

來源

2009-02-03 14:56:58

我認爲你的大部分性能在最後返回數組（...）會丟失。相反，我建議：
*定義兩個功能，一個用於x和一個y的
或
*內嵌代碼中的位運算需要的計算

來源

2009-02-03 16:11:36 Ron

將整數轉換爲笛卡爾座標的替代/更快方法？

回答

相關問題