Каков компактный способ хранения разреженной матрицы, который позволяет эффективно перебирать каждую строку и каждый столбец?
Хранение разреженной матрицы и эффективная итерация
Ответы (1)
В статье Википедии по этому вопросу упоминается несколько способов построения структур данных для разреженных матрицы, частично используя фактическую структуру матрицы для представления. Кажется, не существует канонического способа представления, подходящего для всех видов матриц.
person
Codor
schedule
08.05.2014
Спасибо за ответ! Я читал эту статью, но мне нужно немного другое. Что мне нужно от моей матрицы, так это просто итерация по строкам и столбцам. Мне не нужен доступ по индексу. Поэтому может существовать другой специфический способ хранения такой матрицы в памяти.
- person typedef; 08.05.2014
@typedef Хорошо, я понимаю, но какова конечная цель? Будут ли строки и столбцы индексироваться по записи?
- person Codor; 08.05.2014
Извините, что вы имеете в виду под будет проиндексирован по записи? Я не упомянул, что достаточно матрицы только для чтения, которая позволяет перебирать строку или столбец.
- person typedef; 08.05.2014
@typedef В основном я спрашивал о разъяснениях; пожалуйста, уточните, что вы подразумеваете под «перебирать каждую строку и каждый столбец». Я предполагаю, что некоторые данные будут прочитаны или записаны в строки и столбцы.
- person Codor; 08.05.2014
Хорошо, спасибо, я понял. Итак, мне нужен класс ReadOnlySparseMatrix, который (например) имеет два метода: GetRowConstIterator (строка ui32) и GetColumnConstIterator (столбец ui32). Итераторы, возвращаемые этими функциями, должны иметь методы IsValid() и оператор*. Все описанные методы должны быть O(1). Конечно, для этого есть простое решение: хранить две обычные разреженные матрицы, одну по строкам, другую по столбцам, но я думаю, что это можно оптимизировать, чтобы не хранить одни и те же данные несколько раз.
- person typedef; 08.05.2014
Вы используете С++? Если это так, отметьте вопрос соответствующим образом, это потенциально может привлечь больше людей, которые могут внести свой вклад.
- person Codor; 08.05.2014
Я думаю, что лучшее, что вы можете получить, — это разреженная матрица порядка строк и разреженная матрица порядка столбцов, данные которой представляют собой массив указателей, а не массив данных на месте. Но тогда, конечно, запрос столбца - это O (nnz)
- person joeln; 09.05.2014
