Эффективный способ реализации SparseMatrix

Question

У меня огромная матрица, но многие записи пусты.

Поэтому я попытался использовать вектор деревьев AVL, где длина вектора составляет около 20 ⁷ , а каждое дерево AVL имеет около 110 000 узлов (всего 20 ^{7 * 1006). * · 110 000 узлов).}

Но теперь, когда я увеличиваю размер проблемы до 90 000, я получаю сообщение об ошибке «Превышен лимит GC OverHeader», потому что слишком много узлов, и я настроил свою JVM с максимальным размером кучи 2 ГБ.

Интересно, есть ли другой способ эффективной реализации разреженной матрицы?

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

Answer 1

Хорошая сводка структур данных с разреженной матрицей приведена на https://en.wikipedia.org/wiki/Sparse_matrix#Storing_a_sparse_matrix, но, конечно, все зависит от того, что вам нужно с этим делать. Если все, что вам нужно, это поиск, я бы ожидал, что хеш-таблица будет более компактной, чем сбалансированное дерево. Это не займет много времени, чтобы попробовать java.util.HashMap.