#java #hashmap #hashtable #adjacency-list #adjacency-matrix
#java #hashmap #хэш-таблица #список смежности #матрица смежности
Вопрос:
В моем проекте я пытаюсь построить матрицу смежности для графика, и из соображений пространства и времени мы должны использовать разреженную матрицу, что, насколько я понимаю, проще всего сделать с помощью hashmap. К сожалению, нам также пришлось реализовать список смежности, который я реализовал с помощью упомянутой hashmap, и поскольку наша матрица смежности должна структурно отличаться, я не могу использовать hashmap для матрицы. Есть ли какой-либо другой способ ее реализации?
Ответ №1:
Для n-мерной матрицы вы можете использовать вариант двоичного дерева. При вставке etc вы просто перебираете размеры, пока не найдете лист.
Итак, для простого двумерного набора данных, скажем (2, 5), (10, 1), (5, 6), (3, 4) вставленный в таком порядке, вы получите
(2, 5)
(10, 1)
(5, 6)
/
(3, 4)
(2, 5) вставляется в корневой каталог.
(10, 1) выполняется правильно, потому что 10 > 2.
(5, 6) идет справа от (2, 5), потому что 5 > 2. Затем он идет справа от (10, 1), потому что 6 > 1.
(3, 4) идет вправо 3 > 2. Затем вправо 4 > 1. Затем влево 3 < 5.
Ответ №2:
На странице Википедии, посвященной разреженным матрицам, перечислены 6 альтернатив:
- Словарь ключей (DOK).
- Список списков (LIL)
- Список координат (COO)
- Йельский формат
- Сжатая разреженная строка (CSR или CRS)
- Сжатый разреженный столбец (CSC или CCS)
Другой альтернативой является список смежности.
Наконец, вам также следует рассмотреть возможность представления матрицы смежности в виде растрового изображения, сопоставляя каждую ячейку матрицы с определенным битом. (Типичная JVM представляет boolean[] в виде массива машинных байтов с одним логическим значением на байт.) Если учесть объемные накладные расходы Java-хэш-таблиц и списков, матрица смежности должна быть довольно большой … и разреженный … перед более сложными «разреженными» структурами данных дает вам экономию места.
Ответ №3:
Вы могли бы использовать список списков или список координат.
Ответ №4:
Попробуйте List<SparseIntArray> , используя реализацию ArrayList as List , или обычный массив SparseIntArray[] , если вы знаете размер.
SparseIntArray — довольно маленький изолированный класс от Google Android.
Вот как я использую это для представления разреженных матриц с обычными операциями. Это очень экономит память.