Алгоритм сравнения матриц

Question

Если у вас есть 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). Есть ли лучший эффективный алгоритм? Или я мог бы что-то сделать с тем, как я их представляю, чтобы вы могли применить более эффективный алгоритм? И заметьте, эта Матрица может быть очень большой.

Answer 1

"Но в худшем случае это O (N M). Есть ли лучший эффективный алгоритм?" Вероятно, не из-за размерности данных, составляющих O (N M). Многие операции с матрицами, подобные этой, имеют порядок M N, поскольку в худшем случае есть M N элементов, которые необходимо будет проверить в случае совпадения матриц.

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

Вот быстрый, хотя у меня было: отслеживать текущий элемент, назовите это XY

1. Начните с верхнего левого угла, поэтому XY теперь является верхним углом

2. Убедитесь, что элементы XY в обоих равны, если не равны, переходите к 3, иначе переходите к 4

3. Если элементов нет, то у вас есть элемент матрицы разностей. Запишите этот элемент, затем найдите в этой строке и столбце другие элементы (возможно, что-то вроде двоичного поиска будет самым быстрым). После поиска строки / столбца у вас есть координаты ребер. Если элементы не равны, переходите к 4.

4. Следующий шаг переместите XY по диагонали на один элемент вниз и один элемент вправо, затем снова перейдите к 2

5. после того, как диагональ пройдена, вам нужно будет проверить ее по следующей диагонали (я подозреваю, что лучше выбрать новую диагональ, которая находится дальше всего от текущей диагонали, хотя у меня нет никаких доказательств того, что это лучший выбор) пока все элементы не будут охвачены. В худшем случае это все еще O (N * M), но в среднем это может быть быстрее.

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

Answer 2

Нет, более эффективного алгоритма нет. Для идентичных матриц необходимо отсканировать все элементы, поэтому алгоритм обязательно O(n*m).

Answer 3

Как и другие отмечали, O (N * M) является оптимальным.

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

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

Answer 4

Я думаю, что предложенный алгоритм является оптимальным. Однако я предлагаю вам попробовать очень эффективную библиотеку BLAS и сравнить ее производительность. Существует также библиотека Boost uBlas , которая предоставляет интерфейс C ++ и методы для выражений Matrix .