为什么在这个问题上，4次通过解决方案的性能比一次通过解决方案更快？

Question

问题指出：给定方向（Up，Down，Left，Right）从原点开始，最终结果会是原点吗？String moves

一个明显的解决方案是简单地设置两个变量（用于跟踪垂直和水平运动），并查看它们在所有方向操作后是否变为零：

public boolean judgeCircle(String moves) {

    char[] chars = moves.toCharArray();

    int vertical = 0;

    int horizontal = 0;

    for(int i = 0; i < chars.length; i++){

        char c = chars[i];

        switch(c){

            case 'U':

                vertical ++;

                break;

            case 'D':

                vertical --;

                break;

            case 'L': 

                horizontal --;

                break;

            case 'R': 

                horizontal ++;

                break;

        }

    }

    return (vertical == 0) && (horizontal == 0);

}

该算法在大约8ms内为Leetcode的测试用例找到正确的解决方案。

但是，扫描所有操作 4 次的解决方案仅在大约 1 毫秒内找到解决方案：

public boolean judgeCircle(String moves) {

 int x = charCount(moves, 'R') - charCount(moves, 'L');

    int y = charCount(moves, 'U') - charCount(moves, 'D');

    return x == 0 && y == 0; 

}

private int charCount(String moves, char c) {

    int count = 0;

    for(int i=0; i<moves.length(); i++) {

        if(moves.charAt(i) == c) {

            count++; 

        }

    }

    return count;   

}

我将这两种解决方案重复了大约10次，结果总是一致的。但是，为什么扫描4倍的算法比只通过一次找到答案的算法运行得更快（快4倍！）呢？moves

Answer 1

