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

Ответ 1

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

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

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

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

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

Ответ 2

Вот хороший способ хранения симметричной матрицы, для этого требуется только память 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

Ответ 3

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

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]).

Ответ 4

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

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;

Ответ 5

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

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 - вам нужно вычислить в нем правильное смещение, но это не так сложно, и он будет использовать немного меньше памяти, работать немного быстрее и т.д. d используйте простой код для первой версии и при необходимости оптимизируйте его позже.

Ответ 6

Вы можете использовать шахматный массив (или то, что они вызывают), если ваш язык поддерживает его, и когда x < y, переключите положение x и y. Так что...

Псевдокод (несколько стиль 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]