Bir kartezyen bir tamsayı dönüştürme alternatif / hızlı yöntemler koordine?

4 Cevap php

Henüz başka bir PHP MVC framework öğrenmeye yardımcı olmak için kendim için eğlenceli bir yan proje olarak, ben bir PHP gibi Reversi / Othello yazıyorum & oldum Ajax uygulaması, çoğunlukla basit şeyler. Ben nedenlerle bir dizi için çok boyutlu bir dizi kullanarak karşı karar ve yerine tamsayılar koordinatlara dönüştürmek için (64 unsurlar uzun zamandır bu durumda) bir doğrusal dizi ve bir kaç yöntem var.

Bu yüzden merak ettim, bir koordinat noktasına bir tamsayı dönüştürmek için herhangi diğer muhtemelen daha hızlı algoritmalar var?

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

Ve kuşaklar uğruna, metot coord2int için yazdı

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

Update:
So in the land of the weird, the results were not what I was expecting but using a pre-computed lookup table has predominantly shown to be the fastest, guess trading memory for speed is always a winner?

  • Orada kez bir tablo burada ama ben SO ile nedeniyle şekillendirme sorunları kesti.

4 Cevap

Ben şu anda bu kendimi ölçmek için vaktim yok, ama ben bir ön bilgisayarlı arama tablosu hız içinde çözüm yeneceğini şüpheli olur. Kod şöyle bir şey olacaktır:

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

Tabii ki, bu dönüşüm kod very sık sık adı ise pratikte sadece önceden hesaplamak için tüm koordinatları rahatsız olur böylece aşırı baş bir sürü eklese.

Ah evet! Bu ikili mükemmel bir örneğidir:

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

Gerçekte iyi bir derleyici bu optimizasyon bulmak ve kullanmak olacaktır, böylece daha hızlı mutlaka değil. Test ve derleyici / yorumlayıcı bu yaparsa bakın.

8 ile herhangi bir ikili bölme 3 bit ile bir sağa kayması olarak aynı olduğu için çalışır. Modern işlemciler tek bir talimat, bir 32 bit vardiya kadar yapabilirsiniz varil değiştirenleriz var.

Ters kadar kolaydır:

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

Ben şu anda ölçmek için bir konumda değilim, ama bu bazı ek hızını artırmak gerekir:

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

edit: Beni görmezden - Adem'in bitshifting cevabı üstün olmalıdır.

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

hayır var beyan ve özenti olduğu için bu biraz daha hızlıdır.

etiketler