Как я могу экономно хранить разреженную матрицу в процессе заполнения элемента? - PullRequest
Новая
       8

Как я могу экономно хранить разреженную матрицу в процессе заполнения элемента?

1 голос
/ 07 января 2012

Я знаю, что есть довольно много хороших способов сохранить разреженную матрицу, не занимая много памяти. Но мне интересно, есть ли хороший способ хранения разреженной матрицы при ее создании? Вот более подробный сценарий: программа создает разреженную матрицу, выясняя, куда поместить ненулевое значение на каждую итерацию; и поскольку координаты ненулевого значения не будут известны до времени выполнения, они абсолютно случайны и непредсказуемы.

Я программирую на C ++. Так есть ли способ реализовать это в C ++? Решения на других языках также приветствуются.

Ответы [ 2 ]

2 голосов
/ 17 января 2012

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

Что не описано в вашем вопросе: как вы хотите / хотите представить разреженную матрицу в конце?Что тебе с этим делать?Это повлияет на представление

1 голос
/ 07 января 2012

std :: map может быть тем, что вы ищете, это ключ -> тип карты значений. Объедините это с std :: set, который является уникальной коллекцией элементов. Таким образом, вы можете использовать карту std :: set следующим образом: 

std::map<int, std::set<int> > sparseMatrix;

// Add some edges.
sparseMatrix[0].insert(1); // Add an edge from vertex 0 to 1.
sparseMatrix[4].insert(2); // Add an edge from vertex 4 to 2.
sparseMatrix[0].insert(1); // Edge already exists, no data added to the set.

Это представление позволяет вам представить ориентированный граф, он аналогичен списку ребер. Поведение набора также препятствует тому, чтобы у вас было два «одинаковых ребра» (a-> b и c-> d, где a = b и c = d), что хорошо, такое поведение вы получите, если вы использовал матрицу смежности. Вы можете перебрать все ребра так: 

for(std::map<int, std::set<int> >::const_iterator i = sparseMatrix.begin();
    i != sparseMatrix.end();
    ++i)
{
    for(std::set<int>::const_iterator j = i->second.begin();
        j != i->second.end();
        ++j)
    {
        std::cout << "An edge exists from " << i->first << " to " << *j << ".";
    }
}

Некоторые ссылки:

...