問題指出：給定方向（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
1 回答
元芳怎么了
TA貢獻1798條經驗 獲得超7個贊
我調整了您的示例，以便所有算法都適用于相同的數據。我還在實現中添加了另一個變體。if
@State(Scope.Thread)
public class ForVsSwitch {
private static final int MOVES_LENGTH = 1024;
private static final char[] COMMANDS = { 'U', 'D', 'L', 'R'};
private char[] moves;
@Setup
public void prepare(){
Random random = new Random();
moves = new char[MOVES_LENGTH];
for(int i=0; i< MOVES_LENGTH; i++) {
moves[i] = COMMANDS[random.nextInt(4)];
}
}
@Benchmark
@BenchmarkMode(Mode.SampleTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Warmup(iterations = 3)
@Measurement(iterations = 5)
public void withSwitch() {
judgeCircleWithSwitch(moves);
}
@Benchmark
@BenchmarkMode(Mode.SampleTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Warmup(iterations = 3)
@Measurement(iterations = 5)
public void withFor() {
judgeCircleWithFor(moves);
}
@Benchmark
@BenchmarkMode(Mode.SampleTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Warmup(iterations = 3)
@Measurement(iterations = 5)
public void withIf() {
judgeCircleWithIf(moves);
}
private boolean judgeCircleWithSwitch(char[] moves) {
int vertical = 0;
int horizontal = 0;
for(int i = 0; i < moves.length; i++){
char c = moves[i];
switch(c){
case 'U':
vertical ++;
break;
case 'D':
vertical --;
break;
case 'L':
horizontal --;
break;
case 'R':
horizontal ++;
break;
}
}
return (vertical == 0) && (horizontal == 0);
}
private boolean judgeCircleWithIf(char[] moves) {
int vertical = 0;
int horizontal = 0;
for(int i = 0; i < moves.length; i++){
char c = moves[i];
if(c == 'U') {
vertical++;
} else if(c == 'D') {
vertical--;
} else if(c == 'L') {
horizontal--;
} else if(c == 'R') {
horizontal ++;
}
}
return (vertical == 0) && (horizontal == 0);
}
private boolean judgeCircleWithFor(char[] 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(char[] moves, char c) {
int count = 0;
for(int i=0; i<moves.length; i++) {
if(moves[i] == c) {
count++;
}
}
return count;
}
}
如果我正確閱讀結果，99.9%的執行速度比27ms到29ms快，對吧？算法之間似乎沒有區別。
Benchmark Mode Cnt Score Error Units
ForVsSwitch.withFor sample 5680658 0,003 ± 0,001 ms/op
ForVsSwitch.withFor:withFor·p0.00 sample 0,002 ms/op
ForVsSwitch.withFor:withFor·p0.50 sample 0,003 ms/op
ForVsSwitch.withFor:withFor·p0.90 sample 0,003 ms/op
ForVsSwitch.withFor:withFor·p0.95 sample 0,004 ms/op
ForVsSwitch.withFor:withFor·p0.99 sample 0,019 ms/op
ForVsSwitch.withFor:withFor·p0.999 sample 0,029 ms/op
ForVsSwitch.withFor:withFor·p0.9999 sample 0,075 ms/op
ForVsSwitch.withFor:withFor·p1.00 sample 2,912 ms/op
ForVsSwitch.withIf sample 8903669 0,002 ± 0,001 ms/op
ForVsSwitch.withIf:withIf·p0.00 sample 0,001 ms/op
ForVsSwitch.withIf:withIf·p0.50 sample 0,002 ms/op
ForVsSwitch.withIf:withIf·p0.90 sample 0,002 ms/op
ForVsSwitch.withIf:withIf·p0.95 sample 0,003 ms/op
ForVsSwitch.withIf:withIf·p0.99 sample 0,005 ms/op
ForVsSwitch.withIf:withIf·p0.999 sample 0,027 ms/op
ForVsSwitch.withIf:withIf·p0.9999 sample 0,051 ms/op
ForVsSwitch.withIf:withIf·p1.00 sample 5,202 ms/op
ForVsSwitch.withSwitch sample 8225249 0,002 ± 0,001 ms/op
ForVsSwitch.withSwitch:withSwitch·p0.00 sample 0,001 ms/op
ForVsSwitch.withSwitch:withSwitch·p0.50 sample 0,002 ms/op
ForVsSwitch.withSwitch:withSwitch·p0.90 sample 0,002 ms/op
ForVsSwitch.withSwitch:withSwitch·p0.95 sample 0,003 ms/op
ForVsSwitch.withSwitch:withSwitch·p0.99 sample 0,018 ms/op
ForVsSwitch.withSwitch:withSwitch·p0.999 sample 0,027 ms/op
ForVsSwitch.withSwitch:withSwitch·p0.9999 sample 0,071 ms/op
ForVsSwitch.withSwitch:withSwitch·p1.00 sample 22,610 ms/op
編輯：
我無法確認你的陳述是否成立。我簡化了這個例子。我使用靜態列表作為兩種算法的輸入。我不做熱身，只測量一次執行。正如預期的那樣，4次通過比1次通過更昂貴。我真的不知道你的網站在衡量什么。
@State(Scope.Thread)
public class ForVsSwitch {
private char[] moves = {'U', 'D', 'L', ...};
@Benchmark
@BenchmarkMode(Mode.SingleShotTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Warmup(iterations = 0)
@Measurement(iterations = 1, batchSize = 1)
@Fork(value = 1, warmups = 0)
public void withSwitch() {
judgeCircleWithSwitch();
}
@Benchmark
@BenchmarkMode(Mode.SingleShotTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Warmup(iterations = 0)
@Measurement(iterations = 1, batchSize = 1)
@Fork(value = 1, warmups = 0)
public void withFor() {
judgeCircleWithFor();
}
private boolean judgeCircleWithSwitch() {
int vertical = 0;
int horizontal = 0;
for(int i = 0; i < moves.length; i++){
char c = moves[i];
switch(c){
case 'U':
vertical ++;
break;
case 'D':
vertical --;
break;
case 'L':
horizontal --;
break;
case 'R':
horizontal ++;
break;
}
}
return (vertical == 0) && (horizontal == 0);
}
private boolean judgeCircleWithFor() {
int x = charCount(moves, 'R') - charCount(moves, 'L');
int y = charCount(moves, 'U') - charCount(moves, 'D');
return x == 0 && y == 0;
}
private int charCount(char[] moves, char c) {
int count = 0;
for(int i=0; i<moves.length; i++) {
if(moves[i] == c) {
count++;
}
}
return count;
}
}
for 環路比交換機更昂貴。但正如其他評論中指出的那樣，運行它一次并不是可靠的性能分析。
Benchmark Mode Cnt Score Error Units
ForVsSwitch.withFor ss 0,577 ms/op
ForVsSwitch.withSwitch ss 0,241 ms/op
添加回答
舉報
0/150
提交
取消