java - 矩阵计算太慢

Question

我正在开发名为 Lights Out 的游戏.因此，为了解决这个问题，我必须在模块 2 中计算 AX = B 的答案。因此，出于这个原因，我选择了 jscience 。图书馆。在这个游戏中，A 的大小是 25x25 矩阵，X 和 B 都是 25x1 矩阵。我写了如下代码:

AllLightOut.java类:

public class AllLightOut {
    public static final int SIZE = 5;

    public static double[] Action(int i, int j) {
        double[] change = new double[SIZE * SIZE];
        int count = 0;

        for (double[] d : Switch(new double[SIZE][SIZE], i, j))
            for (double e : d)
                change[count++] = e;

        return change;
    }

    public static double[][] MatrixA() {
        double[][] mat = new double[SIZE * SIZE][SIZE * SIZE];

        for (int i = 0; i < SIZE; i++)
            for (int j = 0; j < SIZE; j++)
                mat[i * SIZE + j] = Action(i, j);

        return mat;
    }

    public static SparseVector<ModuloInteger> ArrayToDenseVectorModule2(
            double[] array) {
        List<ModuloInteger> list = new ArrayList<ModuloInteger>();

        for (int i = 0; i < array.length; i++) {
            if (array[i] == 0)
                list.add(ModuloInteger.ZERO);
            else
                list.add(ModuloInteger.ONE);
        }

        return SparseVector.valueOf(DenseVector.valueOf(list),
                ModuloInteger.ZERO);
    }

    public static SparseMatrix<ModuloInteger> MatrixAModule2() {
        double[][] mat = MatrixA();
        List<DenseVector<ModuloInteger>> list = new ArrayList<DenseVector<ModuloInteger>>();

        for (int i = 0; i < mat.length; i++) {
            List<ModuloInteger> l = new ArrayList<ModuloInteger>();
            for (int j = 0; j < mat[i].length; j++) {
                if (mat[i][j] == 0)
                    l.add(ModuloInteger.ZERO);
                else
                    l.add(ModuloInteger.ONE);
            }

            list.add(DenseVector.valueOf(l));
        }

        return SparseMatrix.valueOf(DenseMatrix.valueOf(list),
                ModuloInteger.ZERO);
    }

    public static double[][] Switch(double[][] action, int i, int j) {
        action[i][j] = action[i][j] == 1 ? 0 : 1;

        if (i > 0)
            action[i - 1][j] = action[i - 1][j] == 1 ? 0 : 1;

        if (i < action.length - 1)
            action[i + 1][j] = action[i + 1][j] == 1 ? 0 : 1;

        if (j > 0)
            action[i][j - 1] = action[i][j - 1] == 1 ? 0 : 1;

        if (j < action.length - 1)
            action[i][j + 1] = action[i][j + 1] == 1 ? 0 : 1;

        return action;
    }
}

主类如下:

public class Main {
    public static void main(String[] args) {
        double[] bVec = new double[] { 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0,
                1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0 };

        SparseMatrix<ModuloInteger> matA = AllLightOut.MatrixAModule2();
        SparseVector<ModuloInteger> matB = AllLightOut
                .ArrayToDenseVectorModule2(bVec);

        ModuloInteger.setModulus(LargeInteger.valueOf(2));
    Vector<ModuloInteger> matX = matA.solve(matB);

        System.out.println(matX);
    }
}

我运行这个程序大约 30 分钟，但没有结果。我的代码是否包含 fatal error 或错误？为什么需要这么长时间？

感谢您的关注:)

编辑这条线发生减速 Matrix<ModuloInteger> matX = matA.inverse(); .请注意 JScience benchmark result ，这个库的速度非常快，但我不知道为什么我的程序运行得太慢了!

编辑2请注意，当我尝试 SIZE = 3 ，我得到了真正的答案。例如:马塔:

{{1, 1, 0, 1, 0, 0, 0, 0, 0},
{1, 1, 1, 0, 1, 0, 0, 0, 0},
{0, 1, 1, 0, 0, 1, 0, 0, 0},
{1, 0, 0, 1, 1, 0, 1, 0, 0},
{0, 1, 0, 1, 1, 1, 0, 1, 0},
{0, 0, 1, 0, 1, 1, 0, 0, 1},
{0, 0, 0, 1, 0, 0, 1, 1, 0},
{0, 0, 0, 0, 1, 0, 1, 1, 1},
{0, 0, 0, 0, 0, 1, 0, 1, 1}}

垫子:

{1, 1, 1, 1, 1, 1, 1, 0, 0}

MatC:

{0, 0, 1, 1, 0, 0, 0, 0, 0}

但是当我尝试 SIZE = 5 , 发生减速。

Answer 1

