用逻辑填充 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，它会在 map.containsKey(n) 处抛出一个 WhosebugError。我需要能够制作 [2000x2000] 矩阵。

我知道问题可能出在递归上。但是，有办法解决这个问题吗？我可以用 BitSets 做点什么吗（我不知道怎么做）？

我也可以使用其他数据类型矩阵：String[][] 或 boolean[][]。我无法在 Java SDK/JDK.

之外使用图书馆

编辑：它不是"What is WhosebugError?"的副本，我知道它是什么，我知道它们为什么会出现。我需要帮助找到替代方法来防止此错误。

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 ：偶数，因为 even + even + even 是偶数
6 -> 51 ：奇数，因为奇数+偶数+偶数是奇数
7 -> 125 ：奇数，因为偶数 + 偶数 + 奇数是奇数
8 -> 293 ：奇数，因为偶数+偶数+奇数是奇数
9 -> 696 ：偶数，因为奇数+偶数+奇数是偶数
10 -> 1657 ：奇数，因为奇数+偶数+偶数是奇数
11 -> 3928 : 偶数，因为奇数 + 偶数 + 奇数是偶数
12 -> 9330 ：偶数，因为 even + even + even 是偶数
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) 分支是处理这些情况的简单方法。

Answer 2

我们只对结果模 2 感兴趣，因此所有计算都可以模 2 完成。然后递归减少到（为计算模 2 编写 calc'）：

calc'(1) = 1
calc'(2) = 0
calc'(3) = 1
calc'(n) = (calc'(n-1) + calc'(n-3)) % 2

因此我们看到下一个值仅取决于固定距离内的两个先前值，并且由于每个值的数字范围是有限的（只能是 0 或 1），我们知道序列最终必须是周期性的。一点实验表明周期是 7.

所以值模 2 是（对于 n >= 1）：

calc'(n) = 
     1 if n%7 = 1,
     0 if n%7 = 2,
     1 if n%7 = 3,
     0 if n%7 = 4,
     0 if n%7 = 5,
     1 if n%7 = 6,
     1 if n%7 = 0.

用逻辑填充 int[2000][2000] 时发生 StackOverflow 错误

StackOverflow error while filling int[2000][2000] with a logic

java

stack-overflow

recursion

matrix