单线程环境下Java全局变量res迭代中异常重置原因探究

问题描述 #

在单线程运行的N皇后问题代码中，使用类全局变量res统计解法总数。当执行语句res = res + backTrace(n, row + 1, columns, record1, record2);时，res出现异常重置的情况；但改用临时变量接收backTrace的返回值，再执行res += a后，代码运行完全正常。需要解释单线程环境下出现该现象的原因。

原代码与输出 #

原代码 #

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

class Solution {
    int res = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = in.readLine()) != null) {
            int n = Integer.parseInt(line);
            int ret = new Solution().totalNQueens(n);
            String out = String.valueOf(ret);
            System.out.print(out);
        }
    }

    public int totalNQueens(int n) {
        Set<Integer> columns = new HashSet<Integer>();
        Set<Integer> record1 = new HashSet<Integer>();
        Set<Integer> record2 = new HashSet<Integer>();
        backTrace(n, 0, columns, record1, record2);
        return res;
    }

    private int backTrace(int n, int row, Set<Integer> columns, Set<Integer> record1, Set<Integer> record2) {
        if (n == row) {
            return 1;
        }
        for (int i = 0; i < n; i++) {
            if (columns.contains(i)) {
                continue;
            }
            int check1 = row - i;
            if (record1.contains(check1)) {
                continue;
            }
            int check2 = row + i;
            if (record2.contains(check2)) {
                continue;
            }
            columns.add(i);
            record1.add(check1);
            record2.add(check2);
            System.out.println("res start:" + res);
            res = res + backTrace(n, row + 1, columns, record1, record2);
            System.out.println("res end:" + res);
            columns.remove(i);
            record1.remove(check1);
            record2.remove(check2);
        }
        return 0;
    }
}

原代码输出 #

res start:0
res start:0
res end:0
res start:0
res start:0
res end:0
res end:0
res end:0
res start:0
res start:0
res start:0
res start:0
res end:1
res end:0
res end:0
res end:0
res start:0
res start:0
res start:0
res start:0

修改后代码与输出 #

修改后代码 #

package com.nbp.cdncp.vpe.api.controller;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

class Solution {
    int res = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = in.readLine()) != null) {
            int n = Integer.parseInt(line);
            int ret = new Solution().totalNQueens(n);
            String out = String.valueOf(ret);
            System.out.print(out);
        }
    }

    public int totalNQueens(int n) {
        Set<Integer> columns = new HashSet<Integer>();
        Set<Integer> record1 = new HashSet<Integer>();
        Set<Integer> record2 = new HashSet<Integer>();
        backTrace(n, 0, columns, record1, record2);
        return res;
    }

    private int backTrace(int n, int row, Set<Integer> columns, Set<Integer> record1, Set<Integer> record2) {
        if (n == row) {
            return 1;
        }
        for (int i = 0; i < n; i++) {
            if (columns.contains(i)) {
                continue;
            }
            int check1 = row - i;
            if (record1.contains(check1)) {
                continue;
            }
            int check2 = row + i;
            if (record2.contains(check2)) {
                continue;
            }
            columns.add(i);
            record1.add(check1);
            record2.add(check2);
            System.out.println("res start:" + res);
            var a = backTrace(n, row + 1, columns, record1, record2);
            res += a;
            System.out.println("res end:" + res);
            columns.remove(i);
            record1.remove(check1);
            record2.remove(check2);
        }
        return 0;
    }
}

修改后代码输出 #

res start:0
res start:0
res end:0
res start:0
res start:0
res end:0
res end:0
res end:0
res start:0
res start:0
res start:0
res start:0
res end:1
res end:1
res end:1
res end:1
res start:1
res start:1
res start:1
res start:1
res end:2
res end:2
res end:2
res end:2
res start:2
res start:2
res start:2
res end:2
res end:2
res start:2
res end:2
res end:2
2

原因分析 #

核心问题在于表达式的执行顺序：

1. 对于res = res + backTrace(...)：
   JVM会先读取当前res的数值并暂存，然后调用backTrace方法。但backTrace是递归方法，在递归过程中会多次修改全局变量res的值。当递归返回后，JVM会用之前暂存的旧res值加上backTrace的返回值，重新赋值给res——这就直接覆盖了递归过程中对res的所有修改，表现为res被"重置"。
   比如原输出中，内层递归将res加到1，但外层执行res = 0 + 0（外层调用backTrace前res是0，backTrace返回0），导致res被重置为0。

2. 对于var a = backTrace(...); res += a：
   代码会先执行backTrace方法，此时递归过程中对res的修改已经全部生效；之后再将backTrace的返回值加到当前最新的res上，是正确的累加逻辑，不会覆盖之前的修改，因此能得到正确的统计结果。

内容的提问来源于stack exchange，提问作者Harutya