Определите, содержит ли очень большой массив дубликат

Question

Для массива нормального размера мы можем определить, содержит ли он дубликат, сортируя или используя hashset и т. Д. Но если у нас есть очень большой массив, скажем, длина составляет 10 миллиардов, как мы можем определить, содержит ли он дубликат?

Последующие действия: если мы знаем, что в этом большом массиве должен быть один дубликат, как мы можем определить, какой из них?

Моя идея использует сортировку, но я не знаю, есть ли лучший способ справиться с этими ситуациями.

Answer 1

Сначала ведите свои данные в ковши K с таким кодом.

files = array of K file handles 
for each d in data { 
    write d to files[hash(d) % K] 
} 
close each file 

Если вы выбрали K достаточно большим, каждое ведро будет удобно вписываться в ОЗУ. Не забудьте выбрать хорошую хеш-функцию, иначе ведра будут неуравновешенными. Фактический код также будет зависеть от используемой системы хранения. Например, если вы используете обычный жесткий диск, поиск стоит дорого, и необходимо принять меры, чтобы избежать измельчения диска. Один из подходов заключался бы в том, чтобы считывать столько данных, сколько будет вписываться в ОЗУ, а затем перебирать по нему K раз, добавляя только один из выходных файлов в каждом проходе.

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

for each f in the K files { 
    data = read f into RAM 
    detect duplicates in data 
} 

Альтернативным решением было бы использовать map-reduce framework.

Стадия карты будет выглядеть следующим образом:

map(value) { 
    emit(key=hash(value), value=value) 
} 

И уменьшить шаг будет выглядеть следующим образом:

reduce(key, values) { 
    if there's a duplicate in values { 
     emit the duplicate value. 
    } 
} 

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