Разреженное матричное представление

Question

У меня есть 2 вопроса относительно разреженного представления матрицы.

Основано на примере матрицы, которая у меня есть Приведенное выше, мне нужно предложить решение для представления разреженной матрицы.

Я думал о представлении разреженной матрицы, используя связанный список .

Можете ли вы, ребята, предложить мне правильный алгоритм для обоих моих вопросов? Заранее спасибо

Answer 1

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

Например:

1. Ха sh значений, где ключ - строка / столбец ненулевого элемента, например, Matrix.hash[(i,j)], Matrix.hash[(i,j)] = n
2. Связанный список ненулевых строк, каждая запись представляет собой связанный список ненулевых столбцов. например, Matrix.rows.get(i).get(j), Matrix.rows.set(i, (j, n))
3. Представление в сжатом пространстве строк, CSR (см. ссылку ниже)

Ссылки и примеры:

1. Разреженная матрица и ее представления | Набор 1 (с использованием массивов и связанных списков)
2. Разреженная матрица и ее представления | Набор 2 (с использованием списка списков и словаря ключей)
3. Представления разреженной матрицы | Установите 3 (CSR)

Чтобы отобразить содержимое разреженной матрицы, просто циклы:

for all rows i=1 to n:
    for all columns j=1 to m:
        if Matrix.has(i,j): display Matrix.get(i,j)
        else: display 0
    display newLine

Примечание , в зависимости от выбранного представления , печать l oop может быть немного оптимизирована, конечно, она должна l oop через все строки и столбцы, но, например, операции .has и .get могут быть объединены в одну оптимизированную .get и так далее ..

ОБНОВЛЕННЫЙ вопрос:

Для представления списка представление, псевдокод для вставки нового ненулевого значения значение n в строке i столбец j будет выглядеть примерно так:

function insert(matrix, n/*value*/, i/*row*/, j/*column*/)
{
    row = matrix.rows, prevrow = null;
    while(null!=row && row.index<i) { prevrow=row; row=row.next; }
    if ( !row )
    {
       if ( prevrow )
       {
           // rows with indexes less than i
           prevrow.next = {
               index:i,
               columns:{
                  index:j,
                  value:n,
                  next:null
               }, 
               next:null
            };
       }
       else
       {
           // empty matrix
           matrix.rows = {
               index:i,
               columns: {
                  index:j,
                  value:n,
                  next:null
               }, 
               next:null
            };
       }
    }
    else if ( row.index == i )
    {
        // insert column to existing row i
        col = row.columns; prevcol = null;
        while(null!=col && col.index<j){ prevcol=col; col=col.next; }
        if ( !col )
        {
           if ( prevcol )
           {
               // row with column indexes less than j
               prevcol.next = {
                  index:j,
                  value:n,
                  next:null
              };
           }
           else
           {
            // empty row
               row.columns = {
                  index:j,
                  value:n,
                  next:null
               };
           }
        }
        else if ( col.index == j )
        {
            // change value to existing column j
            col.value = n;
        }
        else
        {
            // insert new column at right place
            if ( prevcol )
            {
               prevcol.next = { 
                  index:j,
                  value:n,
                  next:col
               };
            }
            else
            {
                row.columns = {
                  index:j,
                  value:n,
                  next:col
                };
            }
        }
    }
    else
    {
        // insert new row/column at right place
        if ( prevrow )
        {
            prevrow.next = { 
              index:i,
              columns:{
                 index:j,
                 value:n,
                 next:null
              },
              next: row
           };
        }
        else
        {
            matrix.rows = {
                index:i,
                columns:{
                   index:j,
                   value:n,
                   next:null
                },
                next:row
            };
         }
    }
}

Для список списков представление печати lo oop может быть оптимизировано немного похоже на следующее (псевдокод):

function print(matrix, n/*rows*/, m/*columns*/)
{
    row = matrix.rows;
    for(i=0; i<n; i++)
    {
        if ( !row || (row.index > i) )
        {
            for(j=0; j<m; j++) print('0 ');
        }
        else if ( row.index == i )
        {
            col = row.columns
            for(j=0; j<m; j++)
            {
                if ( !col || (col.index > j) )
                {
                    print('0 ');
                }
                else if ( col.index == j )
                {
                    print(string(col.value)+' ');
                    col = col.next;
                }
            }
            row = row.next;
        }

        print("\n"); // print new line
    }
}