Ответ Эриксона, вероятно, ожидаемый тем, кто задает этот вопрос.
Вы можете использовать каждую из N машин в качестве корзины в хеш-таблице:
- для каждой строки (скажем, строка номер i в последовательности) вычислить хеш-функцию для нее, h.
- отправить значения i и h на номер машины n для хранения, где n = h% N.
- с каждого компьютера, получить список всех значений хеш-функции h, для которых было получено более одного индекса, вместе со списком индексов.
- проверить наборы строк с одинаковыми значениями хеша, чтобы увидеть, действительно ли они равны.
Честно говоря, для 10 миллиардов строк вы могли бы правдоподобно сделать это на 1 ПК. Хеш-таблица может занимать что-то вроде 80-120 ГБ с 32-битным хешем, в зависимости от точной реализации хеш-таблицы. Если вы ищете эффективное решение, вам нужно немного конкретизировать, что вы подразумеваете под «машиной», потому что это зависит от того, сколько памяти у каждого есть, и относительной стоимости сетевого взаимодействия.