нахождение числа, появляющегося снова среди чисел, сохраненных в файле

Question

Скажем, у меня есть 10 миллиардов чисел, хранящихся в файле. Как мне найти номер, который уже появился однажды ранее?

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

Как бы вы подошли к этой проблеме?

Заранее спасибо:)

Answer 1

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

Answer 2

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

При большом диапазоне (например, int) вам необходимо каждый раз просматривать файл.Формат файла может позволить более эффективный поиск (например, двоичный поиск в случае отсортированного массива).

Answer 3

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

Answer 4

Вы должны прочитать каждое число и сохранить его в хэш-карте, чтобы в случае повторного появления номера оно автоматически сбрасывалось.

Answer 5

Вам нужно реализовать некую циклическую конструкцию, чтобы читать числа по одному, поскольку вы не можете хранить их в памяти сразу.

Как? О, какой язык вы используете?