MIPS鑽石分選

Question

我在內存中有以下菱形陣列，從基地址5000開始。第一個有效值位於5008（索引2），其他所有值都相對於它定位。

. . 4 . . 
. 3 7 8 . 
2 2 9 8 5 
. 1 5 9 . 
. . 3 . . 

所有值表示爲「。」在數組中是未初始化的，所以他們不應該被訪問。

現在的問題。我需要在MIPS中排序這個數組而不訪問內存中未初始化的值。由於內存限制，我無法創建一個包含鑽石所有有效索引的新數組。所以基本上，我卡住了。

Answer 1

細胞k的行可以被計算爲：

row(k) = k < (S+1)*(S+1)/4 ? isqrt(k) : S - 1 - isqrt((S*S-1)/2 - k) 

n行的菱形陣列中的縮進是：

indent(n) = abs((S - 1)/2 - n) 

細胞，其中行n開始於是：

start(n) = n < S/2 ? n*n : (S*S+1)/2 - (S-n)*(S-n) 

結合這些，你可以cal culate細胞k的指標：

index(k) = row(k)*S + indent(n) + (k - start(row(k))) 

例子：

S = 5 
. . # . . 
. # # # . 
# # # # # 
. # # # . 
. . # . . 

cell row  indent start index 
0  0  2  0  2 
1  1  1  1  6 
2  1  1  1  7 
3  1  1  1  8 
4  2  0  4  10 
5  2  0  4  11 
6  2  0  4  12 
7  2  0  4  13 
8  2  0  4  14 
9  3  1  9  16 
10  3  1  9  17 
11  3  1  9  18 
12  4  2  12  22 

利用這一點，你可以很容易地實現Selection sort：

/// Calculates the index of cell k in a diamond array of size S. 
int index(int k, int S) 
{ 
    int row = k < (S+1)*(S+1)/4 ? isqrt(k) : S - 1 - isqrt((S*S-1)/2 - k); 
    int indent = abs((S - 1)/2 - row); 
    int start = n < S/2 ? n*n : (S*S+1)/2 - (S-n)*(S-n); 
    return row*S + indent + (k - start); 
} 

/// Sorts the diamond array data, of size S. 
void diamondSelectionSort(int[] data, int S) 
{ 
    int total = (S*S+1)/2; 
    for (int i = 0; i < total; i++) 
    { 
     int indexI = index(i,S); 

     int bestCell = i; 
     int bestIndex = indexI; 
     int bestValue = data[bestIndex]; 

     for (int j = i+1; j < total; j++) 
     { 
      int indexJ = index(j,S); 

      if (data[indexJ] < bestValue) 
      { 
       bestCell = j; 
       bestIndex = indexJ; 
       bestValue = data[indexJ]; 
      } 
     } 
    } 

    if (bestIndex > i) 
    { 
     data[bestIndex] = data[indexI]; 
     data[indexI] = bestValue; 
    } 
} 

/// Integer square root. Adopted from 
/// http://home.utah.edu/~nahaj/factoring/isqrt.c.html 
int isqrt (int x) 
{ 
    if (x < 1) return 0; 

    int squaredbit = (int) ((((unsigned int) ~0) >> 1) & 
      ~(((unsigned int) ~0) >> 2)); 
    int remainder = x; 
    int root = 0; 
    while (squaredbit > 0) { 
     if (remainder >= (squaredbit | root)) { 
      remainder -= (squaredbit | root); 
      root = (root >> 1) | squaredbit; 
     } else { 
      root >>= 1; 
     } 
     squaredbit >>= 2; 
    } 

    return root; 
} 

---

index()可以拿出一小：

/// Calculates the index of cell k in a diamond array of size S. 
int index(int k, int S) 
{ 
    int row, indent, start; 
    if (k < (S+1)*(S+1)/4) 
    { 
     row = isqrt(k); 
     indent = (S - 1)/2 - row; 
     start = n*n; 
    } 
    else 
    { 
     row = S - 1 - isqrt((S*S-1)/2 - k); 
     indent = row - (S - 1)/2; 
     start = (S*S+1)/2 - (S-n)*(S-n); 
    } 
    return row*S + indent + (k - start); 
}