Создание разреженной матрицы в Java без использования хеш-таблиц?

Question

В моем проекте я пытаюсь построить матрицу смежности для графа, и из соображений пространства и времени мы должны использовать разреженную матрицу, что, насколько я понимаю, легче всего сделать с помощью хэш-карты. К сожалению, нам также пришлось реализовать список смежности, который я реализовал с помощью указанного hashmap, и, поскольку наша матрица смежности должна быть структурно иной, я не могу использовать hashmap для матрицы. Есть ли другой способ его реализации?

Answer 1

Для n-мерной матрицы вы можете использовать вариант двоичного дерева. При вставке и т. Д. Вы выполняете циклический переход по размерам, пока не найдете лист.

Таким образом, для простого двумерного набора данных, скажем, (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. </p>

Answer 2

На странице Википедии Разреженные матрицы перечислены 6 альтернатив:

• Словарь ключей (DOK).
• Список списков (LIL)
• Список координат (COO)
• Формат Yale
• Сжатый разреженный ряд (CSR или CRS)
• Сжатый разреженный столбец (CSC или CCS)

Другой альтернативой является Список смежности .

Наконец, вам также следует рассмотреть возможность представления матрицы смежности в виде битовой карты, отображающей каждую ячейку матрицы в определенный бит.(Типичная JVM представляет boolean[] в виде массива машинных байтов с одним логическим значением на байт.) Если учесть затраты пространства в хэш-таблицах и списках Java, матрица смежности должна быть довольно большой ... и разреженной ...прежде чем более сложные «разреженные» структуры данных обеспечат вам экономию места.

Answer 3

Попробуйте List<SparseIntArray>, используя ArrayList как List реализацию или простой массив SparseIntArray[], если вы знаете размер.

SparseIntArray - довольно маленький изолированный класс от Google Android.

Вот как Я использую его для представления разреженных матриц с общими операциями. Это очень эффективно для памяти.

Answer 4

Вы можете использовать список списков или список координат .