Эффективный способ представления нижней/верхней треугольной матрицы

Ответ 1

Действительно, вам лучше всего использовать обычную двухмерную матрицу. ОЗУ довольно дешево. Если вы действительно не хотите этого делать, тогда вы можете построить одномерный массив с нужным количеством элементов, а затем выяснить, как получить доступ к каждому элементу. Например, если массив структурирован следующим образом:

    j
    1234
i 1 A
  2 BC
  3 DEF
  4 GHIJ

и вы сохранили его как одномерный массив, слева направо, вы получите доступ к элементу C (2, 2) с помощью array[3]. Вы можете работать с функцией от [i][j] до [n], но я не буду испортить вам удовольствие. Но вам не нужно это делать, если только треугольный массив не будет действительно огромным или вас очень беспокоит пространство.

Ответ 2

Если у вас есть 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-гигабайтную машину, сокращение ее половины делает огромную разницу.)

Ответ 3

Использовать зубчатый массив:

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 [ ]

Ответ 4

Число уникальных элементов, 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 внутренне, и функции члена переверните по мере необходимости.

Ответ 5

В ответ Адриана МакКарти замените

p += side - row;

с

p += row + 1;

для нижней треугольной матрицы вместо верхней.

Ответ 6

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

Для матрицы 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. Это просто базовый скелет, поэтому не забудьте реализовать деструктор.

Ответ 7

Риффы на ответ Дани...

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

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.