起因
前面有一道猜数字游戏的题，去看性能分析，多数都是5ms。没错，我第一次提交的时候也是5ms。当时我就去看1ms的答案，想找找差距。经过仔细地对比，发现是返回结果时没有使用StringBuilder。乍一看好像可以说得过去，由于字符串的不可变性，拼接字符串实际上返回的是新对象。但是拼接了3次，就要创建3个对象吗？
在jsl8中有这样的描述：Java编译器可以使用StringBuffer或类似技术减少中间String对象。
Thinking in Java中也有提到：
尽管如此，书中建议我们不要在循环中使用字符串拼接，因为会重复创建StringBuilder对象。
题外话，也不是所有的字符串拼接都会使用StringBuilder，如果拼接的都是字符串常量，编译后会进行常量折叠。
那么问题来了，我们没有在循环中进行字符串拼接，为什么会有性能差异？
JMH测试
那我们就使用JMH分别测一测leetCode上提交5ms与1ms的代码。二者之间除了返回时字符串拼接的方式不同，其余代码均相同。
/**
* @date 2024-03-13 11:19
*/
@BenchmarkMode(Mode.AverageTime)
@Warmup(iterations = 3, time = 1)
@Measurement(iterations = 10, time = 1)
@Threads(1)
@Fork(1)
@State(value = Scope.Benchmark)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class Test {
public static void main(String[] args) throws RunnerException {
Options opt = new OptionsBuilder()
.include(Test.class.getSimpleName())
.result("result.json")
.resultFormat(ResultFormatType.JSON).build();
new Runner(opt).run();
}
@Param(value = {"1122", "1807", "1123"})
private String secret;
@Param(value = {"2211", "7810", "0111"})
private String guess;
/** 5ms*/
@Benchmark
public String stringConcatenation() {
int bulls = 0;
int cows = 0;
char[] secretCharArray = secret.toCharArray();
int[] missArray = new int[10];
int[] cowsArray = new int[10];
for (int i = 0; i < secretCharArray.length; i++) {
int guessCharacter = guess.charAt(i) - '0';
int secretCharacter = secretCharArray[i] - '0';
if (guessCharacter == secretCharacter) {
bulls++;
} else {
missArray[secretCharacter] += 1;
cowsArray[guessCharacter] += 1;
}
}
for (int i = 0; i < cowsArray.length; i++) {
if (missArray[i] > 0 && cowsArray[i] > 0) {
cows += Math.min(missArray[i], cowsArray[i]);
}
}
return bulls + "A" + cows + "B";
}
/** 1ms*/
@Benchmark
public String stringBuilder() {
int bulls = 0;
int cows = 0;
char[] secretCharArray = secret.toCharArray();
int[] missArray = new int[10];
int[] cowsArray = new int[10];
for (int i = 0; i < secretCharArray.length; i++) {
int guessCharacter = guess.charAt(i) - '0';
int secretCharacter = secretCharArray[i] - '0';
if (guessCharacter == secretCharacter) {
bulls++;
} else {
missArray[secretCharacter] += 1;
cowsArray[guessCharacter] += 1;
}
}
for (int i = 0; i < cowsArray.length; i++) {
if (missArray[i] > 0 && cowsArray[i] > 0) {
cows += Math.min(missArray[i], cowsArray[i]);
}
}
StringBuilder sb = new StringBuilder();
return sb.append(bulls).append('A').append(cows).append('B').toString();
}
}
性能
测试结果发现性能差异不大。具体是什么原因就不清楚了，可能是leetcode没有进行编译优化或者是根据代码特征直接给的性能分析？
需要考虑 服务器负载、JVM的即时编译行为、测试用例的具体数据分布 等因素。
我发现同一道题，不同时间测试用例可能是不同的，比如代码提交后提示解答错误 73/74，修改了代码过了一段时间提交发现问题没有解决，还提示解答错误 73/74，但是输入的数据是不同的。
后续
我在评论区还发现了一位网友的一次遍历的写法，可以说是很巧妙了。但是，只要使用字符串拼接，性能就是5ms。
class Solution {
public String getHint(String secret, String guess) {
int[] nums = new int[10];
int countA = 0, countB = 0;
for (int i = 0; i < secret.length(); i++) {
if (secret.charAt(i) == guess.charAt(i)) countA++;
else {
if (nums[guess.charAt(i) - '0']-- > 0) countB++;
if (nums[secret.charAt(i) - '0']++ < 0) countB++;
}
}
StringBuilder sb = new StringBuilder();
return sb.append(countA).append('A').append(countB).append('B').toString();
}
}
最后说一下这个一次遍历的思路，如果猜测的数字与secret当前位置的数字不符：
当猜测数字计数却大于0，说明secret之前遇到过，算是位置不正确，应该将bulls加一。不论前面判断结果怎样，猜测数字计数总要减一。
当secret数字计数小于0，说明guess之前猜到过，但是由于当时没有多余的secret数字，所以没有加。这里遇到了，就将bulls加一。不论前面的判断结果，猜测数字计数总要加一。
