短路求值

發表於   |   分類於 ，   |   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*
	What is the output of this program ?
	猜猜看，這個程式的輸出是什麼？
*/

public class Problem {

	public static void main(String[] args) {
		
		Problem p = new Problem();
		p.evaluation();
	}
	
	public boolean sayHello(){
		
		System.out.println("Hello");
		return true;
	}
	
	public void evaluation(){
		
		boolean t = true;
		
		if(t||sayHello()){
			System.out.println("finish");
		}
	}
}

Answer

1
finish

很遺憾，他不會和你sayHello，不過只要我們做點小小的改動：

1
2
3
4
5
6
7
public void evaluation(){
    boolean t = true;
		
    if(t|sayHello()){
        System.out.println("finish");
    }
}

Output

1
2
Hello
finish

整份程式碼只將if判斷中的||修改成|，在解答理由之前，先看看第二個問題吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

/*
    and what about this?
*/

public class Problem {

	public static void main(String[] args) {
		
		Problem p = new Problem();
		p.evaluation();

	}
	
	public boolean sayHello(){
		System.out.println("Hello");
		return true;
	}
	
	public void evaluation(){
		
		boolean t = false;
		
		if(t&&sayHello()){
			System.out.println("finish");
		}else{
			System.out.println("goal");
		}
	}
}

Answer

1
goal

有了先前的經驗，答案應該不怎麼意外吧？同樣的，只要做點小小的更改，&&->&就會進入sayHello()，可以親自嘗試看看。

為什麼沒有執行sayHello()？

仔細推敲上頭的兩個問題，我們可以發現第一個問題是||屬於OR關係，只要其中之一為真，該敘述即為真。第二個問題則是&&屬於AND關係，只要其中之一為假，該敘述便為假。

換句話來說，在一個OR關係中，只要出現了一個true，不管其他的變數是真是假，我們都能聲稱該敘述為真，同樣的，在AND關係中只要出現了一個false，該敘述即為假。所以為求效率，我們可以把求值策略改成這樣：

只有前 i 個運算式求不出結果時，才去執行第 i+1 個運算式

像這類只進行必要運算的求值策略，被稱為短路求值(Short-circuit evaluation)，就好比物理中只要電路某處短路，電流就會直接繞道而行一般，又因為它只進行必要的運算，又被稱為最小化求值。

第一個問題的運算為true||sayHello()，OR中一個為真結果就為真，所以沒必要大費周章的執行sayHello()，第二個問題是同樣的道理。值得一提的是，判斷仍然是由左而右，而不是挑成本最小的運算。

短路求值能為我們的程式碼提升不少彈性，比如

1
2
3
if(obj!=null&&obj.func){
	//do something...
}

即便obj真的為null，求值也在obj!=null就結束了，不會因執行了obj.func而跳出Exception。然而，在使用上也當務求謹慎，比如上述的例子，若調轉了求值順序便會擲出例外。

為什麼那些改動會造成結果不同？

有短路求值，也自然有與之相對的嚴格求值(Eager evaluation)，其不論是否已知結果，都會很守本分的把運算式通通做完。在C++/Java，嚴格求值所用的運算子即為|與&，所以即便早就知道結果了，程式仍舊會把sayHello()執行一遍。若有興趣其他語言的運算子是哪些，可以看看wiki的這份表格。