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

Question

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

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

Контекст проблемы: у меня есть настройка активного режима ожидания для моего приложения. Всякий раз, когда происходит событие, которое вызывает изменение состояния, активный отправляет обновление в резервный. Тем не менее, мы наблюдали, что иногда резерв не синхронизирован с активным, даже если активный отправил все обновления. Поэтому мы планируем провести аудит синхронизированной структуры данных. Аудит вычислит контрольную сумму на активном и отправит их ведомому. Раб будет делать то же самое и вернет 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

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

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

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

Answer 3

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

Answer 4

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

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