優化對角線迭代器，理想情況下有預測

我有興趣優化我的對角線迭代器。有關該問題的背景信息，請參閱2009年的StackOverflow問題Traverse Matrix in Diagonal strips。在下面的代碼中，我使用與該主題中找到的解決方案不同的方法。這個想法是創建一種類似灰色代碼的迭代器，它只使用一個布爾控制變量來遍歷對角線（無論列是否增加，zColumnIncrease）。這種方法創建一個狀態機，具有7種可能的狀態：優化對角線迭代器，理想情況下有預測

 // z - boolean type indicator 
     // ct - count (number of rows or columns) 
     // x - index (the one-based index of the row or column) 

     zColumnIncrease = true; 
     .... 
     if(xRow == ctRows && xColumn == ctColumns) break; 
     if(zColumnIncrease){ 
      if(xColumn < ctColumns){ 
       xColumn++; 
       if(xRow > 1){ 
        xRow--; 
       } else { 
        zColumnIncrease = false; 
       } 
      } else { 
       zColumnIncrease = false; 
       xRow++; 
      } 
     } else { 
      if(xColumn > 1){ 
       if(xRow < ctRows){ 
        xColumn--; 
        xRow++; 
       } else { 
        zColumnIncrease = true; 
        xColumn++; 
       } 
      } else { 
       zColumnIncrease = true; 
       if(xRow < ctRows){ 
        xRow++; 
       } else { 
        xColumn++; 
       } 
      } 
     }

注意，這個狀態機（通常是在一些工作循環的末尾）迭代對角線的牛耕式轉行書寫法秩序。例如，對於一個5×5列有序矩陣細胞的迭代如下：

11 
21 12 
13 22 31 
41 32 23 14 
15 24 33 42 51 
52 43 34 25 
35 44 53 
54 45 
55

我想這樣做的是優化這種狀態機。我看到兩種主要的優化類型：邏輯表達式壓縮和預測。在第一種情況下，可能以某種方式組合邏輯，以便代碼更有效。更大的勝利將是用預測的指令替換if-陳述。理想情況下，我希望這樣做，以便生成的彙編語言翻譯不受支持。因此，我有興趣對此代碼進行優化，並且特別想知道如何預測代碼以使其變得無分支。

來源

2014-02-20 Tyler Durden

由於這似乎是對有效代碼的優化問題，所以它可能更適合於[codereview.se]。 – Dukeling

我不想進行代碼審查。這裏需要的優化類型是一個複雜的算法問題，而不是一些重構。 –

讓我們用+/./-（對於+1/0/-1）來表示從一個位置到下一個位置的列和行索引的增量。

對於5x5的陣列，我們有

+. 
-+ .+ 
+- +- +. 
-+ -+ -+ .+ 
+- +- +- +- .+ 
-+ -+ -+ +. 
+- +- .+ 
-+ +.

我們還可以安排這種像數組，希望能看到一列/行模式出現：

+. -+ +. -+ .+ 
.+ +- -+ +- -+ 
+- -+ +- -+ .+ 
.+ +- -+ +- -+ 
+- +. +- +.

或單獨爲c和r ：

+ - + - . 
. + - + - 
+ - + - . 
. + - + - 
+ + + + 

. + . + + 
+ - + - + 
- + - + + 
+ - + - + 
- . - .

我們可以總結說， e遞增遵循交替的+和-的規則矩陣，除了沿着四條邊的某些地方。主要模式通過每次迭代改變符號來獲得。要提供給基本圖案的改正GOE如下（2爲+2）：

. . . . - 
+ . . . . 
. . . . - 
+ . . . . 
. 2 . 2 

+ . + . 2 
. . . . . 
. . . . 2 
. . . . . 
. - . -

它們可以使用表達式來獲得諸如(r & 1) & !c（頂部陣列的第一列）或(~r & 1) & !(c-4)（最後一列頂部陣列）。小心一點，所有增量都可以在任何地方進行無分支計算。不是很短，但無分支。

來源

2014-02-20 21:21:06

優化對角線迭代器，理想情況下有預測

回答

相關問題