Альтернативные / более быстрые методы преобразования целого числа в декартову координату?

Question

В качестве забавного побочного проекта для себя, чтобы помочь в изучении еще одной 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);
}

И ради потомков, метод, который я написал дляordin2int

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

Обновление:
Таким образом, в стране странных результатов оказалось не то, что я ожидал, а использование предварительно вычисленной таблицы поиска в большинстве случаев показало, что это самая быстрая, предполагаемая торговая память на скорость, всегда победитель?

• Здесь была таблица с временами, но я сократил ее из-за проблем со стилем в SO.

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

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

Конечно, это добавляет много накладных расходов, так что на практике вы бы потрудились предварительно вычислить все координаты, если ваш код преобразования был назван очень часто.

Answer 3

Я думаю, что большая часть вашей производительности теряется при возврате массива (...) в конце. Вместо этого я предлагаю:
* определить две функции, одну для х и одну для у
или
* встроенная битовая арифметика в коде, требующем вычисления

Answer 4

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

это немного быстрее, потому что нет объявления и изменения var.

Answer 5

Я не в состоянии измерять прямо сейчас, но вы должны быть в состоянии получить некоторую дополнительную скорость с этим:

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

edit: игнорировать меня - ответ Адама на биты должен быть лучше.