Как сэкономить место и время с помощью зеркального массива NxN - PullRequest
Новая
       3

Как сэкономить место и время с помощью зеркального массива NxN

0 голосов
/ 22 октября 2011

Допустим, у меня есть N x N массив чисел со свойством, что число [i] [j] всегда равно числу [j] [i]. То есть: 

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

Можно ли использовать представление для экономии места и времени при доступе к элементам? Это уменьшит размер массива пополам и, если возможно, уменьшит штраф за промах в кеше путем индексации [i] [j] и [j] [i] в ​​одном и том же месте в памяти.

Ответы [ 2 ]

1 голос
/ 22 октября 2011

Просто используя одномерный массив, вы должны сэкономить место, и время доступа может немного измениться, хотя, будет ли оно быстрее или нет, это, вероятно, зависит от компилятора и языка.

Я быстро написал это решение в 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;
};

Примечание: этот код не выполняет никакой проверки ошибок, которую вы передаете вдопустимое значение строки и столбца.

1 голос
/ 22 октября 2011

Вы можете перечислить элементы в одномерном массиве следующим образом: 

01234  (n=5)
 5678
  901
   23
    4

Позиция в массиве: (n + (n-y+1))*y/2 + (x-y).

Если x<y, то поменять местами две координаты.

...