3 回答

TA貢獻1804條經驗 獲得超3個贊
選項 A是 O(x^2*y) 選項 B是 O(x*y) 在您的情況下,選項 A 最多需要 2,000,000,000 次迭代,而 B 最多需要 4,000,000 次迭代。這當然不包括休息或繼續。我可能會堅持 B。

TA貢獻1779條經驗 獲得超6個贊
你也會從循環中的函數調用中獲得很多收獲,例如
int n= array.size()
for(int i=0; i<n; i++)
而不是
for(int i=0; i<array.size(); i++)
除非您在循環內修改數組大小,否則重復的函數調用是一種浪費。

TA貢獻1805條經驗 獲得超10個贊
我確實想知道是否有某種編譯器機制可以發現這樣一個事實,即循環初始化中 size() 的返回值可能是常量,因此可以替換為“有效最終”常量. 因此,我運行了以下兩個循環,第一個沒有手動持續優化:
int n1=a1.size();
for(int i=0; i<a1.size(); i++) {
int n2=a2.size();
for(int j=0; j<a2.size(); j++) {
int n3=a3.size();
for(int k=0; k<a3.size(); k++) {
int candidate=a1.get(i)*a2.get(j)*a3.get(k);
candidate+=n1*n2*n3;
func(candidate);
}//k
}//j
}//i
第二個是手動不斷優化:
int n1=a1.size();
for(int i=0; i<n1; i++) {
int n2=a2.size();
for(int j=0; j<n2; j++) {
int n3=a3.size();
for(int k=0; k<n3; k++) {
int candidate=a1.get(i)*a2.get(j)*a3.get(k);
candidate+=n1*n2*n3;
func(candidate);
}//k
}//j
}//i
然后,我使用 a1.size()=100、a2.size()=200 和 a3.size()=300 運行這些循環 10 次以獲得時間,并計算每個變量的 100 次的平均誤差和標準誤差具有 200 次運行順序的循環是隨機的。
整個過程在單個作業(即 JVM 的一次調用)中重復 10 次,以獲得 10 對均值和標準誤差(一對來自優化運行的成員,另一個來自未優化運行的成員)。在所有 10 個案例中,優化的平均時間都比未優化的平均時間快得多。在每種情況下,平均值之間的差異都超過標準誤差的 6.9 倍,并且在 10 個案例中的 7 個案例中,平均值之間的差異超過 15 個標準誤差。數據如下。為循環生成的字節碼是不同的,雖然我不聲稱會說字節碼,但還有對 a*.size() 的額外 invokevirtual 調用,我認為這是造成兩個循環版本性能差異的原因。
因此,考慮到 @Turing85 的評論,我想知道在什么情況下可以忽略“在這個級別上”的優化?
openjdk 版本“11” 2018-09-25 OpenJDK Runtime Environment 18.9 (build 11+28) OpenJDK 64-Bit Server VM 18.9 (build 11+28, mixed mode)
======數據======
優化循環運行 100 次平均每次耗時 6.412 秒,標準誤差為 0.013;100 次未優化的循環運行平均每次耗時 6.502 秒,標準誤差為 0.013
優化循環運行 100 次平均每次耗時 5.143 秒,標準誤差為 0.004;100 次未優化的循環運行平均每次耗時 5.232 秒,標準誤差為 0.005
優化循環的 100 次運行平均每次耗時 6.090 秒,標準誤差為 0.006;100 次未優化的循環運行平均每次耗時 6.175 秒,標準誤差為 0.006
優化循環的 100 次運行平均每次耗時 5.739 秒,標準誤差為 0.005;100 次未優化的循環運行平均每次耗時 5.827 秒,標準誤差為 0.005
優化循環的 100 次運行平均每次耗時 5.613 秒,標準誤差為 0.005;100 次未優化的循環運行平均每次耗時 5.697 秒,標準誤差為 0.004
100 次優化循環運行平均每次耗時 6.045 秒,標準誤差 0.004;100 次未優化的循環運行平均每次耗時 6.121 秒,標準誤差為 0.004
100 次優化循環運行平均每次耗時 5.333 秒,標準誤差 0.003;100 次未優化的循環運行平均每次耗時 5.415 秒,標準誤差為 0.003
100 次優化循環運行平均每次耗時 5.903 秒,標準誤差為 0.009;100 次未優化的循環運行平均每次耗時 5.972 秒,標準誤差為 0.007
優化循環的 100 次運行平均每次耗時 5.770 秒,標準誤差為 0.005;100 次未優化的循環運行平均每次耗時 5.851 秒,標準誤差為 0.005
100 次優化循環運行平均每次耗時 4.975 秒,標準誤差為 0.004;100 次未優化的循環運行平均每次耗時 5.052 秒,標準誤差為 0.004
添加回答
舉報