Хэш-функция для матрицы

Question

У меня есть две матрицы, и мне нужно их сравнить, но я не хочу сравнивать позицию за позицией, я думаю, что это не лучший способ. Я думал о хэш-функциях, кто-нибудь знает, как вычислить хэш матрицы?

Answer 1

Если ваши матрицы реализованы как массивы, я бы предложил использовать memcmp() из string.h, чтобы определить, равны ли они.

Если используются значения с плавающей запятой и значения являются результатом фактических вычислений, то нет возможности проверить их значение по значению, так как вам придется включать эпсилоны для учета числовых ошибок.

Answer 2

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

trace of the matrix
vector of L0, L1, L2 norms of all columns or rows
diagonal of LU factorization
tridiagonal reduction (if symmetric)
diagonal of eigenvalues (if possible)
diagonal of SVD

Answer 3

Во-первых, хеш не скажет вам, равны ли две матрицы, а только подскажет, различаются ли они; потому что могут быть (и будут, закон Мерфи всегда скрывается) столкновения.

Вы можете вычислить хеш, связав любую функцию над элементами ... если вы можете привести элементы к целочисленным значениям (не усечению, а двоичному представлению), возможно, вы могли бы XOR все из них (но имейте в виду, что это не будет работать, если некоторые значения одинаковы, но с различным представлением, например -0 и +0 или NaN).

Так что мой совет: у вас может быть какая-то хеш-функция (даже сумма всех элементов может быть действительной), предварительно рассчитанная (это важно, нет смысла вычислять хеш каждый раз, когда вы хотите сделать сравнение и затем сравните хэши), чтобы быстро отбросить несколько разных матриц, но если хеш-код одинаков, вам придется сравнивать каждую позицию.

Answer 4

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

ссылка на контрольную сумму в Википедии