Структура данных для разреженной матрицы, в которой элементы распределены случайным образом

Question

Я не мог думать ни о чем другом, кроме связанного списка ... Есть идея получше?

Answer 1

Если вы храните элементы в матрице, вы можете рассмотреть возможность использования хеш-таблицы от координат до их содержимого. Это позволяет искать содержимое любого расположения матрицы гораздо быстрее, чем если бы оно было сохранено в связанном списке (а именно O (1), а не O (n)).

Answer 2

Матрицы Quatree (код, используемый в статье там ), имеют достаточно хорошую вставку и сложность доступа, а также достаточно хорошую производительность.Для них существуют конкретные алгоритмы (в основном в виде научных работ).Однако они не очень распространены.Но они делают заслуживают больше любви.Если вы намереваетесь решать системы, вам будет объяснено разложение, хорошо подходящее для матриц квадродерева там .

Если ваша матрица будет построена сразу, и вам не нужно добавлять / удалять элементыпосле его создания хранилище сжатых строк (или хранилище сжатых столбцов) широко распространено и эффективно, и есть библиотеки и специальные алгоритмы для их работы.

В конце концов, вы не сказали нам, что хотитеделать с вашими матрицами.

Answer 3

Для каждого ненулевого элемента вам нужно сохранить его координаты (строку / столбец) и его значение. Есть множество способов сделать это.

В Википедии есть обзор нескольких подходов: http://en.wikipedia.org/wiki/Sparse_matrix#Storing_a_sparse_matrix

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