매트릭스 비교 알고리즘

Question

치수 N * M의 매트릭스가 2 개있는 경우. 차이점을 얻는 가장 좋은 방법은 무엇입니까? 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)입니다.

Answer 2

"최악의 경우, 이것은 O (N M)입니다. 더 효율적인 알고리즘이 있습니까?" 아마도 O (N M) 인 데이터의 크기 때문이 아닐 것입니다. 이와 같은 많은 행렬 연산은 M N입니다. 왜냐하면 최악의 경우 행렬이 같은 경우 모두 검사해야하는 N 개의 요소가 M입니다.

평균의 경우를 살펴보면 차이 상자가 전체 행렬 내에서 반드시 하나의 직사각형 일 경우보다 평균적으로 모든 요소보다 적게 스캔 할 수 있다고 생각합니다. 여기

는 내가 가진 비록 빠르다 : XY 상단 모서리

확인 지금 있도록 은 왼쪽 상단 모서리에 전화, 현재 요소의 XY

1. 시작을 추적하는 요소 XY 둘 다 동일하지 않다면 3으로 가야합니다. 그렇지 않으면 4로 이동하십시오.

2. 요소가없는 경우 차이 행렬의 요소가 있습니다. 이 요소를 기록한 다음 다른 요소에 대한 해당 행과 열을 검색합니다 (이진 검색과 같은 항목이 가장 빠를 수도 있음). 행/열을 검색하면 가장자리의 좌표가 있습니다. 요소는 아래 4

3. 다음 단계 이동 XY 대각선 하나 개의 요소와 하나 개의 요소에 동일하지 않은 이동이 있다면 바로 다음 대각선이 다음 덮여 다시 한 번

4. 당신이 함께 테스트해야합니다 2로 이동 다음 대각선 (현재 대각선에서 가장 멀리 떨어져있는 새로운 대각선을 선택하는 것이 가장 좋을 것 같지만 모든 요소가 포함될 때까지 이것이 최선의 선택이라는 증거는 없습니다). 최악의 경우는 아직 O (N * M)이지만 평균적인 경우 더 빠를 수도 있습니다.

은 기본적으로 당신은 가능한 한 빨리 하나 개 다른 요소하려고하는, 그래서 목표는 첫째 다른 요소를 찾기 위해 검색의 수의 기대 값을 최소화하는 방법으로 첫 번째 요소를 선택하고있다.

Answer 3

O (N * M)이 최적이라고 다른 사람들도 지적했습니다.

매트릭스를 통해 스캔 할 때 메모리 레이아웃을 염두에 두어야한다는 점을 추가하고 싶습니다. 행렬에 행렬이 배치 된 경우 가로로 스캔하는 것이 가장 좋습니다. 열로 배치 된 경우 세로로 스캔하는 것이 좋습니다. 이것은 거의 최적의 캐싱 동작으로 이어질 것입니다.

물론,이 질문의 차이는 사실 직사각형의 형태라고 가정합니다. 그것이 다른 모양이라면 경계 사각형을 원한다면 무엇이든지간에 행과 열을 모두 스캔해야합니다.

Answer 4

제안 된 알고리즘이 최적이라고 생각합니다. 그러나 나는 당신이 매우 효율적이고 BLAS 라이브러리를 시도하고 성능을 비교하는 것이 좋습니다. C++ 인터페이스를 제공하는 Boost uBlas 라이브러리와 methods for Matrix expressions도 있습니다.