The slowdown happening in this line Matrix<ModuloInteger> matX = matA.inverse();

那是因为系数矩阵 matA对于 SIZE == 5 不可逆(或 4、9、11、14、16、...？)。

我有点惊讶库没有检测到并抛出异常。如果库试图反转 solve() 中的矩阵，那会产生同样的后果。

某些尺寸的系数矩阵的奇异性导致并非这些尺寸的所有谜题都是可解的，而其他尺寸的谜题有多个解。

由于我们计算模 2，我们可以使用位或 boolean s 来模拟我们的状态/切换，使用 XOR添加和&乘法。我已经使用高斯消去法编写了一个简单的求解器，也许它对你有帮助(我没有花太多时间考虑设计，所以它并不漂亮):

public class Lights{
    private static final int SIZE = 5;

    private static boolean[] toggle(int i, int j) {
        boolean[] action = new boolean[SIZE*SIZE];
        int idx = i*SIZE+j;
        action[idx] = true;
        if (j > 0)      action[idx-1] = true;
        if (j < SIZE-1) action[idx+1] = true;
        if (i > 0)      action[idx-SIZE] = true;
        if (i < SIZE-1) action[idx+SIZE] = true;
        return action;
    }
    private static boolean[][] matrixA() {
        boolean[][] mat = new boolean[SIZE*SIZE][];
        for(int i = 0; i < SIZE; ++i) {
            for(int j = 0; j < SIZE; ++j) {
                mat[i*SIZE+j] = toggle(i,j);
            }
        }
        return mat;
    }
    private static void rotateR(boolean[] a, int r) {
        r %= a.length;
        if (r < 0) r += a.length;
        if (r == 0) return;
        boolean[] tmp = new boolean[r];
        for(int i = 0; i < r; ++i) {
            tmp[i] = a[i];
        }
        for(int i = 0; i < a.length - r; ++i) {
            a[i] = a[i+r];
        }
        for(int i = 0; i < r; ++i) {
            a[i + a.length - r] = tmp[i];
        }
    }
    private static void rotateR(boolean[][] a, int r) {
        r %= a.length;
        if (r < 0) r += a.length;
        if (r == 0) return;
        boolean[][] tmp = new boolean[r][];
        for(int i = 0; i < r; ++i) {
            tmp[i] = a[i];
        }
        for(int i = 0; i < a.length - r; ++i) {
            a[i] = a[i+r];
        }
        for(int i = 0; i < r; ++i) {
            a[i + a.length - r] = tmp[i];
        }
    }
    private static int count(boolean[] a) {
        int c = 0;
        for(int i = 0; i < a.length; ++i) {
            if (a[i]) ++c;
        }
        return c;
    }
    private static void swapBits(boolean[] a, int i, int j) {
        boolean tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    private static void addBit(boolean[] a, int i, int j) {
        a[j] ^= a[i];
    }
    private static void swapRows(boolean[][] a, int i, int j) {
        boolean[] tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    private static void xorb(boolean[] a, boolean[] b) {
        for(int i = 0; i < a.length; ++i) {
            a[i] ^= b[i];
        }
    }
    private static boolean[] boolBits(int bits, long param) {
        boolean[] bitArr = new boolean[bits];
        for(int i = 0; i < bits; ++i) {
            if (((param >> i) & 1L) != 0) {
                bitArr[i] = true;
            }
        }
        return bitArr;
    }
    private static boolean[] solve(boolean[][] m, boolean[] b) {
        // Move first SIZE rows to bottom, so that on the diagonal
        // above the lowest SIZE rows, there are unit matrices
        rotateR(m, SIZE);
        // modify right hand side accordingly
        rotateR(b,SIZE);
        // clean first SIZE*(SIZE-1) columns
        for(int i = 0; i < SIZE*(SIZE-1); ++i) {
            for(int k = 0; k < SIZE*SIZE; ++k) {
                if (k == i) continue;
                if (m[k][i]) {
                    xorb(m[k], m[i]);
                    b[k] ^= b[i];
                }
            }
        }
        // Now we have a block matrix
        /*
         * E 0 0 ... 0 X
         * 0 E 0 ... 0 X
         * 0 0 E ... 0 X
         * ...
         * 0 0 ... E 0 X
         * 0 0 ... 0 E X
         * 0 0 ... 0 0 Y
         *
         */
        // Bring Y to row-echelon form
        int i = SIZE*(SIZE-1), j, k, mi = i;
        while(mi < SIZE*SIZE){
            // Try to find a row with mi-th bit set
            for(j = i; j < SIZE*SIZE; ++j) {
                if (m[j][mi]) break;
            }
            if (j < SIZE*SIZE) {
                // Found one
                if (j > i) {
                    swapRows(m,i,j);
                    swapBits(b,i,j);
                }
                for(k = 0; k < SIZE*SIZE; ++k) {
                    if (k == i) continue;
                    if (m[k][mi]) {
                        xorb(m[k], m[i]);
                        b[k] ^= b[i];
                    }
                }
                // cleaned up column, good row, next
                ++i;
            }
            // Look at next column
            ++mi;
        }
        printMat(m,b);
        boolean[] best = b;
        if (i < SIZE*SIZE) {
            // We have zero-rows in the matrix,
            // check whether the puzzle is solvable at all,
            // i.e. all corresponding bits in the rhs are 0
            for(j = i; j < SIZE*SIZE; ++j) {
                if (b[j]) {
                    System.out.println("Puzzle not solvable, some lights must remain lit.");
                    break;
//                     throw new IllegalArgumentException("Puzzle is not solvable!");
                }
            }
            // Pretending it were solvable if not
            if (j < SIZE*SIZE) {
                System.out.println("Pretending the puzzle were solvable...");
                for(; j < SIZE*SIZE; ++j) {
                    b[j] = false;
                }
            }
            // Okay, puzzle is solvable, but there are several solutions
            // Let's try to find the one with the least toggles.

            // We have the canonical solution with last bits all zero
            int toggles = count(b);
            System.out.println(toggles + " toggles in canonical solution");
            int freeBits = SIZE*SIZE - i;
            long max = 1L << freeBits;
            System.out.println(freeBits + " free bits");
            // Check all combinations of free bits whether they produce
            // something better
            for(long param = 1; param < max; ++param) {
                boolean[] base = boolBits(freeBits,param);
                boolean[] c = new boolean[SIZE*SIZE];
                for(k = 0; k < freeBits; ++k) {
                    c[i+k] = base[k];
                }
                for(k = 0; k < i; ++k) {
                    for(j = 0; j < freeBits; ++j) {
                        c[k] ^= base[j] && m[k][j+i];
                    }
                }
                xorb(c,b);
                int t = count(c);
                if (t < toggles) {
                    System.out.printf("Found new best for param %x, %d toggles\n",param,t);
                    printMat(m,c,b);
                    toggles = t;
                    best = c;
                } else {
                    System.out.printf("%d toggles for parameter %x\n", t, param);
                }
            }
        }
        return best;
    }
    private static boolean[] parseLights(int[] lights) {
        int lim = lights.length;
        if (SIZE*SIZE < lim) lim = SIZE*SIZE;
        boolean[] b = new boolean[SIZE*SIZE];
        for(int i = 0; i < lim; ++i) {
            b[i] = (lights[i] != 0);
        }
        return b;
    }
    private static void printToggles(boolean[] s) {
        for(int i = 0; i < s.length; ++i) {
            if (s[i]) {
                System.out.print("(" + (i/SIZE + 1) + ", " + (i%SIZE + 1) + "); ");
            }
        }
        System.out.println();
    }
    private static void printMat(boolean[][] a, boolean[] rhs) {
        for(int i = 0; i < SIZE*SIZE; ++i) {
            for(int j = 0; j < SIZE*SIZE; ++j) {
                System.out.print((a[i][j] ? "1 " : "0 "));
            }
            System.out.println("| " + (rhs[i] ? "1" : "0"));
        }
    }
    private static void printMat(boolean[][] a, boolean[] sol, boolean[] rhs) {
        for(int i = 0; i < SIZE*SIZE; ++i) {
            for(int j = 0; j < SIZE*SIZE; ++j) {
                System.out.print((a[i][j] ? "1 " : "0 "));
            }
            System.out.println("| " + (sol[i] ? "1" : "0") + " | " + (rhs[i] ? "1" : "0"));
        }
    }
    private static void printGrid(boolean[] g) {
        for(int i = 0; i < SIZE; ++i) {
            for(int j = 0; j < SIZE; ++j) {
                System.out.print(g[i*SIZE+j] ? "1" : "0");
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        int[] initialLights = new int[] { 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0,
                1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0 };
        boolean[] b = parseLights(initialLights);
        boolean[] b2 = b.clone();
        boolean[][] coefficients = matrixA();
        boolean[] toggles = solve(coefficients, b);
        printGrid(b2);
        System.out.println("--------");
        boolean[][] check = matrixA();
        boolean[] verify = new boolean[SIZE*SIZE];
        for(int i = 0; i < SIZE*SIZE; ++i) {
            if (toggles[i]) {
                xorb(verify, check[i]);
            }
        }
        printGrid(verify);
        xorb(b2,verify);
        if (count(b2) > 0) {
            System.out.println("Aww, shuck, screwed up!");
            printGrid(b2);
        }
        printToggles(toggles);
    }
}