Если два человека A & B имеют два больших логических списка, как найти первое несоответствие в списках с наименьшей передачей данных между двумя людьми?

Question

Скажем, список с человеком A = [T, T, F, T, F ...] и список с человеком B = [T, T, F, T, T ...], тогда нам нужно скажем, что индекс 4 является первой позицией несоответствия в списках.
Количество записей в списках может быть очень большим (~ 50 миллионов). Как эффективно выполнить этот поиск с наименьшим количеством данных (байтов), передаваемых между двумя людьми?

Answer 1

Вы можете использовать древовидную структуру Merkle и найти несоответствие в O(log n) передачах. Для 256-битной хеш-функции (например, SHA256) вы можете разбить массив на части по 256 элементов. Эта часть будет листьями Меркле.