m * n 행렬의 동일성

Question

두 개의 행렬이 동일하지 않게 만드는 두 개의 m * n 행렬과 더 중요한 [i] [j] 색인 (또는 인덱스)의 동등성을 검사하는 가장 효율적인 방법은 무엇입니까?

제 경우에 'm'은 상대적으로 작고 (< = 4) n은 비교적 큽니다 (< = 512).

문제점의 배경 : 응용 프로그램에 대한 활성 대기 설정이 있습니다. 상태 변경을 유발하는 이벤트가 발생할 때마다 활성 상태가 대기 상태로 업데이트를 보냅니다. 그러나 활성 상태 인 사용자가 모든 업데이트를 보내더라도 대기 상태가 때때로 활성 상태와 동기화되지 않는 경우가 있습니다. 따라서 우리는 동기화 된 데이터 구조에 대한 감사를 실행할 계획입니다. 감사는 활성 상태 인 체크섬을 계산하여 슬레이브로 보냅니다. 슬레이브도 똑같은 작업을 수행하고 일치하지 않으면 NAk를 반환합니다. 그러면 활성 상태가 슬레이브를 다시 동기화합니다. 내 문제는 노예가 체크섬이 일치하지 않는 [i] [j] 위치로 돌아 가기를 원한다는 것입니다.

편집 : 언어 C는 행렬이 당신이 그 (것)들에게 원소 별 비교해야합니다 불일치 아무 생각이 없기 때문에

Answer 1

m >> n 인 경우 많이 사용하지는 않지만 m ~ n이면 모든 행과 열을 개별적으로 체크섬 할 수 있으므로 총 m + n 체크섬을 전송할 수 있습니다. 이렇게하면 i 번째 행 체크섬 및 j 번째 열 체크섬이 일치하지 않을 때 행렬 A_ij 항목에 문제가 있음을 알 수 있습니다. 그러나 체크섬이 얼마나 강력하고 가짜가 허용되는 빈도에 따라 다른 문제가 발생할 수 있습니다.

귀하의 경우, 516 개의 체크섬을 전송하는 것은 2048 개의 항목 전체를 보내는 것보다 중요하지 않으므로이를 구현하는 것은 조기 최적화로 시간을 낭비하는 것일 수 있습니다. 그러나 512 × 512 매트릭스의 경우 1024 개의 체크섬을 전송하는 것이 262,144 개의 항목을 보내는 것보다 훨씬 더 좋습니다.

Answer 2

. 행렬을 반복하고 비교하면됩니다.

캐시 미스 페널티를 처리해야합니다. 불필요한 캐시 라인 재로드를 발생시키지 않는 순서로 매트릭스를 스캔해야합니다. 이는 언어에 따라 다릅니다. 예를 들어, C의 경우 외부 루프가 첫 번째 인덱스를 반복하고 내부 루프가 두 번째 인덱스를 반복해야합니다.

Answer 3

sharptooth에 명시된 바와 같이 체크섬은 대부분 뒤집을 수 없습니다. 행렬의 부분 만 해시 할 수 있다면 일종의 이진 검색을 할 수 있습니다. 여기서 반복 할 때마다 나머지 범위의 절반을 제거 할 수 있습니다. 두 개 이상의 불일치 요소가있는 경우에도 작동 할 수 있습니다. 두 개를 모두 확인해야합니다.
또한 매트릭스에는 약 2000 개의 셀이 있으며 실제로는 매우 작습니다. 그러므로 그것들을 비교하는 것이 빠르다. 모든 객체에 많은 데이터가 포함되어 있다면 모든 객체를 해시 할 수 있으므로 해시 행렬을 객체의 크기보다 훨씬 작게해야합니다.
다시 한번 체크섬을 계산한다는 것은 전체 행렬을 거친다는 것을 의미하므로, 비교할 수있는 가장 좋은 와트는 제안 된대로 1 대 1 일 것입니다.

Answer 4

Information Theory은 아무 것도 얻을 수 없다고 알려줍니다. m * n 셀이 있고 각각이 비트의 정보 (예 : 16 비트 정수)를 포함하면 매트릭스의 가능한 공간이 m * n * 비트를 차지합니다.

하나의 "메시지"를 보내고 "모든 것이 서로 독특하고 이상한 방식으로 서로 다르다"는 모든 경우를 처리하려면 자연 법칙을 따라야합니다. 이 메시지 m * n * k 비트가 길다. m * n * b - 1 비트를 사용하면 구별 할 수없는 두 가지 상황을 만들 수 있습니다. 사실, 당신의 상태 공간의 절반은 구별 할 수 없게 될 것입니다.

이제 요구 사항을 자세히 설명하면 일부 가능한 공간을 줄일 수 있습니다. 당신이 무엇을 할 수 예를 들어, 다른 사람에 의해 설명 된대로 1 셀 동기화 밖으로 인식하는 능력입니다. 2 diff가있는 경우 1 diff를 찾기 위해 설계된 알고리즘은 완전히 실패합니다. 예 : 그것은 셀 A가 실제로 셀 B와 C 일 때 동기가 맞지 않는다고 말할 것입니다.