Повышение скорости до матрицы смежности

Question

В настоящее время у меня есть алгоритм, который работает на матрице смежности размером n на m. В моем алгоритме мне нужно обнулить целые строки или столбцы одновременно. Моя реализация в настоящее время O (m) или O (n) в зависимости от того, является ли это столбцом или строкой.

Есть ли способ обнулить столбец или строку за O (1) раз?

Answer 1

По сути, это зависит от архитектуры чипа, с которым вы имеете дело. Для большинства процессоров невозможно обнулить целые объемы памяти на ходу, и поэтому каждое слово потребует отдельной операции с памятью, независимо от того, какие средства предоставляет ваш язык программирования.

Это очень помогает, если ваша память непрерывна для времени доступа к памяти, потому что память, смежная с памятью, к которой только что обращались, будет кэширована, и последующие обращения попадут в кеш, что приведет к высокой производительности.

Результатом этого является то, что если ваша матрица велика, может быть быстрее обнулить строку за раз или столбец за раз, а не наоборот, в зависимости от того, записаны ли ваши данные столбцом или строки.

РЕДАКТИРОВАТЬ: я предположил, что ваши матрицы не редкие, или треугольные, или иным образом особенные, так как вы говорите о "обнулении целой строки". Если вы знаете, что ваша матрица в основном пуста или каким-то другим образом соответствует специальному шаблону, вы сможете представить свою матрицу по-другому (не просто в массиве nxm), и история будет другой. Но если у вас есть матрица nxm прямо сейчас, то это так.

Answer 2

Зависит от того, как реализованы ваши матрицы.

Если у вас есть представление, такое как массив массивов, вы можете указывать на общий обнуленный массив элементов, если вы проверяете, что впоследствии не пишете в него. Это означает, что один из строки или столбца может быть обнулен в O (N) с постоянными затратами на все другие операции записи.

У вас также может быть пара массивов - один для строк, другой для столбцов - которые масштабируют значения в матрице. Установка нуля в любом из них будет операцией O (1) для маскировки строки или столбца за счет дополнительной обработки для каждого чтения; но это может стоить того, чтобы временно удалить узел из графа, если это обычный вариант использования. Это также оставляет исходную версию матрицы нетронутой, так что вы можете распараллелить ваш алгоритм (предполагая, что единственная операция, которую требуется, это обрезка всех ребер в или из узла).

Answer 3

Является ли метрика расстояния и график ненаправленным? (в этом случае матрица симметрична). В этом случае вы можете просто оперировать нижней или верхней треугольной матрицей по всей программе. Таким образом, вам просто нужно обнулить одну строку (или столбец, если вы имеете дело с верхней треугольной). и даже тогда это не будет целый ряд, в среднем половина.