Я работаю над своими данными в программе на C/С++, которая является 2-мерной. Здесь мое значение вычисляется для пары, и здесь значения будут одинаковыми для foo[i][j] и foo[j][i].
Таким образом, если я реализую его, используя простой 2-мерный массив, половина моего пространства будет потрачена впустую. Итак, какая лучшая структура данных будет представлять эту нижнюю/верхнюю треугольную матрицу.
Привет,
Действительно, вам лучше всего использовать обычную двухмерную матрицу. ОЗУ довольно дешево. Если вы действительно не хотите этого делать, тогда вы можете построить одномерный массив с нужным количеством элементов, а затем выяснить, как получить доступ к каждому элементу. Например, если массив структурирован следующим образом:
j
1234
i 1 A
2 BC
3 DEF
4 GHIJ
и вы сохранили его как одномерный массив, слева направо, вы получите доступ к элементу C (2, 2) с помощью array[3]. Вы можете работать с функцией от [i][j] до [n], но я не буду испортить вам удовольствие. Но вам не нужно это делать, если только треугольный массив не будет действительно огромным или вас очень беспокоит пространство.
Если у вас есть N элементов, то нижняя треугольная матрица без основной диагонали будет иметь (N - 1) * N/2 элементов или (N + 1) * N/2 элементов с главной диагональю. Без основной диагонали (I, J) (I, J ∈ 0..N-1, I > J) ⇒ (I * (I - 1)/2 + J). С главной диагональю (I, J ∈ 0..N-1, я ≥ J) ⇒ ((I + 1) * I/2 + J).
(И да, когда вы выделяете 4 гигабайта на 2,5-гигабайтную машину, сокращение ее половины делает огромную разницу.)
Использовать зубчатый массив:
int N;
// populate N with size
int **Array = new Array[N];
for(int i = 0; i < N; i++)
{
Array[i] = new Array[N - i];
}
он создаст массив вроде
0 1 2 3 4 5
0 [ ]
1 [ ]
2 [ ]
3 [ ]
4 [ ]
5 [ ]
Число уникальных элементов, m, должно быть представлено в n на n симметричной матрице:
С главной диагональю
m = (n*(n + 1))/2
Без диагонали (для симметричной матрицы, как описывает OP, требуется основная диагональ, но только для хорошей меры...)
m = (n*(n - 1))/2.
Не делить на 2, пока последняя операция не будет важна, если используется целочисленная арифметика с усечением.
Вам также необходимо выполнить некоторую арифметику, чтобы найти индекс я в выделенной памяти, соответствующий строке x и столбцу y в диагональной матрице.
Указатель в выделенной памяти, i, строки x и столбца y в верхней диагональной матрице:
С диагональю
i = (y*(2*n - y + 1))/2 + (x - y - 1)
Без диагонали
i = (y*(2*n - y - 1))/2 + (x - y -1)
Для нижней диагональной матрицы flip x и y в уравнениях. Для симметричной матрицы просто выберите либо x >= y, либо y >= x внутренне, и функции члена переверните по мере необходимости.
В ответ Адриана МакКарти замените
p += side - row;
с
p += row + 1;
для нижней треугольной матрицы вместо верхней.
Как и Дэн и Праксеолит предложил для нижней треугольной матрицы с диагональю, но с исправленным правилом перехода.
Для матрицы n по n требуется массив (n+1)*n/2 длина и правило перехода Matrix[i][j] = Array[i*(i+1)/2+j].
#include<iostream>
#include<cstring>
struct lowerMatrix {
double* matArray;
int sizeArray;
int matDim;
lowerMatrix(int matDim) {
this->matDim = matDim;
sizeArray = (matDim + 1)*matDim/2;
matArray = new double[sizeArray];
memset(matArray, .0, sizeArray*sizeof(double));
};
double &operator()(int i, int j) {
int position = i*(i+1)/2+j;
return matArray[position];
};
};
Я сделал это с помощью double, но вы можете сделать его как template. Это просто базовый скелет, поэтому не забудьте реализовать деструктор.
Риффы на ответ Дани...
Вместо того, чтобы выделять множество массивов разных размеров, что может привести к фрагментации памяти или странным схемам доступа к кэшу, вы можете выделить один массив для хранения данных и одного небольшого массива для хранения указателей на строки в первом распределении.
const int side = ...;
T *backing_data = new T[side * (side + 1) / 2]; // watch for overflow
T **table = new T*[side];
auto p = backing_data;
for (int row = 0; row < side; ++row) {
table[row] = p;
p += side - row;
}
Теперь вы можете использовать table, как если бы это был зубчатый массив, как показано в ответе Dani:
table[row][col] = foo;
Но все данные находятся в одном блоке, что в противном случае это может быть не в зависимости от стратегии распределителя.
Использование таблицы указателей строк может быть или не быть быстрее, чем вычисление смещения с использованием формулы Praxeolitic.