Equality of matrices m * n
What is the most efficient way of checking the equality of two m * n matrices and more importantly the index [i] [j] (or indices) which caused the two matrices to be unequal.
In my case, "m" is relatively small (<= 4) and n is relatively large (<= 512).
Problem context: I have an Active Standby setup for my application. Whenever an event occurs that causes a state change, the active one sends an update to sleep. However, we observe that sometimes the standby does not sync with the active one, even if the active one sends all updates. Therefore, we plan to audit the data structure synchronized. The audit will calculate the checksum for the active one and send them to the slave. The slave will do the same and will return NAk if they don't match. The asset syncs the slave again. My problem is that I want the slave to return the position [i] [j] which caused the checksum to not match.
Edit: C language
a source to share
While this is little used for the case where m → n, if m ~ n, you can check all rows and columns separately, giving you only m + n checksums to transfer. By doing this, you know that when the i
th row checksum and j
th column checksum do not match, there is a problem with writing the A_ij
matrix. But there can be other problems, depending on how reliable your checksums are and how often they allow false negatives.
In your case, sending 516 separate checksums is not a significant win over sending the entire 2048-record matrix, and therefore implementing this is probably just wasting your time on premature optimization. But for a 512 × 512 matrix, sending 1024 checksums is much better than sending 262,144 records.
a source to share
Since you have no idea where the matrix mismatch is, you will have to compare them step by step. Just iterate over matrices and compare.
You have to take care of the potential cache miss penalties - you need to scan matrices in order so that you don't cause unnecessary cache reloads. It depends on the language. For C, for example, you need the outer loop to repeat the first index, and the inner loop to repeat the second index.
a source to share
As stated above, checksums cannot be reversed in most cases. If you can only hash parts for a matrix, you can sort of a binary search where you remove half of the remaining range on each iteration. This can work even when there is more than one non-matching item: you must check both halves.
Also, your matrix has about 2000 cells, which is actually very small. Therefore, their comparison should be quick. If each object contains a lot of data, you can hash each object (so you have 2000 hashes, which should be much smaller than your objects) and compare the hash matrices - then you know exactly where the problem is. <w> Again, keep in mind that calculating the checksum means moving the entire matrix, so the best wat to compare them is probably one by one, as intended.
a source to share
Information theory tells us that you can't get anything here. If there are m * n cells , and each of them contains k bits of information (for example, 16-bit integers), then the space of possibilities of your matrix is m * n * k .
If you want to be able to send one "message" and handle each case from "they are synchronized", "each cell is different in a unique and strange way," then the laws of nature require you to do this message m * n * k bits. If you use bits m * n * b - 1 , I can plot two situations that you cannot distinguish. In fact, half of your state space will become indistinguishable.
Now, if you further describe your requirements, we can reduce some of the possibilities. For example, what you can get cheap is the ability to recognize 1 cell out of sync as described by others. Be aware that an algorithm designed to detect 1 diff will fail completely if 2 diffs exist. for example it will tell you that cell A is out of sync when it really is cells B and C.
a source to share