#c #algorithm
#c #алгоритм
Вопрос:
Давайте предположим, что у нас есть огромная симметричная диагональная матрица. Каков эффективный способ реализовать это?
Единственный способ, о котором я мог подумать, это то, что, используя симметричное свойство, где Xij = Xji , мы можем уменьшить размер этой матрицы вдвое. Но тогда представление этой матрицы с использованием 2D-массива было бы неэффективным, поскольку мы не можем уменьшить размер матрицы с помощью массивов.
Другая вещь, представляющая эту матрицу с использованием списка смежности, также была бы неэффективной, поскольку связывала эту матрицу с графиком. Это был бы график плотности. И работа со списком adj занимает много времени, такого как удаление, вставка и поиск.
Но как насчет использования куч?
Комментарии:
1. Попробуйте использовать одномерный массив с неровным столбцом и индексацией для обработки зеркального отображения.
2. Да, это хороший вариант. Есть ли какие-либо другие методы, о которых вы можете подумать?
3. Боюсь, недостаточно информации, чтобы дать вам что-то лучшее. Необходимо знать предполагаемый шаблон использования, но одномерный массив даже при умеренно сложной математике индексирования, которая вам понадобится, попадает во множество приятных мест.
4. Эмм.. Что такое симметричная диагональная матрица? Не могли бы вы показать пример?
Ответ №1:
Нет единого ответа, пока вы не решите, что вы собираетесь делать с этой матрицей (или, может быть, матрицами?).
Если вы просто собираетесь сохранить и запомнить это, то просто сохраните его последовательно, исключая избыточные записи. (Ваш код знает, как получить к нему доступ, потому что это все, что он делает, верно?)
Более вероятно, вы хотите выполнять обычные матричные операции над ней. В таком случае, вы пытаетесь сделать хранение эффективным или выполнение? В более позднем случае я не вижу много возможностей, основанных на том, что он симметричен — умножения — дорогая вещь, и вам, вероятно, все еще нужны все это. Если это хранилище, то вы ограничиваете себя операциями, которые принимают только симметричный вход и симметричный выход? Звучит ужасно специфично. Если это так, то вам нужно выполнить вычисления только для той части, которую вы сохраняете, потому что по определению другие записи симметричны, поэтому просто напишите свой код для генерации этой части матрицы, и все готово.
Комментарии:
1. Иногда вы знаете, что нам нужно балансировать между эффективным хранением и эффективным выполнением. Матрица, с которой я имею дело, содержит расстояния между точками, т. Е. Метрику расстояния, такую как косинусное расстояние. Поскольку я имею дело с большими наборами данных, мне нужно найти эффективную структуру данных, которая будет балансировать между хранилищами и выполнением.
2. Обычно экономия в диапазоне 0-50% никого не слишком волнует (реальной отдачей является экономия в 90-99,9%). Но если это делает вашу систему выполнимой, я бы сказал, что стоит написать весь код, чтобы он знал форму каждой матрицы — в любом случае, только код операции придает значение любому заданному местоположению в матрице.