#hash #comparison #data-transfer
#хэш #сравнение #передача данных
Вопрос:
Допустим, список с лицом A = [T, T, F, T, F …] и список с лицом B = [T, T, F, T, T …], тогда нам нужно сказать, что индекс 4 является первой позицией несоответствия в списках.
Количество записей в списках может быть очень большим (~ 50 миллионов). Как мы можем эффективно выполнить этот поиск с наименьшим объемом данных (байт), передаваемых между двумя пользователями?
Комментарии:
1. Вы можете использовать Merkle tree и адаптировать его для вашей задачи.
2. Спасибо. Я узнал, что деревья Меркла используются для хэширования любых данных и создания из них дерева хэшей данных. Можно ли провести какую-либо оптимизацию, исходя из того факта, что список содержит только логические значения?
3. Обычно лист дерева Merkle содержит хэш элемента в массиве. Поскольку у вас есть логические значения, вы можете использовать 32 значения за один раз (например: 0-31, 32-63 и так далее для 256-битной хэш-функции).
4. Понял, можешь добавить это в качестве ответа, чтобы я мог его принять?
Ответ №1:
Вы можете использовать древовидную структуру Merkle и найти несоответствие в O(log n) переводах. Для 256-битной хэш-функции (например, SHA256) вы можете разделить массив на части по 256 элементов. Эти части будут листьями дерева Меркла.