Структура данных для работы с матричными задачами

Question

Я часто не понимаю, какая структура данных лучше подходит для матричных алгоритмов.

Под «матричным алгоритмом» я имею в виду алгоритмы, такие как Needleman-Wunsh alignment. Существует много алгоритмов, которые визуально представлены матрицей.

Интересно, что я должен выбрать:

• Массив массивов
• Linked-список связанных списков
• Хэш таблица, где ключ представляет собой кортеж, как (строка, столбец)
• и т.д.

Что я должен учитывать при столкновении с этим тупиком?

Обяснение: Мой вопрос "открыто для языка". Вы можете использовать любой язык программирования в своем ответе.

Answer 1

Какая структура данных зависит от вашего алгоритма и того, как вы получите доступ к этой матрице. Например, если размер фиксирован и необходим быстрый доступ, лучше использовать 2-мерный массив, потому что независимо от того, что вы используете, вам все равно придется выделять это пространство. Если размер матрицы определяется динамически, то, вероятно, вектор векторной (или подобной структуры данных в зависимости от языка). Другой вопрос: если ваша матрица разрежена и чрезвычайно велика (как в алгоритмах цифровой геометрии), и вам приходится часто делать арифметические операции над этой матрицей, тогда могут быть полезны структуры данных с тремя форматами, например, сжатое хранилище строк, которое может быть создано используя 3 вектора. Вы можете узнать больше по этой ссылке https://de.wikipedia.org/wiki/Compressed_Row_Storage Надеюсь, это поможет