ミラーリングされたNxNアレイで空間と時間を節約する方法

Question

私は、[i] [j]の数が[j] [i]の数と常に等しいという性質を持つN x N個の数の配列を持っているとします。つまり：

[ 0 3 9 2 ] 
[ 3 0 5 6 ] 
[ 9 5 0 1 ] 
[ 2 6 1 0 ] 

エレメントへのアクセスに時間とスペースを節約するために使用できる表現はありますか？ [i] [j]と[j] [i]をメモリ内の同じ位置にインデックスすることによって、アレイサイズを半分に削減し、可能であればキャッシュミスのペナルティを減らします。

Answer 1

1次元配列を使用するだけで、スペースを節約し、アクセス時間に若干の変更があるかもしれませんが、高速であるかどうかにかかわらず、おそらくコンパイラと言語に依存します。

私はQtの中ですぐにこのソリューションを書きましたが、STLのC++または他の言語に変換するのは簡単でなければなりません：

#include <QVector> 
#include <QDebug> 
#include <QString> 

class MirroredArray 
{ 
public: 
    MirroredArray(int sideLength) 
    { 
     values.fill(0, sideLength*(sideLength+1)/2); 
     this->s = sideLength; 
    } 

    int get(int r, int c) 
    { 
     if(c > r) 
     { 
      return values.at(s*r-(r-1)*r/2 + c-r); 
     } 
     else 
     { 
      return values.at(s*c-(c-1)*c/2 + r-c); 
     } 
    } 

    void set(int r, int c, int value) 
    { 
     if(c > r) 
     { 
      values[s*r-(r-1)*r/2 + c-r] = value; 
     } 
     else 
     { 
      values[s*c-(c-1)*c/2 + r-c] = value; 
     } 
    } 
    int getSide() 
    { 
     return s; 
    } 

    QString contentsToString() 
    { 
     QString temp = "(" + QString::number(values.size()) + ") - "; 
     for(int i = 0; i<values.size(); i++) 
      temp += QString::number(i) + ", "; 
     return temp; 
    } 

private: 
    QVector <int> values; 
    int s; 
}; 

注：このコードは、あなたが渡していることを確認するすべてのエラーを行いません。有効な行と列の値。

Answer 2

あなたはこのように1次元配列の要素を列挙することができます。

は

(n=5) 
5678 
    901 
    23 
    4 

配列の位置が(n + (n-y+1))*y/2 + (x-y)です。

x<yの場合は、2つの座標を入れ替えます。