Программирование Жемчуг: найти одно целое число, по крайней мере, дважды

Question

Это в разделе 2.6 и проблеме 2, исходная проблема выглядит так:

"Учитывая последовательный файл, содержащий 4 300 000 000 32-разрядных целых чисел, как найти тот, который появляется по крайней мере дважды?"

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

Answer 1

Создайте битовый массив длиной 2^32 бита (инициализация в ноль), который будет иметь размер около 512 МБ и поместится в ОЗУ на любой современной машине.

Начните читать файл, int через int, проверьте бит с тем же индексом, что и значение int, если бит установлен, вы нашли дубликат, если он равен нулю, установите в единицу и продолжите следующий int из файла,

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

Answer 2

Принцип Pigeonhole - Если у вас есть N голубей в M Pigeonholes и 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 ГБ данных, зависит от вас:)

Что касается общей категории алгоритмов, то это проблема комбинаторики (математики о счетах).

Answer 3

Я также искал то же самое, и я наткнулся на эту [ссылку]: http://mikedebo.ca/2008/04/21/programming-pearls-solutions-to-exercises-2a-c/ думал поделиться тем же,

Answer 4

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

Мое наблюдение выглядит следующим образом: последовательный файл будет содержать только 32-битные целые числа (то есть от 0 до 2 ^ 31 - 1). Предположим, что вы поместили все их в этот файл уникальным образом, в итоге вы получите 2 ^ 31 строк. Вы можете видеть, что, если вы снова положите эти положительные целые числа, у вас будет 2 ^ 31 * 2 строки, и это будет меньше, чем 4 300 000 000.

Таким образом, ответом являются целые положительные целые числа в диапазоне от 0 до 2 ^ 31 - 1.

Answer 5

Сортируйте целые числа и просматривайте их, чтобы увидеть, являются ли последовательные целые числа дубликатами. Если вы хотите сделать это в памяти, это требует 16 ГБ памяти, что возможно на современных компьютерах. Если это невозможно, вы можете отсортировать числа с помощью сортировки слиянием и сохранить промежуточные массивы на диске.

Моя первая попытка реализации будет использовать sort а также uniq Команды из Unix.