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

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

20 голосов
/ 30 октября 2011

Я работаю над своими данными в программе на C / C ++, которая является двухмерной. Здесь мое значение рассчитывается для пары, и здесь значения будут одинаковыми для foo[i][j] и foo[j][i].

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

С уважением,

Ответы [ 7 ]

13 голосов
/ 12 июля 2013

Если у вас есть 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, I ≥ J) ⇒ ((I + 1) * I / 2 + J).

(И да, когда вы выделяете 4 гигабайта на машине объемом 2,5 гигабайта, сокращение его вдвое имеет огромное значение.)

12 голосов
/ 30 октября 2011

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

    j
    1234
i 1 A
  2 BC
  3 DEF
  4 GHIJ

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

3 голосов
/ 30 октября 2011

Использовать неровный массив: 

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 [ ]
2 голосов
/ 19 ноября 2016

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

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

2 голосов
/ 01 января 2015

Количество уникальных элементов m, которые необходимо представить в симметричной матрице n n:

С основной диагональю

m = (n*(n + 1))/2

Без диагонали (для симметричной матрицы, как описывает ОП, необходима главная диагональ, но только для хорошей меры ...)

m = (n*(n - 1))/2.

Не делится на 2, пока не будет важна последняя операция, если используется целочисленная арифметика с усечением.

Вам также необходимо выполнить некоторую арифметику, чтобы найти индекс i в выделенной памяти, соответствующей строке 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)

Для нижней диагональной матрицы переверните x и y в уравнениях. Для симметричной матрицы просто выберите либо x> = y, либо y> = x, и функции-члены будут переворачиваться по мере необходимости.

1 голос
/ 07 марта 2016

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

p += side - row;

на 

p += row + 1;

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

0 голосов
/ 16 января 2016

По ответу Дани ...

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

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, как если бы это был зубчатый массив, как показано в ответе Дани: 

table[row][col] = foo;

Но все данные находятся в одном блоке, который иначе не мог бы зависеть от стратегии вашего распределителя.

Использование таблицы указателей строк может быть или не быть быстрее, чем вычисление смещения по формуле Праксеолита.

...