Найти целое число не среди четырех миллиардов заданных

Question

Это вопрос интервью:

Учитывая входной файл с четырьмя миллиардами целых чисел, предоставьте алгоритм для генерации целого числа, которого нет в файле.Предположим, у вас есть 1 ГБ памяти.Следуйте тому, что вы сделали бы, если бы у вас было только 10 МБ памяти.

Мой анализ:

Размер файла 4 × 10 ⁹ × 4 байта = 16 ГБ.

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

Мое понимание (после прочтения всех ответов):

Предполагается, что речь идет о 32-разрядных целых числах.,Есть 2 ^ 32 = 4 * 10 ⁹ различных целых чисел.

Случай 1: у нас есть 1 ГБ = 1 * 10 ⁹ * 8 бит = 8 миллиардов битпамять.

Решение: если мы используем один бит, представляющий одно целое число, этого достаточно.нам не нужна сортировка.Реализация:

int radix = 8;
byte[] bitfield = new byte[0xffffffff/radix];
void F() throws FileNotFoundException{
    Scanner in = new Scanner(new FileReader("a.txt"));
    while(in.hasNextInt()){
        int n = in.nextInt();
        bitfield[n/radix] |= (1 << (n%radix));
    }

    for(int i = 0; i< bitfield.lenght; i++){
        for(int j =0; j<radix; j++){
            if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j);
        }
    }
}

Случай 2: 10 МБ памяти = 10 * 10 ⁶ * 8 бит = 80 миллионов бит

Решение: Для всех возможных 16-битные префиксы, есть 2 ^ 16, число целых = 65536, нам нужно 2 ^ 16 * 4 * 8 = 2 миллиона бит.Нам нужно построить 65536 ведер.Для каждого сегмента нам нужно 4 байта, в которых хранятся все возможности, поскольку в худшем случае все 4 миллиарда целых чисел принадлежат одному и тому же блоку.

1. Построить счетчик каждого блока через первый проход по файлу.
2. Просканируйте сегменты, найдите первого, у которого было меньше 65536 попаданий.
3. Создайте новые сегменты с высокими 16-битными префиксами, которые мы нашли на шаге 2 через второй проход файла
4. Сканирование сегментов, созданных в шаге 3, найдите первое, которое не имеет попадания.

Код очень похож на приведенный выше.

Вывод: Мыуменьшить объем памяти за счет увеличения пропускной способности файла.

---

Уточнение для тех, кто опаздывает: в вопросе не говорится, что в файле нет ровно одного целого числа -по крайней мере, это не так, как большинство людей интерпретируют это.Тем не менее, многие комментарии в ветке комментариев касаются этого варианта задачи.К сожалению, комментарий о том, что представил его в ветке комментариев, был позже удален его автором, так что теперь он выглядит так, как будто осиротевшие ответы на него просто неправильно поняли все.Это очень запутанно.К сожалению.

Answer 1

Вы можете использовать битовые флаги, чтобы отметить, присутствует ли целое число или нет.

После обхода всего файла отсканируйте каждый бит, чтобы определить, существует число или нет.

Предполагая каждыйцелое число - 32 бита, они будут удобно помещаться в 1 ГБ ОЗУ, если битовая маркировка выполнена.

Answer 2

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

Пусть все возможные целые числа будут в диапазоне от *От 1003 * до int_max и bool isNotInFile(integer) функция, которая возвращает истину, если файл не содержит определенного целого числа, и ложь в другом (сравнивая это определенное целое число с каждым целым числом в файле)

for (integer i = int_min; i <= int_max; ++i)
{
    if (isNotInFile(i)) {
        return i;
    }
}

Answer 3

Для ограничения памяти 10 МБ:

1. Преобразовать число в двоичное представление.
2. Создать двоичное дерево, где left = 0 и right = 1.
3. Вставьте каждое число в дереве, используя его двоичное представление.
4. Если число уже вставлено, листья будут уже созданы.

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

4 миллиарда число = 2 ^ 32, что означает, что 10 МБ может быть недостаточно.

