Алгоритм Вопрос о индексировании поиска файлов

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

Вопрос

Если файл содержит примерно 300 миллионов номеров социального обеспечения (9-значное число), найдите 9-значный номер, которого нет в файле. У вас есть неограниченное пространство на диске, но в вашем распоряжении всего 2 МБ оперативной памяти.

Ответ

На первом этапе мы создаем массив 2 ^ 16 целых чисел, который инициализируется до 0 и для каждого числа в файле, мы берем его 16 наиболее значимых битов для индексации в этот массив и увеличиваем число.

Так как в файле меньше 2 ^ 32 номеров, то в массиве должно быть (по крайней мере) одно число, меньшее 2 ^ 16. Это говорит нам о том, что среди возможных чисел с этими верхними битами есть хотя бы одно число.

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

Ответ 1

Чтобы упростить объяснение, скажем, у вас есть список двузначных чисел, где каждая цифра находится между 0 и 3, но вы не можете сэкономить 16 бит для запоминания для каждого из 16 возможных номеров, независимо от того, вы уже столкнулись с этим. Вы создаете массив a из 4 3-битных целых чисел, а в a[i] вы храните количество чисел с первой цифрой i, с которой вы столкнулись. (Двухбитовых целых чисел было бы недостаточно, потому что вам нужны значения 0, 4 и все числа между ними.)

Если у вас есть файл

00, 12, 03, 31, 01, 32, 02

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

4, 1, 0, 2

Теперь вы знаете, что все числа, начинающиеся с 0, находятся в файле, но для каждого из оставшихся, по крайней мере, один отсутствует. Пусть выбрать 1. Мы знаем, что есть хотя бы одно число, начинающееся с 1, которое не находится в файле. Итак, создайте массив из 4 бит, для каждого числа, начиная с 1, установите соответствующий бит и, в конце концов, выберите один из битов, который не был установлен, в нашем примере, если может быть 0. Теперь у нас есть решение: 10.

В этом случае использование этого метода - это разница между 12 бит и 16 бит. С вашими номерами это разница между 32 кБ и 119 МБ.

Ответ 2

В круглых выражениях у вас есть около 1/3 числа, которые могут существовать в файле, не предполагая дубликатов.

Идея состоит в том, чтобы сделать два прохода через данные. Относитесь к каждому номеру как к 32-битовому (без знака). В первом проходе держите отслеживание того, сколько чисел имеет одинаковое число в наиболее значительных 16 бит. На практике будет множество кодов, где есть нуль (например, все для 10-значных SSN, скорее всего, все те, у кого есть нуль для первой цифры, также отсутствуют). Но из диапазонов с ненулевым количеством отсчетов большинство из них не будет иметь 65536 записей, что было бы, если бы не было пробелов в диапазоне. Поэтому, немного позаботившись, вы можете выбрать один из диапазонов, чтобы сосредоточиться на втором проходе.

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

Предполагая, что вам не совсем повезло, выберите один с наименьшим количеством бит (или любой из них с менее чем 65536 записей); назовите его целевым диапазоном. Reset массив для всех нулей. Перечитайте данные. Если номер, который вы читаете, находится не в целевом диапазоне, игнорируйте его. Если он находится в диапазоне, запишите число, установив значение массива в 1 для младших 16-разрядных чисел. Когда вы прочитали весь файл, любое число с нулем в массиве представляет собой отсутствующий SSN.