равенство матриц m * n

Question

Что является наиболее эффективным способом проверки равенства двух матриц m * n и, что более важно, индекса [i] [j] (или индексов), из-за чего две матрицы неравны.

В моем случае «m» относительно невелико (< = 4), а n относительно велико (< = 512).

Контекст проблемы: у меня есть Active Standby setup для моего приложения. Всякий раз, когда происходит событие, которое вызывает изменение состояния, активный отправляет обновление в режим ожидания. Тем не менее, мы наблюдаем, что иногда режим ожидания не синхронизируется с активным, даже если активный отправляет все обновления. Поэтому мы планируем провести аудит структуры данных, синхронизированной. Аудит рассчитает контрольную сумму на активную и отправит их в подчиненный. Раб будет делать то же самое и вернет NAk, если они не совпадут. Актив снова синхронизирует ведомое устройство. Моя проблема в том, что я хочу, чтобы slave вернул позицию [i] [j], из-за которой контрольная сумма не совпала.

Edit: Язык 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

Как указано выше, контрольные суммы в основном не могут быть отменены. Если вы можете хэшировать только части для матрицы, вы можете как бы бинарный поиск, где вы удаляете половину оставшегося диапазона на каждой итерации. Это может работать даже при наличии более одного несоответствующего элемента: вам нужно проверить обе половины.
Кроме того, ваша матрица имеет около 2000 ячеек, на самом деле очень маленькая. Поэтому их сравнение должно быть быстрым. Если каждый объект содержит много данных, вы можете хэшировать каждый объект (поэтому у вас есть 2000 хэшей, которые должны быть намного меньше ваших объектов) и сравнить матрицы хэшей - тогда вы точно знаете, где проблема.
Опять же, имейте в виду, что вычисление контрольной суммы означает перебор по всей матрице, поэтому лучший ват для их сравнения, вероятно, один за другим, как было предложено.

Answer 4

Information Theory сообщает, что вы ничего не можете получить здесь. Если есть ячейки m * n, и каждый из них содержит k бит информации (например, 16-битные целые числа), тогда пространство возможностей вашей матрицы занимает m * n * k бит.

Если вы хотите, чтобы иметь возможность отправлять одно «сообщение» и обрабатывать каждый случай из «они синхронизированы», «каждая ячейка отличается уникальным и странным образом», тогда законы природы требуют от вас это сообщение m * n * k бит длиной. Если вы используете m * n * b - 1 бит, я смогу построить две ситуации, которые вы не можете отличить. На самом деле половина вашего пространства государства станет неразличимой.

Теперь, если вы опишете свои требования дальше, мы сможем сократить пространство возможностей. То, что вы, может получить, например, дешево, это способность распознавать 1 ячейку вне синхронизации, как было описано другими. Имейте в виду, что алгоритм, предназначенный для обнаружения 1 diff, будет полностью терпеть неудачу, если существует 2 diff. например он скажет вам, что ячейка A не синхронизирована, когда она действительно является клетками B и C.