我最近在做這個問題，直接取自IOI 2010的day 1 task 3，“生活質量”，遇到了一個奇怪的現象。
我正在設定一個 0-1 矩陣并使用它來計算 1 個回圈中的前綴和矩陣：
for (int i = 1; i <= m; i )
{
for (int j = 1; j <= n; j )
{
if (a[i][j] < x) {lower[i][j] = 0;} else {lower[i][j] = 1;}
b[i][j] = b[i-1][j] b[i][j-1] - b[i-1][j-1] lower[i][j];
}
}
我在 4 次測驗中得到了 TLE（超過了時間限制）（時間限制為 2.0 秒）。單獨使用 2 for 回圈時：
for (int i = 1; i <= m; i )
{
for (int j = 1; j <= n; j )
{
if (a[i][j] < x) {lower[i][j] = 0;} else {lower[i][j] = 1;}
}
}
for (int i = 1; i <= m; i )
{
for (int j = 1; j <= n; j )
{
b[i][j] = b[i-1][j] b[i][j-1] - b[i-1][j-1] lower[i][j];
}
}
給了我完整的 AC（接受）。
正如我們從這里的 4 張圖片中看到的：
TLE 結果，圖 1：https : //i.stack.imgur.com/9o5C2.png
TLE 結果，圖 2：https : //i.stack.imgur.com/TJwX5.png
AC 結果，圖 1：https : //i.stack.imgur.com/1fo2H.png
AC 結果，圖 2：https : //i.stack.imgur.com/CSsZ2.png
2 個 for 回圈代碼通常運行得更快（即使在接受的測驗用例中），這與我的邏輯形成對比，即單個 for 回圈應該更快。為什么會發生這種情況？
完整代碼（AC）：https : //pastebin.com/c7at11Ha（請忽略所有廢話和諸如 之類的東西using namespace std;，因為這是一個競爭性的編程競賽）。
- 注：裁判服務器lqdoj.edu.vn建立在全球編程競賽平臺dmoj.ca上。
uj5u.com熱心網友回復：
如果您查看組裝，您將看到差異的來源
if (a[i][j] < x) {lower[i][j] = 0;} else {lower[i][j] = 1;}
b[i][j] = b[i-1][j] b[i][j-1] - b[i-1][j-1] lower[i][j];在這種情況下，存在資料依賴性。對 b 的賦值取決于賦值給 lower 的值。所以操作在回圈中按順序進行 - 首先分配給lower，然后分配給b。由于依賴性，編譯器無法顯著優化此代碼。
將分配分成 2 個回圈
，對lower 的分配現在是獨立的，編譯器可以使用 simd 指令來提高性能。第二個回圈或多或少與原始程式集相似
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/328476.html