Чтение из файла разреженной матрицы

Question

Я использую представление Йеля разреженной матрицы в алгоритме итерации мощности, все идет хорошо и быстро.

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

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

Я пытался Somethings читать и после этого вставить в мой разреженной матрицы:

1) Используя плотную матрицу.

2) Используя другую реализацию с разреженной матрицей, я попытался использовать std :: map.

3) Очередь приоритета, я сделал массив приоритетных_круг. Я вставляю элемент i, j в priority_queue [i], поэтому, когда я выхожу priority_queue [i], я беру младший j-индекс строки i.

Но мне нужно что-то действительно быстрое и эффективное для памяти, потому что самая большая матрица, которую я буду использовать, будет равна 100k x 100k, а попытки, которые я сделал, были настолько медленными, почти в 200 раз медленнее, чем сама итерация мощности.

Любые предложения? Извините за плохой английский :(

Answer 1

как многие редкие погрузчики работают в том, что вы используете промежуточную чистые тройки структуру. Т.е. любого файл выглядит, вы загрузите его в нечто вроде vector< tuple< row, column, value> >.

Затем построить редкая структура от , что. Причина в том, что вы используете. У вашей разреженной структуры матрицы, вероятно, есть ограничения, например, вам нужно знать количество элементов в каждой строке/столбце, или нужно сортировать вход и т. д. Вы можете массировать свою тройную решетку во все, что вам нужно (то есть путем ее сортировки).

Это также делает тривиальным решить свою дилемму симметрии. Для каждой тройки исходного файла вы вставляете как (row, column, value), так и (column, row, value) в свою промежуточную структуру.

Другой вариант - просто написать сценарий, который будет сортировать файл вашего профессора.

FYI, в разреженном мире число элементов (ненулевых) - это то, что важно, а не размеры матрицы. 100k-by-100k - это бессмысленная информация. Например, вся эта матрица может быть полностью пустой.