хеш для определенного массива

Question

У меня есть очень специфическая проблема, которую я хочу эффективно решить.

Геометрия определяется V объемами, пронумерованными от 0 до V-1. Каждый том ограничен различными поверхностями, пронумерованными от 0 до N-1).

                            Volume | Surfaces
                            --------------------
Geometry A (V=2, N=7):      0      | [0 3 5 6 2] 
                            1      | [5 4 2 1]
                            2      | [4 0 1 3 6]

Обратите внимание, что поверхность появится только один раз в объеме . Кроме того, поверхность находится максимум в 2 объемах геометрии.

Вот проблема:

У меня есть два разных описания одной и той же базовой геометрии, и я хочу найти, какой объем в геометрии A соответствует тому или иному объему в геометрии B. Другими словами, у меня одинаковые N поверхностей, но объем V определяется по-разному.

Вот геометрия B, которая может соответствовать геометрии A выше:

                             Volume | Surfaces
                            --------------------
Geometry B (V=2, N=7):      0      | [1 5 4 2]
                            1      | [3 6 5 0 2] 
                            2      | [0 1 3 6 4]

Учитывая геометрию A и B, я хочу иметь возможность связывать каждый том геометрии A с соответствующим объемом в геометрии B, наиболее эффективно, насколько это возможно.

A   0  1  2
B   1  0  2

Проект решения:

Сортировка каждого массива поверхностей в порядке возрастания или убывания, а затем сортировка каждого тома в соответствии с лексикографическим порядком их поверхностей. Проблема легко и надежно решается таким образом.

Лучшее решение:

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

Почему я думаю, что хеш может быть хорошим решением?

Взять хеш (Объем) = мин ([Поверхности])

Этот хеш уже имеет не более 1 столкновения, потому что поверхность может появляться только в 2 томах!

Теперь, если я возьму хэш (Громкость) = min ([Поверхности]) + max ([Поверхности]) * N, у меня все еще будет не более 1 столкновения, но вероятность становится очень маленькой, когда много объемов и поверхности.

Answer 1

Я нашел довольно хорошую хеш-функцию, в которой почти никогда не должно быть коллизий:

V: [S_0 S_1 S_2 S_3...S_N-1]

u64 hash(V) = 0;
for i in {0..N-1} :
    hash(V) = hash(V) ^ (1<<(S_i & 63))
end

Это дает уникальное 64-битное число, и все числа возможны (в отличие от решения Omg, где большинство чисел невозможно получить, учитывая, что в списке поверхностей нет повторений)

В крайнем случае, когда происходит столкновение (которое я увижу после сортировки), я буду глупо сравнивать массивы.

Answer 2

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

предположим, что p_i - это i-ое простое число, такое, что p_0 = 2, p_1 = 3, p_2 = 5, p_3 = 7, p_4 = 11, p_5 = 13, p_6 = 17, p_7 = 19 .... Мы может определить хеш-функцию для x_0, x_1, ..., x_k из массива так, чтобы h (x_0, ..., x_k) = p_ {x_0} p_ {x_1} ... p_ {x_k}. Также для повторяющихся чисел мы можем применить число повторений как степень p_ {x_i}. Это означает, например, что если x_i повторяется 3 раза, мощность p_ {x_i} в h будет равна p_ {x_i} ^ 3. если число повторений x_i равно a_i, мы будем иметь h (x_0, ..., x_k) = p_ {x_0} ^ {a_0} p_ {x_1} ^ {a_1} ... p_ {x_k} ^ {a_k}.

Следовательно, для геометрии A имеем:

                    Volume |      Surfaces     | Hash
                    ----------------------------------
  geometry A           0   | [0, 3, 5, 6, 2]   | 2 * 7 * 13 * 17 * 5 = 15470 
                       1   | [5, 4, 2, 1]      | 13 * 11 * 5 * 3 = 2145
                       2   | [4, 0, 1, 3, 6]   | 11 * 2 * 3 * 7 * 17 = 7854

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