Это в разделе 2.6 и задаче 2, исходная задача такая:
«В последовательном файле, содержащем 4 300 000 000 32-битных целых чисел, как найти такое, которое встречается хотя бы дважды?»
Мой вопрос к этому упражнению таков: каковы уловки вышеупомянутой проблемы и к какой категории общего алгоритма относится эта проблема?
Создайте битовый массив длиной 2 ^ 32 бита (инициализируйте его нулем), это будет около 512 МБ и поместится в ОЗУ на любой современной машине.
Начните читать файл, int по int, проверьте бит с тем же индексом, что и значение int, если бит установлен, вы нашли дубликат, если он равен нулю, установите на единицу и перейдите к следующему int из файла .
Хитрость заключается в том, чтобы найти подходящую структуру данных и алгоритм. В этом случае все помещается в оперативную память с подходящей структурой данных, и можно использовать простой и эффективный алгоритм.
Если числа int64, вам нужно найти подходящую стратегию сортировки или сделать несколько проходов, в зависимости от того, сколько дополнительной памяти вы есть в наличии.
Принцип голубятни. Если у вас есть N голубей в M ячейках и N>M, то в яме есть как минимум 2 голубя. Набор 32-битных целых чисел — это наши 2^32 ячейки, 4,3 миллиарда чисел в нашем файле — это голуби. Поскольку 4,3x10^9 > 2^32, мы знаем, что есть дубликаты.
Вы можете применить этот принцип, чтобы проверить, находится ли дубликат, который мы ищем, в подмножестве чисел за счет чтения всего файла, не загружая больше, чем понемногу за раз в ОЗУ - просто подсчитайте количество раз. вы видите число в своем тестовом диапазоне и сравниваете его с общим количеством целых чисел в этом диапазоне. Например, чтобы проверить наличие дубликатов от 1 000 000 до 2 000 000 включительно:
int pigeons = 0;
int pigeonholes = 2000000 - 1000000 + 1; // include both fenceposts
for (each number N in file) {
if ( N >= 1000000 && N <= 2000000 ) {
pigeons++
}
}
if (pigeons > pigeonholes) {
// one of the duplicates is between 1,000,000 and 2,000,000
// try again with a narrower range
}
Выбор того, насколько большой диапазон (ы) для проверки и сколько раз вы хотите прочитать 16 ГБ данных, зависит от вас :)
Что касается общей категории алгоритмов, то это проблема комбинаторики (математики о счете).
Если вы имеете в виду 32-битные положительные целые числа, я думаю, что эта проблема не требует какого-то специального алгоритма или трюка для решения. Простое наблюдение приведет к намеченному решению.
Мое наблюдение выглядит так: последовательный файл будет содержать только 32-битные целые числа (то есть от 0 до 2 ^ 31 - 1). Предположим, что вы поместили их все в этот файл уникальным образом, в итоге вы получите 2 ^ 31 строки. Вы можете видеть, что если вы поместите эти положительные целые числа еще раз, вы получите 2 ^ 31 * 2 строки, а это меньше 4 300 000 000.
Таким образом, ответом являются целые положительные числа от 0 до 2 ^ 31 - 1.
Отсортируйте целые числа и просмотрите их, чтобы увидеть, являются ли последовательные целые числа дубликатами. Если вы хотите сделать это в памяти, вам потребуется 16 ГБ памяти, что возможно на современных машинах. Если это невозможно, вы можете отсортировать числа с помощью сортировки слиянием и сохранения промежуточных массивов на диск.
Моей первой попыткой реализации было бы использование команд sort и uniq из unix.
