c# - 转置表示为 ulong 值的 4x4 矩阵(尽可能快)

Question

我一直致力于 2048 的 C# 实现以实现强化学习为目的。

每一步的“滑动”操作，都需要按照特定的规则移动和组合方 block 。这样做涉及对二维值数组的大量转换。

直到最近我还在使用 4x4 字节矩阵:

var field = new byte[4,4];

每个值都是 2 的指数，所以 0=0 , 1=2 , 2=4 , 3=8 ，等等。 2048 block 将由 11 表示。

因为给定图 block 的(实际)最大值是 15(只需要 4 位)，所以可以将这个 4x4 字节数组的内容推送到 ulong 中。值(value)。

事实证明，使用这种表示法某些操作的效率要高得多。例如，我通常必须像这样反转数组:

    //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 进行这种反转快 ~15 倍:

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

请注意十六进制的使用，这非常有用，因为每个字符代表一个方 block 。

我遇到最多麻烦的操作是 Transpose , 它翻转了 x和 y二维数组中值的坐标，如下所示:

    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 倍。但是，我正在寻找一种性能更高的方法，要么利用转置中固有的模式，要么更有效地管理我正在移动的位。

Answer 1

你可以通过组合跳过 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;
        }