Транспонирование матрицы 4x4, представленной как удлиненное значение (как можно быстрее) - PullRequest
Новая
       22

Транспонирование матрицы 4x4, представленной как удлиненное значение (как можно быстрее)

0 голосов
/ 12 ноября 2018

Я работал над реализацией C # 2048 с целью реализации обучения с подкреплением.

Операция «слайд» для каждого хода требует, чтобы плитки перемещались и комбинировались в соответствии с конкретными правилами. Это включает в себя ряд преобразований в двумерном массиве значений.

До недавнего времени я использовал матрицу 4x4 байта: 

var field = new byte[4,4];

Каждое значение имело показатель степени 2, поэтому 0=0, 1=2, 2=4, 3=8 и т. Д. Плитка 2048 будет представлена ​​как 11.

Поскольку (практическое) максимальное значение для данного элемента мозаичного изображения составляет 15 (для которого требуется только 4 бита), возможно преобразовать содержимое этого массива байтов 4x4 в значение ulong.

Оказывается, что некоторые операции намного более эффективны с этим представлением. Например, мне обычно приходится инвертировать массивы так: 

    //flip horizontally
    const byte SZ = 4;
    public static byte[,] Invert(this byte[,] squares)
    {
        var tmp = new byte[SZ, SZ];
        for (byte x = 0; x < SZ; x++)
            for (byte y = 0; y < SZ; y++)
                tmp[x, y] = squares[x, SZ - y - 1];
        return tmp;
    }

Я могу сделать эту инверсию на ulong ~ 15x быстрее: 

    public static ulong Invert(this ulong state)
    {
        ulong c1 = state & 0xF000F000F000F000L;
        ulong c2 = state & 0x0F000F000F000F00L;
        ulong c3 = state & 0x00F000F000F000F0L;
        ulong c4 = state & 0x000F000F000F000FL;

        return (c1 >> 12) | (c2 >> 4) | (c3 << 4) | (c4 << 12);
    }

Обратите внимание на использование гекса, что чрезвычайно полезно, потому что каждый символ представляет плитку.

Операция, с которой у меня больше всего проблем, это Transpose, которая переворачивает координаты x и y значений в массиве 2d, например: 

    public static byte[,] Transpose(this byte[,] squares)
    {
        var tmp = new byte[SZ, SZ];
        for (byte x = 0; x < SZ; x++)
            for (byte y = 0; y < SZ; y++)
                tmp[y, x] = squares[x, y];
        return tmp;
    }

Самый быстрый способ, который я нашел, это использовать немного глупости: 

    public static ulong Transpose(this ulong state)
    {
        ulong result = state & 0xF0000F0000F0000FL; //unchanged diagonals

        result |= (state & 0x0F00000000000000L) >> 12;
        result |= (state & 0x00F0000000000000L) >> 24;
        result |= (state & 0x000F000000000000L) >> 36;
        result |= (state & 0x0000F00000000000L) << 12;
        result |= (state & 0x000000F000000000L) >> 12;
        result |= (state & 0x0000000F00000000L) >> 24;
        result |= (state & 0x00000000F0000000L) << 24;
        result |= (state & 0x000000000F000000L) << 12;
        result |= (state & 0x00000000000F0000L) >> 12;
        result |= (state & 0x000000000000F000L) << 36;
        result |= (state & 0x0000000000000F00L) << 24;
        result |= (state & 0x00000000000000F0L) << 12;

        return result;
    }

Шокирующе, но это все еще почти в 3 раза быстрее, чем в цикле. Тем не менее, я ищу более производительный метод, использующий использование паттерна, присущего транспозиции, или более эффективное управление битами, которые я перемещаю.

Ответы [ 2 ]

0 голосов
/ 13 ноября 2018

Другая хитрость заключается в том, что иногда возможно перемещать непересекающиеся наборы битовых групп, оставленных на разные величины, используя умножение. Это требует, чтобы частичные продукты не «перекрывались».

Например, шаги влево на 12 и 24 могут быть выполнены как: 

ulong t = (state & 0x0000F000FF000FF0UL) * ((1UL << 12) + (1UL << 24));
r0 |= t & 0x0FF000FF000F0000UL;

Это сокращает 6 операций до 4. Умножение не должно быть медленным, на современном процессоре это занимает 3 цикла, и пока он работает над этим умножением, процессор может идти вперед и работать и на других этапах. В качестве бонуса, на Intel imul будет идти к порту 1, а смены - к портам 0 и 6, поэтому сохранение двух смен с умножением - хорошая сделка, открывая больше места для других смен. Операции AND и OR могут идти на любой порт ALU, и здесь на самом деле это не проблема, но это может помочь задержке разделить цепочку зависимых OR: 

public static ulong Transpose(this ulong state)
{
    ulong r0 = state & 0xF0000F0000F0000FL; //unchanged diagonals

    ulong t = (state & 0x0000F000FF000FF0UL) * ((1UL << 12) + (1UL << 24));
    ulong r1 = (state & 0x0F0000F0000F0000L) >> 12;
    r0 |= (state & 0x00F0000F00000000L) >> 24;
    r1 |= (state & 0x000F000000000000L) >> 36;
    r0 |= (state & 0x000000000000F000L) << 36;
    r1 |= t & 0x0FF000FF000F0000UL;

    return r0 | r1;
}
0 голосов
/ 13 ноября 2018

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

public static ulong Transpose(this ulong state)
        {
            ulong result = state & 0xF0000F0000F0000FL; //unchanged diagonals

            result |= (state & 0x0F0000F0000F0000L) >> 12;
            result |= (state & 0x00F0000F00000000L) >> 24;
            result |= (state & 0x000F000000000000L) >> 36;
            result |= (state & 0x0000F0000F0000F0L) << 12;
            //result |= (state & 0x000000F000000000L) >> 12;
            //result |= (state & 0x0000000F00000000L) >> 24;
            result |= (state & 0x00000000F0000F00L) << 24;
            //result |= (state & 0x000000000F000000L) << 12;
            //result |= (state & 0x00000000000F0000L) >> 12;
            result |= (state & 0x000000000000F000L) << 36;
            //result |= (state & 0x0000000000000F00L) << 24;
            //result |= (state & 0x00000000000000F0L) << 12;

            return result;
        }
...