Алгоритм Сравнения матриц
Если у Вас есть 2 Матрицы размеров N*M. что лучший способ состоит в том, чтобы получить различие Rect?
Пример:
2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3
2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3
2 3 4 5 4 3 2 3 <---> 2 3 2 3 2 3 2 3
2 3 4 5 2 3 2 3 2 3 2 3 2 3 2 3
2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3
|
|
\ /
Rect([2,2] , [3,4])
4 5 4
4 5 2-> A (2 x 3 Matrix)
Лучшее, о котором я мог думать, должно просканировать от Верхнего левого хита точку, где существует различие. Затем сканирование от Нижнего правого и поражает точка, где существует различие.
Но В худшем случае, это - O (N*M). существует ли лучший эффективный алгоритм? Или есть ли что-то, что я мог сделать с тем, как я представляю их, так, чтобы можно было применить более эффективный алгоритм? И обратите внимание, эта Матрица может быть очень большой.
4 ответа
Нет, более эффективного алгоритма не существует. Для одинаковых матриц необходимо сканировать все элементы, поэтому алгоритм обязательно O(n*m).
"Но в худшем случае это O(NM). есть ли более эффективный алгоритм?". Вероятно, нет, поскольку размерность данных составляет O(NM). Многие матричные операции, подобные этой, имеют порядок MN, потому что в худшем случае есть MN элементов, которые все должны быть проверены в случае, если матрицы равны.
Рассмотрение среднего случая более интересно, если поле разности - это обязательно один прямоугольник в пределах всей матрицы, то я подозреваю, что в среднем можно обойтись сканированием меньше, чем всех элементов.
Вот что мне пришло в голову: отслеживайте текущий элемент, назовем его XY
Начните с левого верхнего угла, так что XY - это верхний угол сейчас
Проверьте, что элементы XY в обоих равны, если не равны, перейдите к 3, если нет, перейдите к 4
Если элементы не равны, то у вас есть элемент матрицы различий. Запишите этот элемент, затем найдите в этой строке и столбце другие элементы (возможно, быстрее всего использовать что-то вроде двоичного поиска). После того, как строка/столбец будут найдены, вы получите координаты краев. Если элементы не равны, перейдите к 4.
Следующим шагом переместите XY по диагонали на один элемент вниз и один элемент вправо, затем снова перейдите к 2.
Как только диагональ будет пройдена, вам нужно будет проверить следующую диагональ (я подозреваю, что выбор новой диагонали, наиболее удаленной от текущей диагонали, будет лучшим, хотя у меня нет доказательств того, что это лучший выбор), пока все элементы не будут пройдены. В худшем случае это все еще O(N*M), но в среднем случае это может быть быстрее.
По сути, вы пытаетесь найти один различный элемент как можно быстрее, поэтому цель состоит в том, чтобы выбрать первый элемент таким образом, чтобы минимизировать ожидаемое значение количества поисков для нахождения первого различного элемента.
Я думаю, что предложенный алгоритм является оптимальным. Однако я предлагаю вам попробовать библиотеку BLAS, которая очень эффективна, и сравнить производительность. Существует также библиотека Boost uBlas, которая предоставляет интерфейс C++ и методы для матричных выражений.
Как отметили другие, O(N*M) является оптимальным.
Я хотел бы добавить, что при сканировании матрицы следует помнить о ее расположении в памяти. Если матрица разложена по строкам, то лучше всего сканировать по горизонтали. Если она расположена по столбцам, то лучше сканировать по вертикали. Это приведет к практически оптимальному поведению кэширования.
Конечно, это предполагает, что рассматриваемая разница действительно имеет форму прямоугольника. Если это какая-то другая форма, и вам нужен ограничивающий прямоугольник, вам придется сканировать и строки, и столбцы, независимо ни от чего.