РЕДАКТИРОВАТЬ

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

EDIT II

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

Answer 4

Я отвечу на 1 ГБ версию:

Недостаточно информации в вопросе, поэтому сначала я выскажу некоторые предположения:

Целое число составляет 32 бита с диапазоном от -2 147 483 648 до 2 147 483 647.

Псевдо-код:

var bitArray = new bit[4294967296];  // 0.5 GB, initialized to all 0s.

foreach (var number in file) {
    bitArray[number + 2147483648] = 1;   // Shift all numbers so they start at 0.
}

for (var i = 0; i < 4294967296; i++) {
    if (bitArray[i] == 0) {
        return i - 2147483648;
    }
}

Answer 5

Пока мы делаем творческие ответы, вот еще один.

Используйте внешнюю программу сортировки для числовой сортировки входного файла.Это будет работать для любого объема памяти, который у вас может быть (при необходимости будет использоваться хранилище файлов).Прочитайте отсортированный файл и выведите первое пропущенное число.

Answer 6

Исключение битов

Один из способов - исключить биты, однако на самом деле это может не дать результата (скорее всего, это не так). Psuedocode:

long val = 0xFFFFFFFFFFFFFFFF; // (all bits set)
foreach long fileVal in file
{
    val = val & ~fileVal;
    if (val == 0) error;
}

Число битов

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

Range Logic

Отслеживание списка упорядоченных диапазонов (упорядоченных по началу). Диапазон определяется структурой:

struct Range
{
  long Start, End; // Inclusive.
}
Range startRange = new Range { Start = 0x0, End = 0xFFFFFFFFFFFFFFFF };

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

Answer 7

Я думаю, что это решенная проблема (см. Выше), но есть интересный побочный случай, о котором следует помнить:

Если существует ровно 4 294 967 295 (2 ^ 32 - 1) 32-разрядных целых чисел без повторов, и поэтому отсутствует только одно, существует простое решение.

Начните промежуточную сумму с нуля, и для каждого целого числа в файле добавьте это целое число с 32-разрядным переполнением (эффективно, runningTotal = (runningTotal + nextInteger)% 4294967296). После завершения добавьте 4294967296/2 к промежуточному итогу, снова с 32-разрядным переполнением. Вычтите это из 4294967296, и в результате получите пропущенное целое число.

Проблема «только одно отсутствующее целое число» разрешима только с одним прогоном и только 64 битами ОЗУ, выделенными для данных (32 для промежуточного итога, 32 для чтения в следующем целом числе).

Следствие. Более общая спецификация чрезвычайно проста для сравнения, если нас не интересует, сколько битов должно иметь целочисленный результат. Мы просто генерируем достаточно большое целое число, которое не может содержаться в файле, который нам дан. Опять же, это занимает абсолютно минимальную оперативную память. Смотрите псевдокод.

# Grab the file size
fseek(fp, 0L, SEEK_END);
sz = ftell(fp);
# Print a '2' for every bit of the file.
for (c=0; c<sz; c++) {
  for (b=0; b<4; b++) {
    print "2";
  }
}

Answer 8

2 ^{128 * 10 18} + 1 (что (2 ⁸ ) ^{16 * 10 18} + 1) - не может ли быть универсальный ответ на сегодня?Это число, которое не может быть сохранено в файле 16 EB, что является максимальным размером файла в любой текущей файловой системе.

Answer 9

Как сказал Райан в основном, отсортируйте файл, а затем пройдитесь по целым числам, и когда значение будет пропущено, вы получите его:)

РЕДАКТИРОВАТЬ в downvoters: OP упомянул, что файл может быть отсортирован, так что это допустимый метод.

Answer 10

Если вы не принимаете 32-битное ограничение, просто верните случайно сгенерированное 64-битное число (или 128-битное, если вы пессимист).Вероятность столкновения составляет 1 in 2^64/(4*10^9) = 4611686018.4 (примерно 1 на 4 миллиарда).Вы были бы правы большую часть времени!

(шучу ... вроде.)