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

Question

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

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

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

Answer 1

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

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

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

Answer 2

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

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

Answer 3

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

Answer 4

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

Моя первая попытка реализации заключается в использовании команд sort и uniq из unix.

Answer 5

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

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

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