Как хранить симметричную матрицу?

Question

Какой наилучший способ сохранить симметричную матрицу в памяти?

Было бы хорошо сэкономить половину пространства без чрезмерного снижения скорости и сложности структуры.Это не зависящий от языка вопрос, но если вам нужно сделать какие-то предположения, просто предположите, что это старый добрый простой язык программирования, такой как C или C ++.чтобы все было просто или просто когда сама матрица действительно большая, я прав?

Просто ради формальности я имею в виду, что это утверждение всегда верно для данных, которые я хочу сохранить

matrix[x][y] == matrix[y][x]

Answer 1

Вот хороший метод для хранения симметричной матрицы, он требует только N (N + 1) / 2 памяти:

int fromMatrixToVector(int i, int j, int N)
{
   if (i <= j)
      return i * N - (i - 1) * i / 2 + j - i;
   else
      return j * N - (j - 1) * j / 2 + i - j;
}

Для некоторой треугольной матрицы

0 1 2 3
  4 5 6
    7 8
      9

1D представление (хранится, например, в std::vector) выглядит следующим образом:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

И вызов fromMatrixToVector (1, 2, 4) возвращает 5, поэтому данные матрицы имеют вектор [5] -> 5.

Для получения дополнительной информации см http://www.codeguru.com/cpp/cpp/algorithms/general/article.php/c11211/TIP-Half-Size-Triangular-Matrix.htm

Answer 2

Я считаю, что многие высокопроизводительные пакеты просто хранят всю матрицу, а затем читают только верхний или нижний треугольник. Затем они могут использовать дополнительное пространство для хранения временных данных во время вычислений.

Однако, если хранение действительно является проблемой, просто сохраните элементы n(n+1)/2, составляющие верхний треугольник, в одномерном массиве. Если это затрудняет доступ, просто определите набор вспомогательных функций.

В C для доступа к матрице matA вы можете определить макрос:

#define A(i,j, dim) ((i <= j)?matA[i*dim + j]:matA[j*dim + i])

тогда вы можете получить доступ к вашему массиву почти нормально.

Answer 3

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

int[] new matrix[(rows * (rows + 1 )) >> 1];
int z;
matrix[ ( ( z = ( x < y ? y : x ) ) * ( z + 1 ) >> 1 ) + ( y < x ? y : x ) ] = yourValue; 

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

int[] new matrix[(rows * (rows + 1 )) >> 1];
int[] lookup[rows];
for ( int i= 0; i < rows; i++)
{
   lookup[i] = (i * (i+1)) >> 1;
}
matrix[ lookup[ x < y ? y : x ] + ( x < y ? x : y )  ] = yourValue;

Answer 4

Ну, я бы попробовал треугольную матрицу, например:

int[][] sym = new int[rows][];
for( int i = 0; i < cols; ++i ) {  
     sym=new int[i+1];
}

Но тогда вам придется столкнуться с проблемой, когда кто-то захочет получить доступ к "другой стороне".Например, он хочет получить доступ к [0] [10], но в вашем случае этот val хранится в [10] [0] (при условии 10x10).

Вероятно, «лучшим» способом является ленивый - не делайтеничего, пока пользователь не запросит.Таким образом, вы можете загрузить определенную строку, если пользователь печатает что-то вроде print (matrix [4]).

Answer 5

Вы можете использовать разнесенный массив (или как он там называется), если ваш язык поддерживает его, и когда x

Псевдокод (немного в стиле Python, но не совсем) для матрицы n x n:

matrix[n][]

for i from 0 to n-1:
    matrix[i] = some_value_type[i + 1]

[next, assign values to the elements of the half-matrix]

А потом при обращении к значениям ....

if x < y:
    return matrix[y][x]
else:
    return matrix[x][y]

Answer 6

Если вы используете что-то, поддерживающее перегрузку операторов (например, C ++), это довольно просто сделать прозрачно.Просто создайте матричный класс, который проверяет две подписки, и, если вторая больше первой, поменяйте их местами:

template <class T>
class sym_matrix { 
    std::vector<std::vector<T> > data;
public:
    T operator()(int x, int y) {
        if (y>x)
            return data[y][x];
        else
            return data[x][y];
    }
};

На данный момент я пропустил все остальное и просто охватил подписку.В действительности, чтобы правильно обрабатывать использование как lvalue и rvalue, вам, как правило, нужно возвращать прокси вместо T напрямую.Вам понадобится ctor, который создает data в виде треугольника (т. Е. Для матрицы NxN первая строка будет иметь N элементов, вторая N-1 и т. Д. - или, эквивалентно, 1, 2, ...N).Вы можете также рассмотреть возможность создания data как одного vector - вам нужно вычислить правильное смещение в нем, но это не очень сложно, и оно будет использовать немного меньше памяти, работать немного быстрее и т. Д.Использовать простой код для первой версии и оптимизировать позже, если необходимо.