Как сохранить симметрическую матрицу?
Который является лучшим способом сохранить симметрическую матрицу в памяти?
Было бы хорошо оставить половину свободного места, не ставя под угрозу скорость и сложность структуры слишком много. Это - агностический языком вопрос, но если необходимо сделать некоторые предположения просто предположить, что это - старый добрый простой язык программирования как C или C++..
Это кажется вещью, которая имеет смысл просто, если существует способ сохранить вещи простыми или как раз в то самое время, когда сама матрица является действительно большой, действительно ли я прав?
Только ради формальности я подразумеваю, что это утверждение всегда верно для данных, которые я хочу хранить
matrix[x][y] == matrix[y][x]
5 ответов
Я обнаружил, что многие высокопроизводительные пакеты просто хранят всю матрицу, но затем считывают только верхний треугольник или нижний треугольник. Затем они могут использовать дополнительное пространство для хранения временных данных во время вычислений.
Однако если хранение действительно является проблемой, то просто храните n(n+1)/2 элементов, составляющих верхний треугольник, в одномерном массиве. Если это усложняет доступ, просто определите набор вспомогательных функций.
В C для доступа к матрице matA можно определить макрос:
#define A(i,j, dim) ((i <= j)?matA[i*dim + j]:matA[j*dim + i])
тогда вы сможете обращаться к своему массиву почти нормально.
Если вы хотите использовать одномерный массив, код будет выглядеть примерно так:
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;
Хорошо, я бы попробовал треугольную матрицу, например:
int[][] sym = new int[rows][];
for( int i = 0; i < cols; ++i ) {
sym=new int[i+1];
}
Но тогда вам придется столкнуться с проблемой, когда кто-то захочет получить доступ к «другой стороне». Например, он хочет получить доступ к [0] [10], но в вашем случае этот val хранится в [10] [0] (при условии 10x10).
Вероятно, «лучший» способ - это «ленивый» - ничего не делать, пока пользователь не попросит. Таким образом, вы можете загрузить конкретную строку, если пользователь вводит что-то вроде print (матрица [4]).
Если вы используете что-то, что поддерживает перегрузку операторов (например, 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, который создает данных в виде треугольника (т. Е. Для матрицы NxN первая строка будет иметь N элементов, вторая N-1 и так далее - или, что эквивалентно 1, 2, ... N). Вы также можете подумать о создании данных как одного вектора - вам нужно вычислить в нем правильное смещение, но это не так уж сложно, и для этого потребуется немного меньше памяти, запустите немного быстрее и т. д. Я бы использовал простой код для первой версии и при необходимости оптимизирую позже.
Вы можете использовать шахматный массив (или как они там называются), если ваш язык поддерживает его, и когда 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]