Разреженная матрица хранения в C - PullRequest
Новая
       20

Разреженная матрица хранения в C

2 голосов
/ 12 августа 2010

У меня есть разреженная матрица, которая не симметрична, т. Е. Разреженность является несколько случайной, и я не могу рассчитывать на то, что все значения находятся на заданном расстоянии от диагонали.

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

То есть, если первый ненулевой строки m находится в столбце 2, а последний ненулевой в столбце 89, я хочу сохранить в A [m] строк 2-> 89.

Поскольку каждая строка не имеет одинакового количества ненулевых элементов, я сделаю так, чтобы все строки A имели одинаковое количество элементов, и добавили нули к концу строки для строк с меньшим числомненулевых элементов.

Как мне сделать этот перевод в C?На самом деле у меня нет оригинальной, полной матрицы, чтобы просто скопировать значения (исходная матрица приходит ко мне в форме CSR).Если бы я делал это в Фортране, я мог бы просто определить мой массив как двухмерный и просто иметь каждую строку переменной длины, отслеживая начальные / конечные значения ненулевых столбцов и сохранять его таким образом.

Я попытаюсь продемонстрировать ниже:

Это матричное представление значений, которые я знаю - и для каждого значения я знаю расположение строки и столбца 

  [1    2    3    4                   ]
  [   5    6    7    8                ]
  [       10    11    12    13        ]
 m[   14    15    16    17       18   ]
  [         19    20    21         22 ]

Теперь для этой строки m имеет наибольший «промежуток» между первым ненулевым и последним ненулевым, поэтому моя новая матрица будет 5x[span of row m]

  [1     2     3     4          ]
  [5     6     7     8          ]
  [10    11    12    13         ]
 m[14    15    16    17       18]
  [19    20    21       22      ]

Как вы можете видетьстрока m не нуждается в заполнении нулями, так как в любом случае это был самый длинный "span"

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

Ответы [ 3 ]

3 голосов
/ 12 августа 2010

Я бы реализовал это как рваный массив, где A [n] [0] всегда возвращает элемент по диагонали.A [n] [1] вернет элемент справа от диагонали, A [n] [2] вернет элемент слева от диагонали, и так.Затем вам просто нужна функция, которая отображает матричный индекс [i, j] на индекс рваного массива [r] [s].

Это имеет преимущество в разреженности, и если ваши значения остаются близкими к диагонали,массивы не очень длинные.

В качестве альтернативы вы можете иметь это определение: 

struct Row
{
    int InitialOffset;
    int NumElements;
    int[] Values;
}

Тогда у вас будет строка [].Получение значения, основанного на матричном индексе, будет выглядеть следующим образом: 

//matrix is merely an array of rows...
int GetValue(*matrix this, int i, int j)
{
    Row CurrentRow = (*this)[i];
    if (CurrentRow.InitialOffset > j)
        return 0;
    else if (CurrentRow.InitialOffset + CurrentRow.NumElements < j)
        return 0; 
    return CurrentRow.Values[j - CurrentRow.InitialOffset]
}

Мой синтаксис C немного мутен, но вы должны понять.

На основании вашей демонстрации,Я бы порекомендовал это: 

struct Matrix
{
    int[,] Data
    int[] StartOffset;
    int[] NumberElements;
}

Использовать следующим образом ... 

int GetValue(*Matrix this, int i, int j)
{
    if (this.StartOffset[i] > j)
        return 0;
    else if (this.StartOffset[i] + this.NumberElements[i] < j)
        return 0; 
    return this.Data[i, j-this.StartOffset[i]];
}

Ваша процедура инициализации будет выглядеть примерно так 

//Data is a struct that holds row index, col index, and value
Matrix* InitMatrix (*Data values, int numVals)
{
    //loop through values to find longest row and number of rows
    //create new matrix, malloc matrix for longrow * numRows
    //malloc numrows elements for StartOffset and NumItems
    //foreach row, find min() and max()-min() of col indexs and 
    //store in StartOffset and NumItems
}

Вам нужно сделатьнекоторая обработка, но сжатие данных не дешево.

2 голосов
/ 12 августа 2010

Альтернативный подход заключается в использовании связанной структуры (очень эффективно, если матрица очень разрежена, не так хороша, как она становится более заполненной). Я намекнул на реализацию в предыдущем ответе .

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

1 голос
/ 12 августа 2010

Дерек, вы упомянули в одном из комментариев, что вы хотите использовать один malloc. Это означает, что вы знаете , сколько непустых элементов у вас есть. Учитывая это, можно хранить разреженную матрицу в массиве, который содержит для каждого элемента значение элемента матрицы и «дельту местоположения» для следующего элемента. Что-то вроде: 

struct melem {
    int value; // value of data
    int offset; // offset to next element
}

struct melem matrix[num_nonempty_elements];

...

// Note: this is pseudocode!
matrix[row*COLS + col].value = a[row][col];
matrix[row*COLS + col].offset = (row*COLS + col)_[i] - (row*COLS + col)_[i-1];

РЕДАКТИРОВАТЬ: Думая об этом, это очень похоже на подход со связанным списком, но требует 1 распределения. OTOH, это может потребовать больше вычислений для доступа к необходимой ячейке.

...