Вы можете сделать это с помощью простых чисел.Сохраняйте таблицу простых чисел для первых 66 простых чисел и используйте элементы ваших массивов (смещение +2) для индексации в таблицу простых чисел.
Идентификатор массива - это просто произведение простых чисел, представленныхэлементы в массиве.
К сожалению, продукт должен быть представлен как минимум 67 битами:
- 66 th штрих - 317, а 317 8 = 101 970 394 089 246 452 641
- log 2 (101 970 394 089 246 452 641) = 66,47 (округлено в большую сторону) равно 67 бит
Примерпсевдокод для этого (при условии существования типа данных int128):
int primes[] =
{
2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317
};
// Assumes:
// Each xs[i] is [-2, 63]
// length is [1, 8]
int128 identity(int xs[], int length)
{
int128 product = 1;
for (int i = 0; i < length; ++i)
{
product *= primes[xs[i] + 2];
}
return product;
}
bool equal(int a[], int b[], int size)
{
return identity(a, size) == identity(b, size);
}
Вы можете использовать long double в GCC для хранения продукта, поскольку он определен как 80-битовый тип данных, но я не уверен, приведет ли ошибка умножения с плавающей точкой к конфликтам между списками.Я не проверял это.
Мое предыдущее решение ниже не работает, см. Комментарии ниже.
Для каждого списка:
- Вычислитьсумма всех элементов
- Вычисляет произведение всех элементов
- Сохраните длину списка (в вашем случае, поскольку длина гарантированно будет одинаковой для двух списков, вы можете игнорировать ееполностью)
Когда вы вычисляете сумму и произведение, каждый элемент должен быть скорректирован на +3, поэтому ваш диапазон теперь равен [1, 66].
(сумма,продукт, длина) кортеж - это личность вашего списка.Любые списки с одинаковыми идентификаторами равны.
Вы можете поместить этот кортеж (сумма, произведение, длина) в одно 64-битное число:
- Для продукта: 66 8 = 360,040,606,269,696, log 2 (360,040,606,269,696) = 48,36 (округлено) равно 49 битов
- Для суммы: 66 * 8 = 528, log 2 (528) = 9,04 (округлено) составляет 10 бит
- Длина находится в диапазоне [1, 8], log 2 (8) = 3 бита
- 49 + 10 + 3 = 62 бита для представления идентификатора
Затем можно выполнить прямое 64-битноесравнения для определения равенства.
Время выполнения линейно по размеру массивов с одним проходом по каждому.Использование памяти составляет O(1).
Пример кода:
#include <cstdint>
#include <stdlib.h>
// Assumes:
// Each xs[i] is [-2, 63]
// length is [1, 8]
uint64_t identity(int xs[], int length)
{
uint64_t product = 1;
uint64_t sum = 0;
for (int i = 0; i < length; ++i)
{
int element = xs[i] + 3;
product *= element;
sum += element;
}
return (uint64_t)length << 59 | (sum << 49) | product;
}
bool equal(int a[], int b[], int size)
{
return identity(a, size) == identity(b, size);
}
void main()
{
int a[] = { 23, 0, -2, 6, 3, 23, -1 };
int b[] = { 0, -1, 6, 23, 23, -2, 3 };
printf("%d\n", equal(a, b, _countof(a)));
}