使用逻辑填充int [2000] [2000]时出现StackOverflow错误

Question

我需要int[2000][2000]用一些逻辑来填充矩阵.

我填充数组的代码:

// n: (1 to 2000)
for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
        uniMatrix[i][j] = (((calc(i * j * i * j)) & 1) == 0) ? 0 : 1;
    }
}

在这里:i * j * i * j是我对正方形的看法i*j.这calc()是一个用于获取值的方法.然后,我检查返回的值calc()是偶数还是奇数.如果它是偶数,我存储0在矩阵中(i, j),否则我存储1在其中.

我的calc()功能如下:

private static int calc(int n){

    // value of n=calc(1 | 2 | 3) is known
    if(n < 4) return n;

    // if value is present in HashMap, return it (don't calculate again)
    if(map.containsKey(n)) {
        return map.get(n);
    }

    // calculate the answer
    int answer = 1 * calc(n-1) + 2 * calc(n-2) + 3 * calc(n-3);

    // store it in HashMap so that we don't have to recalculate it
    map.put(n, answer);

    return answer;
}

---

现在,如果n是13,它会创建一个[13x13]矩阵.但是,对于n=14,它抛出一个StackOverflowError在map.containsKey(n).我需要能够制作[2000x2000]矩阵.

我知道问题可能是递归.但是,这有什么办法吗？我可以用BitSets做些什么(我不知道怎么做)？

我可以使用其他数据类型矩阵:String[][]或者boolean[][]也可以.我不能在Java SDK/JDK之外使用库.

编辑:它不是"什么是StackOverflowError？"的复制品,我知道它是什么,我知道它们为什么会发生.我需要帮助找到替代方法以防止此错误.

Answer 1

您无法计算calc所需的值范围.在i = j = 216你得到一个整数溢出(结果i * j * i * j变为负数),因此结果calc可能是不正确的.更糟糕的是,你的记忆map也会在规模上爆炸.

好消息是你实际上并不需要计算它.看看这个表达式:

uniMatrix[i][j] = (((calc(i * j * i * j)) & 1) == 0) ? 0 : 1;

您不需要计算的值,您需要知道的是值是偶数还是奇数.你可以用简单的数学知道.calc实施的核心是:

int answer = calc(n - 1) + 2 * calc(n - 2) + 3 * calc(n - 3);

而且我们知道前3个值是1,2,3.实际上它足以知道它们是奇数,偶数,奇数.之后的值可以基于简单的数学计算:

• 将任意数字乘以2将是均匀的
• 将任意数字乘以3将保持原样(如果它是奇数,则奇数,即使它是偶数)
• 添加偶数个奇数将是偶数
• 将偶数添加到任何其他数字将具有另一个数字的均匀性

现在,让我们看看由前面计算的前几个值calc,并验证决定该值是奇数还是偶数的逻辑:

• 0 - > 0:偶数(给定)
• 1 - > 1:奇数(给定)
• 2 - > 2:偶数(给定)
• 3 - > 3:奇数(给定)
• 4 - > 10:偶数,因为奇数+偶数+奇数是偶数
• 5 - > 22:偶数,因为即使+偶数甚至是偶数
• 6 - > 51:奇数,因为奇数+偶数+偶数是奇数
• 7 - > 125:奇数,因为偶数+偶数+奇数是奇数
• 8 - > 293:奇数,因为偶数+偶数+奇数是奇数
• 9 - > 696:偶数,因为奇数+偶数+奇数是偶数
• 10 - > 1657:奇数,因为奇数+偶数+偶数是奇数
• 11 - > 3928:偶数,因为奇数+偶数+奇数是偶数
• 12 - > 9330:偶数,因为即使+偶数甚至是偶数
• 13 - > 22157:奇数,因为奇数+偶数+偶数是奇数
• 14 - > 52601:奇数,因为偶数+偶数+奇数是奇数
• 15 - > 124905:奇数,因为偶数+偶数+奇数是奇数
• 16 - > 296578:偶数,因为奇数+偶数+奇数是偶数

如果你注意到,出现了重复模式:

even odd even even odd odd odd

只有0会中断模式,在这种情况下,该值为0.因此,您的实现可以重写为此,不存在堆栈溢出的风险:

int[] pattern = {0, 1, 0, 0, 1, 1, 1};
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        long x = (long) i * j * i * j;
        if (x < 2) {
            uniMatrix[i][j] = (int) x;
        } else {
            uniMatrix[i][j] = pattern[(int)((x - 2) % pattern.length)];
        }
    }
}

对于0,由于它不遵循该模式,因此需要特殊处理.对于1,x - 2将是负数.由于0和1的正确值本身,if(x <2)分支是处理这些情况的简单方法.