我调整了您的示例，以便所有算法都适用于相同的数据。我还在实现中添加了另一个变体。if@State(Scope.Thread)public class ForVsSwitch {&nbsp; &nbsp; private static final int MOVES_LENGTH = 1024;&nbsp; &nbsp; private static final char[] COMMANDS = { 'U', 'D', 'L', 'R'};&nbsp; &nbsp; private char[] moves;&nbsp; &nbsp; @Setup&nbsp; &nbsp; public void prepare(){&nbsp; &nbsp; &nbsp; &nbsp; Random random = new Random();&nbsp; &nbsp; &nbsp; &nbsp; moves = new char[MOVES_LENGTH];&nbsp; &nbsp; &nbsp; &nbsp; for(int i=0; i< MOVES_LENGTH; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; moves[i] = COMMANDS[random.nextInt(4)];&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; @Benchmark&nbsp; &nbsp; @BenchmarkMode(Mode.SampleTime)&nbsp; &nbsp; @OutputTimeUnit(TimeUnit.MILLISECONDS)&nbsp; &nbsp; @Warmup(iterations = 3)&nbsp; &nbsp; @Measurement(iterations = 5)&nbsp; &nbsp; public void withSwitch() {&nbsp; &nbsp; &nbsp; &nbsp; judgeCircleWithSwitch(moves);&nbsp; &nbsp; }&nbsp; &nbsp; @Benchmark&nbsp; &nbsp; @BenchmarkMode(Mode.SampleTime)&nbsp; &nbsp; @OutputTimeUnit(TimeUnit.MILLISECONDS)&nbsp; &nbsp; @Warmup(iterations = 3)&nbsp; &nbsp; @Measurement(iterations = 5)&nbsp; &nbsp; public void withFor() {&nbsp; &nbsp; &nbsp; &nbsp; judgeCircleWithFor(moves);&nbsp; &nbsp; }&nbsp; &nbsp; @Benchmark&nbsp; &nbsp; @BenchmarkMode(Mode.SampleTime)&nbsp; &nbsp; @OutputTimeUnit(TimeUnit.MILLISECONDS)&nbsp; &nbsp; @Warmup(iterations = 3)&nbsp; &nbsp; @Measurement(iterations = 5)&nbsp; &nbsp; public void withIf() {&nbsp; &nbsp; &nbsp; &nbsp; judgeCircleWithIf(moves);&nbsp; &nbsp; }&nbsp; &nbsp; private boolean judgeCircleWithSwitch(char[] moves) {&nbsp; &nbsp; &nbsp; &nbsp; int vertical = 0;&nbsp; &nbsp; &nbsp; &nbsp; int horizontal = 0;&nbsp; &nbsp; &nbsp; &nbsp; for(int i = 0; i < moves.length; i++){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; char c = moves[i];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; switch(c){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; case 'U':&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; vertical ++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; case 'D':&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; vertical --;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; case 'L':&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; horizontal --;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; case 'R':&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; horizontal ++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return (vertical == 0) && (horizontal == 0);&nbsp; &nbsp; }&nbsp; &nbsp; private boolean judgeCircleWithIf(char[] moves) {&nbsp; &nbsp; &nbsp; &nbsp; int vertical = 0;&nbsp; &nbsp; &nbsp; &nbsp; int horizontal = 0;&nbsp; &nbsp; &nbsp; &nbsp; for(int i = 0; i < moves.length; i++){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; char c = moves[i];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(c == 'U') {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; vertical++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } else if(c == 'D') {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; vertical--;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } else if(c == 'L') {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; horizontal--;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } else if(c == 'R') {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; horizontal ++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return (vertical == 0) && (horizontal == 0);&nbsp; &nbsp; }&nbsp; &nbsp; private boolean judgeCircleWithFor(char[] moves) {&nbsp; &nbsp; &nbsp; &nbsp; int x = charCount(moves, 'R') - charCount(moves, 'L');&nbsp; &nbsp; &nbsp; &nbsp; int y = charCount(moves, 'U') - charCount(moves, 'D');&nbsp; &nbsp; &nbsp; &nbsp; return x == 0 && y == 0;&nbsp; &nbsp; }&nbsp; &nbsp; private int charCount(char[] moves, char c) {&nbsp; &nbsp; &nbsp; &nbsp; int count = 0;&nbsp; &nbsp; &nbsp; &nbsp; for(int i=0; i<moves.length; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(moves[i] == c) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return count;&nbsp; &nbsp; }}如果我正确阅读结果，99.9%的执行速度比27ms到29ms快，对吧？算法之间似乎没有区别。Benchmark&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Mode&nbsp; &nbsp; &nbsp; Cnt&nbsp; &nbsp;Score&nbsp; &nbsp; Error&nbsp; UnitsForVsSwitch.withFor&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sample&nbsp; 5680658&nbsp; &nbsp;0,003 ±&nbsp; 0,001&nbsp; ms/opForVsSwitch.withFor:withFor·p0.00&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sample&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0,002&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ms/opForVsSwitch.withFor:withFor·p0.50&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sample&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0,003&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ms/opForVsSwitch.withFor:withFor·p0.90&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sample&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0,003&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ms/opForVsSwitch.withFor:withFor·p0.95&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sample&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0,004&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ms/opForVsSwitch.withFor:withFor·p0.99&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sample&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0,019&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ms/opForVsSwitch.withFor:withFor·p0.999&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;sample&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0,029&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ms/opForVsSwitch.withFor:withFor·p0.9999&nbsp; &nbsp; &nbsp; &nbsp; sample&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0,075&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ms/opForVsSwitch.withFor:withFor·p1.00&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sample&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 2,912&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ms/opForVsSwitch.withIf&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;sample&nbsp; 8903669&nbsp; &nbsp;0,002 ±&nbsp; 0,001&nbsp; ms/opForVsSwitch.withIf:withIf·p0.00&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sample&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0,001&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ms/opForVsSwitch.withIf:withIf·p0.50&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sample&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0,002&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ms/opForVsSwitch.withIf:withIf·p0.90&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sample&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0,002&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ms/opForVsSwitch.withIf:withIf·p0.95&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sample&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0,003&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ms/opForVsSwitch.withIf:withIf·p0.99&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sample&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0,005&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ms/opForVsSwitch.withIf:withIf·p0.999&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;sample&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0,027&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ms/opForVsSwitch.withIf:withIf·p0.9999&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sample&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0,051&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ms/opForVsSwitch.withIf:withIf·p1.00&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sample&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 5,202&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ms/opForVsSwitch.withSwitch&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;sample&nbsp; 8225249&nbsp; &nbsp;0,002 ±&nbsp; 0,001&nbsp; ms/opForVsSwitch.withSwitch:withSwitch·p0.00&nbsp; &nbsp; sample&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0,001&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ms/opForVsSwitch.withSwitch:withSwitch·p0.50&nbsp; &nbsp; sample&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0,002&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ms/opForVsSwitch.withSwitch:withSwitch·p0.90&nbsp; &nbsp; sample&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0,002&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ms/opForVsSwitch.withSwitch:withSwitch·p0.95&nbsp; &nbsp; sample&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0,003&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ms/opForVsSwitch.withSwitch:withSwitch·p0.99&nbsp; &nbsp; sample&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0,018&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ms/opForVsSwitch.withSwitch:withSwitch·p0.999&nbsp; &nbsp;sample&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0,027&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ms/opForVsSwitch.withSwitch:withSwitch·p0.9999&nbsp; sample&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 0,071&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ms/opForVsSwitch.withSwitch:withSwitch·p1.00&nbsp; &nbsp; sample&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;22,610&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ms/op编辑：我无法确认你的陈述是否成立。我简化了这个例子。我使用静态列表作为两种算法的输入。我不做热身，只测量一次执行。正如预期的那样，4次通过比1次通过更昂贵。我真的不知道你的网站在衡量什么。@State(Scope.Thread)public class ForVsSwitch {&nbsp; &nbsp; private char[] moves = {'U', 'D', 'L', ...};&nbsp; &nbsp; @Benchmark&nbsp; &nbsp; @BenchmarkMode(Mode.SingleShotTime)&nbsp; &nbsp; @OutputTimeUnit(TimeUnit.MILLISECONDS)&nbsp; &nbsp; @Warmup(iterations = 0)&nbsp; &nbsp; @Measurement(iterations = 1, batchSize = 1)&nbsp; &nbsp; @Fork(value = 1, warmups = 0)&nbsp; &nbsp; public void withSwitch() {&nbsp; &nbsp; &nbsp; &nbsp; judgeCircleWithSwitch();&nbsp; &nbsp; }&nbsp; &nbsp; @Benchmark&nbsp; &nbsp; @BenchmarkMode(Mode.SingleShotTime)&nbsp; &nbsp; @OutputTimeUnit(TimeUnit.MILLISECONDS)&nbsp; &nbsp; @Warmup(iterations = 0)&nbsp; &nbsp; @Measurement(iterations = 1, batchSize = 1)&nbsp; &nbsp; @Fork(value = 1, warmups = 0)&nbsp; &nbsp; public void withFor() {&nbsp; &nbsp; &nbsp; &nbsp; judgeCircleWithFor();&nbsp; &nbsp; }&nbsp; &nbsp; private boolean judgeCircleWithSwitch() {&nbsp; &nbsp; &nbsp; &nbsp; int vertical = 0;&nbsp; &nbsp; &nbsp; &nbsp; int horizontal = 0;&nbsp; &nbsp; &nbsp; &nbsp; for(int i = 0; i < moves.length; i++){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; char c = moves[i];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; switch(c){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; case 'U':&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; vertical ++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; case 'D':&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; vertical --;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; case 'L':&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; horizontal --;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; case 'R':&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; horizontal ++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return (vertical == 0) && (horizontal == 0);&nbsp; &nbsp; }&nbsp; &nbsp; private boolean judgeCircleWithFor() {&nbsp; &nbsp; &nbsp; &nbsp; int x = charCount(moves, 'R') - charCount(moves, 'L');&nbsp; &nbsp; &nbsp; &nbsp; int y = charCount(moves, 'U') - charCount(moves, 'D');&nbsp; &nbsp; &nbsp; &nbsp; return x == 0 && y == 0;&nbsp; &nbsp; }&nbsp; &nbsp; private int charCount(char[] moves, char c) {&nbsp; &nbsp; &nbsp; &nbsp; int count = 0;&nbsp; &nbsp; &nbsp; &nbsp; for(int i=0; i<moves.length; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(moves[i] == c) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return count;&nbsp; &nbsp; }}for 环路比交换机更昂贵。但正如其他评论中指出的那样，运行它一次并不是可靠的性能分析。Benchmark&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Mode&nbsp; Cnt&nbsp; Score&nbsp; &nbsp;Error&nbsp; UnitsForVsSwitch.withFor&nbsp; &nbsp; &nbsp; &nbsp;ss&nbsp; &nbsp; &nbsp; &nbsp;0,577&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ms/opForVsSwitch.withSwitch&nbsp; &nbsp; ss&nbsp; &nbsp; &nbsp; &nbsp;0,241&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ms/op