Генерация целого числа, которого нет среди четырех миллиардов заданных

692

Мне дали этот вопрос интервью:

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

Мой анализ:

Размер файла составляет 4 × 10 9 × 4 байта = 16 ГБ.

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

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

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

Предполагая, что мы говорим о 32-разрядных целых числах, существует 2 32 = 4 * 10 9 различных целых чисел.

Случай 1: у нас 1 ГБ = 1 * 10 9 * 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 6 * 8 бит = 80 миллионов бит

Решение:

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

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

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

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


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

SecureFish
источник
32
@trashgod, неправильно. Для 4294967295 уникальных целых у вас останется 1 целое число. Чтобы найти его, вы должны сложить все целые числа и вычесть его из предварительно рассчитанной суммы всех возможных целых чисел.
Накилон
58
Это вторая «жемчужина» из «Программирования жемчуга», и я бы посоветовал вам прочитать всю дискуссию в книге. См. Books.google.com/…
Алок Сингхал,
8
@Richard 64-битное int будет более чем достаточно.
cftarnas
79
int getMissingNumber(File inputFile) { return 4; }( ссылка )
Джонни
14
Неважно, что вы не можете хранить сумму всех целых чисел от 1 до 2 ^ 32, потому что целочисленный тип в таких языках, как C / C ++, ВСЕГДА сохраняет свойства, такие как ассоциативность и коммуникативность. Это означает, что, хотя сумма не будет правильным ответом, если вы рассчитываете ожидаемое с переполнением, фактическую сумму с переполнением, а затем вычитаете, результат все равно будет правильным (при условии, что он сам не переполняется).
thedayturns

Ответы:

530

Предполагая, что "целое число" означает 32 бита : 10 МБ пространства более чем достаточно для подсчета количества чисел во входном файле с любым заданным 16-разрядным префиксом для всех возможных 16-разрядных префиксов за один проход через входной файл. По крайней мере, одно из ведер будет поражено менее чем 2 16 раз. Сделайте второй проход, чтобы узнать, какие из возможных чисел в этом сегменте уже используются.

Если это означает больше, чем 32 бита, но все еще ограниченного размера : сделайте, как указано выше, игнорируя все входные числа, которые выпадают из 32-битного диапазона (со знаком или без знака; на ваш выбор).

Если "целое число" означает математическое целое число : прочитайте один раз вход и отследите наибольшую длину числа самого длинного числа, которое вы когда-либо видели. Когда вы закончите, выведите максимум плюс одно случайное число, которое имеет еще одну цифру. (Одно из чисел в файле может быть bignum, для точного представления которого требуется более 10 МБ, но если входными данными является файл, то вы можете по крайней мере представить длину всего, что в него вписывается).

Хмахолм оставил Монику
источник
24
Отлично. Ваш первый ответ требует только 2 прохода через файл!
CorsiKa
47
10 МБ Бигнум? Это довольно экстремально.
Марк Рэнсом
12
@ Legate, просто пропустите большие цифры и ничего с ними не делайте. Так как вы все равно не собираетесь выводить слишком большое число, нет необходимости отслеживать, какой из них вы видели.
Хмакхольм покинул Монику
12
Преимущество решения 1 заключается в том, что вы можете уменьшить объем памяти за счет увеличения числа проходов.
Юсф
11
@ Барри: Приведенный выше вопрос не означает, что отсутствует только одно число. Там не сказано, что числа в файле тоже не повторяются. (Следуя
заданному
197

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

Если разрешены очень большие целые числа, то можно сгенерировать число, которое, вероятно, будет уникальным за время O (1). Псевдослучайное 128-разрядное целое число, такое как GUID, будет сталкиваться только с одним из четырех миллиардов существующих в наборе менее чем в одном из каждых 64 миллиардов миллиардов случаев.

Если целые числа ограничены 32 битами, то можно создать число, которое, вероятно, будет уникальным за один проход, используя намного меньше, чем 10 МБ. Вероятность того, что псевдослучайное 32-разрядное целое число столкнется с одним из 4 миллиардов существующих целых чисел, составляет около 93% (4e9 / 2 ^ 32). Вероятность того, что все 1000 псевдослучайных целых будут сталкиваться, составляет менее одного на 12 000 миллиардов миллиардов миллиардов (вероятность одного столкновения - 1000). Таким образом, если программа поддерживает структуру данных, содержащую 1000 псевдослучайных кандидатов, и перебирает известные целые числа, исключая совпадения из кандидатов, то почти наверняка найдется хотя бы одно целое число, которого нет в файле.

Бен Хейли
источник
32
Я уверен, что целые числа ограничены. Если бы это было не так, то даже начинающий программист мог бы подумать об алгоритме «сделать один проход через данные, чтобы найти максимальное число, и добавить к нему 1»
Адриан Петреску,
12
Буквальное предположение, что случайный вывод, вероятно, не даст вам много очков в интервью
Брайан Гордон
6
@ Адриан, ваше решение кажется очевидным (и оно было для меня, я использовал его в своем собственном ответе), но это не очевидно для всех. Это хороший тест, чтобы увидеть, можете ли вы найти очевидные решения или собираетесь слишком усложнить все, к чему прикасаетесь.
Марк Рэнсом
19
@Brian: я думаю, что это решение является и творческим, и практичным. Я бы, например, дал бы много уважения за этот ответ.
Ричард Х
6
Ах, здесь лежит грань между инженерами и учеными. Отличный ответ, Бен!
TrojanName
142

Подробное обсуждение этой проблемы обсуждалось в книге Джона Бентли «Колонка 1. Сломать устрицу». Программирование «Жемчуг» Эддисон-Уэсли, с. 3-10.

Бентли обсуждает несколько подходов, в том числе внешнюю сортировку, сортировку слиянием с использованием нескольких внешних файлов и т. Д. Но лучший метод, который предлагает Бентли, - это однопроходный алгоритм с использованием битовых полей , который он шутливо называет «сортировкой по череде» :) Приходя к проблеме, 4 миллиарда числа могут быть представлены в:

4 billion bits = (4000000000 / 8) bytes = about 0.466 GB

Код для реализации набора битов прост: (взят со страницы решений )

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];

void set(int i) {        a[i>>SHIFT] |=  (1<<(i & MASK)); }
void clr(int i) {        a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int  test(int i){ return a[i>>SHIFT] &   (1<<(i & MASK)); }

Алгоритм Бентли делает один проход по файлу, set устанавливает соответствующий бит в массиве и затем проверяет этот массив, используя testмакрос выше, чтобы найти пропущенное число.

Если объем доступной памяти меньше 0,466 ГБ, Bentley предлагает алгоритм k-pass, который делит входные данные на диапазоны в зависимости от доступной памяти. Возьмем очень простой пример: если был доступен только 1 байт (то есть память для обработки 8 чисел), а диапазон был от 0 до 31, мы делим это на диапазоны от 0 до 7, 8-15, 16-22 и т. Д. и обрабатывать этот диапазон в каждом из32/8 = 4 проходов.

НТН.

vine'th
источник
12
Я не знаю книгу, но нет причин называть ее «Wonder Sort», так как это просто сортировка ведрами с 1-битным счетчиком.
Флоло
3
Хотя этот код более переносимый, он будет уничтожен кодом, написанным для использования аппаратно-поддерживаемых векторных инструкций . Я думаю, что в некоторых случаях gcc может автоматически преобразовывать код в векторные операции.
Брайан Гордон
3
@ Брайан: Я не думаю, что Джон Бентли разрешил такие вещи в своей книге об алгоритмах.
Дэвид Хеффернан
8
@BrianGordon, время, проведенное в оперативной памяти, будет незначительным по сравнению со временем, потраченным на чтение файла. Забудьте об оптимизации.
Ян
1
@BrianGordon: Или вы говорили о конце цикла, чтобы найти первый неустановленный бит? Да, векторы будут ускорять это, но зацикливаясь на битовом поле с 64-битными целыми числами, ища то, != -1которое по-прежнему будет насыщать пропускную способность памяти, работающую на одном ядре (это SIMD-в-регистре, SWAR, с битами в качестве элементов). (Для последних разработок Intel / AMD). Вам нужно только выяснить, какой бит не установлен после того, как вы найдете 64-битное местоположение, содержащее его. (И для этого вы можете not / lzcnt.) Справедливо отметить, что циклическое выполнение однобитового теста может быть плохо оптимизировано.
Питер Кордес
120

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

Андрис
источник
6
Если наибольшее число в файле не будет max int, вы просто переполнитесь
KBusc
Каков будет размер этого файла в реальной программе, которой может потребоваться сгенерировать новое целое число и добавить его в файл «используемые целые числа» 100 раз?
Майкл
2
Я думал об этом. Предполагая, что intэто 32биты, просто вывод 2^64-1. Выполнено.
Ималлетт
1
Если это одно целое на строку tr -d '\n' < nums.txt > new_num.txt:: D
Шон
56

Для варианта 1 ГБ ОЗУ вы можете использовать битовый вектор. Вам нужно выделить 4 миллиарда битов == 500 МБ байтового массива. Для каждого числа, считанного с входа, установите соответствующий бит на «1». Как только вы закончите, переберите биты и найдите первый, который все еще равен 0. Его индекс является ответом.

Итай Маман
источник
4
Диапазон чисел на входе не указан. Как работает этот алгоритм, если входные данные состоят из всех четных чисел от 8 до 16 миллиардов?
Марк Рэнсом
27
@Mark, просто игнорируйте входы, выходящие за пределы диапазона 0..2 ^ 32. В любом случае вы не собираетесь выводить какие-либо из них, поэтому нет необходимости помнить, какой из них следует избегать.
Хмакхольм покинул Монику
@ Отметьте любой алгоритм, который вы используете, чтобы определить, как 32-битная строка отображается в реальное число. Процесс все тот же. Разница лишь в том, как вы печатаете его как действительное число на экране.
CorsiKa
4
Вместо итерации вы можете использовать bitSet.nextClearBit(0): download.oracle.com/javase/6/docs/api/java/util/…
starblue
3
Было бы полезно упомянуть, что независимо от диапазона целых чисел по крайней мере один бит гарантированно будет равен 0 в конце прохода. Это связано с принципом голубиных отверстий.
Рафал Доугирд
46

Если они являются 32-разрядными целыми числами (вероятно, из выбора ~ 4 миллиардов чисел, близких к 2 32 ), ваш список из 4 миллиардов чисел займет не более 93% возможных целых чисел (4 * 10 9 / (2 32 ) ). Поэтому, если вы создаете битовый массив из 2 32 бит, каждый из которых инициализируется нулем (что займет 2 29 байт ~ 500 МБ ОЗУ; запомните байт = 2 3 бита = 8 бит), прочитайте список целых чисел и для каждого типа int установите соответствующий элемент массива битов от 0 до 1; а затем прочитайте ваш битовый массив и верните первый бит, который все еще равен 0

В случае, когда у вас меньше оперативной памяти (~ 10 МБ), это решение нужно немного изменить. 10 МБ ~ 83886080 битов все еще достаточно для создания битового массива для всех чисел от 0 до 83886079. Таким образом, вы можете прочитать свой список целых чисел; и только записи #, которые находятся между 0 и 83886079 в вашем битовом массиве. Если числа распределены случайным образом; с подавляющей вероятностью (отличается на 100% примерно на 10 -2592069 ) вы найдете пропущенный int). Фактически, если вы выбираете только числа от 1 до 2048 (только с 256 байтами оперативной памяти), вы все равно найдете пропущенное число в подавляющем проценте (99,9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999995%) времени.

Но скажем, вместо того, чтобы иметь около 4 миллиардов чисел; у вас было что-то вроде 2 32 - 1 цифр и менее 10 МБ ОЗУ; поэтому любой небольшой диапазон целых имеет небольшую вероятность не содержать числа.

Если вам было гарантировано, что каждое целое число в списке уникально, вы можете сложить числа и вычесть сумму с одним пропущенным # до полной суммы (½) (2 32 ) (2 32 - 1) = 9223372034707292160, чтобы найти пропущенное целое число , Однако, если int встречался дважды, этот метод потерпит неудачу.

Тем не менее, вы всегда можете разделить и победить. Наивным методом было бы прочитать массив и подсчитать количество чисел, которые находятся в первой половине (от 0 до 2 31 -1) и во второй половине (2 31 , 2 32 ). Затем выберите диапазон с меньшим числом чисел и повторите деление этого диапазона пополам. (Скажем, если в (2 31 , 2 32 ) чисел было на два меньше , то при следующем поиске будет подсчитано число в диапазоне (2 31 , 3 * 2 30 -1), (3 * 2 30 , 2 32 ). повторять до тех пор, пока вы не найдете диапазон с нулевыми числами, и у вас есть свой ответ. Должно пройти O (LG N) ~ 32 чтения массива.

Этот метод был неэффективным. Мы используем только два целых числа на каждом шаге (или около 8 байтов оперативной памяти с 4-байтовым (32-битным) целым числом). Лучшим методом было бы разделить на sqrt (2 32 ) = 2 16 = 65536 бинов, каждый с 65536 числами в бине. Каждый бин требует 4 байта для хранения своего счетчика, поэтому вам нужно 2 18 байт = 256 кБ. Таким образом, bin 0 равен (от 0 до 65535 = 2 16 -1), bin 1 равен (2 16 = 65536 до 2 * 2 16 -1 = 131071), bin 2 равен (2 * 2 16 = от 131072 до 3 * 2 16 - 1 = 196607). В Python у вас будет что-то вроде:

import numpy as np
nums_in_bin = np.zeros(65536, dtype=np.uint32)
for N in four_billion_int_array:
    nums_in_bin[N // 65536] += 1
for bin_num, bin_count in enumerate(nums_in_bin):
    if bin_count < 65536:
        break # we have found an incomplete bin with missing ints (bin_num)

Прочитайте список целых чисел ~ 4 миллиарда; и посчитайте, сколько целых чисел попадает в каждый из 2 16 бинов, и найдите incomplete_bin, в котором нет всех 65536 чисел. Затем вы снова читаете список из 4 миллиардов целых чисел; но на этот раз заметьте только когда целые числа находятся в этом диапазоне; листать немного, когда вы их найдете.

del nums_in_bin # allow gc to free old 256kB array
from bitarray import bitarray
my_bit_array = bitarray(65536) # 32 kB
my_bit_array.setall(0)
for N in four_billion_int_array:
    if N // 65536 == bin_num:
        my_bit_array[N % 65536] = 1
for i, bit in enumerate(my_bit_array):
    if not bit:
        print bin_num*65536 + i
        break
доктор джимбоб
источник
3
Такой потрясающий ответ. Это на самом деле будет работать; и имеет гарантированные результаты.
Джонатан Дикинсон
@dr jimbob, что если в корзине есть только одно число, и у этого числа есть 65535 дубликатов? Если это так, корзина все равно будет насчитывать 65536, но все 65536 чисел совпадают.
Олкотт
@Alcott - я предположил, что у вас 2 ^ 32-1 (или меньше) чисел, поэтому по принципу «голубиных ям» вы гарантированно получите одну ячейку с количеством импульсов меньше 65536 для более подробной проверки. Мы пытаемся найти только одно пропущенное целое число, а не все. Если у вас было 2 ^ 32 или более чисел, вы не можете гарантировать пропущенное целое число и не сможете использовать этот метод (или у вас есть гарантия с самого начала, что пропущенное целое число). В таком случае лучшим вариантом будет грубая сила (например, прочитайте массив 32 раза; проверьте первые 65536 # в первый раз; и остановитесь, как только ответ будет найден).
Доктор Джимбоб
Хеннинг ранее опубликовал хитрый метод «верхний 16 / нижний 16»: stackoverflow.com/a/7153822/224132 . Мне понравилась идея сложения для уникального набора целых чисел, в котором отсутствует ровно один член.
Питер Кордес
3
@PeterCordes - Да, решение Хеннинга предшествует моему, но я думаю, что мой ответ все еще полезен (прорабатывая несколько вещей более подробно). Тем не менее, Джон Бентли в своей книге «Программирование жемчуга» предложил вариант с несколькими проходами для этой проблемы (см. Ответ Винниса) задолго до того, как возник стекопоток (не то, чтобы я утверждал, что кто-то из нас сознательно украл оттуда или что Бентли был первым, кто проанализировать эту проблему - это достаточно естественное решение для разработки). Два прохода кажутся наиболее естественными, когда ограничение состоит в том, что у вас больше не хватает памяти для решения за 1 проход с гигантским битовым массивом.
р джимбоб
37

Зачем делать это так сложно? Вы спрашиваете целое число, которого нет в файле?

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

Риск попадания в maxint или что-либо еще отсутствует, поскольку в соответствии с правилами нет ограничений на размер целого числа или числа, возвращаемого алгоритмом.

Пит
источник
4
Это работало бы, если бы в файле не было max int, что вполне возможно ...
PearsonArtPhoto
13
В правилах не указывается, что это 32-битный или 64-битный или что-то еще, поэтому, согласно указанным правилам, не существует max int. Целое число - это не компьютерный термин, это математический термин, определяющий положительные или отрицательные целые числа.
Пит
Верно, но нельзя предположить, что это 64-битное число или что кто-то просто не прокрался бы в число max int просто, чтобы запутать такие алгоритмы.
PearsonArtPhoto
24
Полное понятие «max int» недопустимо в контексте, если не указан язык программирования. например, посмотрите на определение Python длинного целого числа. Это безгранично. Там нет крыши. Вы всегда можете добавить один. Вы предполагаете, что это реализуется на языке, который имеет максимально допустимое значение для целого числа.
Пит
32

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

  1. Начните с допустимого диапазона чисел, 0до 4294967295.

  2. Рассчитайте среднюю точку.

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

  4. Если никакие числа не были равны, все готово. Число средней точки является ответом.

  5. В противном случае выберите диапазон с наименьшим числом и повторите с шага 2 этот новый диапазон.

Для этого потребуется до 32 линейных сканирований файла, но для хранения диапазона и количества будет использовано всего несколько байтов памяти.

По сути, это то же самое, что и решение Хеннинга , за исключением того, что он использует два контейнера вместо 16 КБ.

Хаммар
источник
2
Это то, с чего я начал, прежде чем начал оптимизировать по заданным параметрам.
Хмаколм покинул Монику
@ Хеннинг: Круто. Это хороший пример алгоритма, в котором легко настроить пространственно-временной компромисс.
хаммар
@hammar, но что, если эти числа появляются несколько раз?
Олкотт
@Alcott: тогда алгоритм выберет более плотную ячейку вместо более разреженной ячейки, но по принципу голубиного отверстия он никогда не сможет выбрать полностью заполненную ячейку. (Меньшее из этих двух значений всегда будет меньше, чем диапазон корзины.)
Питер Кордес
27

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


Есть ≈4,3 миллиарда 32-битных целых. Мы не знаем, как они распределяются в файле, но наихудший случай - это случай с самой высокой энтропией Шеннона: равное распределение. В этом случае вероятность того, что одно целое число не появится в файле, равна

((2³²-1) / 2³²) ⁴ ⁰⁰⁰ ⁰⁰⁰ ⁰⁰⁰ ≈ .4

Чем ниже энтропия Шеннона, тем выше эта вероятность в среднем, но даже в этом наихудшем случае у нас есть шанс на 90% найти непериодическое число после 5 догадок со случайными целыми числами. Просто создайте такие числа с помощью псевдослучайного генератора, сохраните их в списке. Затем прочитайте int за int и сравните его со всеми вашими догадками. Когда есть совпадение, удалите эту запись списка. После того, как вы просмотрели весь файл, скорее всего, у вас останется более одного предположения. Используйте любой из них. В редком (10%, даже в худшем случае) событии без догадок остаётся получить новый набор случайных целых чисел, возможно, больше на этот раз (10-> 99%).

Потребление памяти: несколько десятков байт, сложность: O (n), накладные расходы: не учитывается, так как большая часть времени будет потрачена на неизбежные обращения к жесткому диску, а не на сравнение целых чисел в любом случае.


На самом деле наихудший случай, когда мы не предполагаем статическое распределение, состоит в том, что каждое целое число встречается макс. один раз, потому что тогда в файле не встречается только 1 - 4000000000 / 2³² ≈ 6% всех целых чисел. Так что вам понадобится еще несколько догадок, но это все равно не будет стоить вредного количества памяти.

leftaroundabout
источник
5
Я рад, что кто-то еще подумал об этом, но почему это здесь, внизу? Это 1-проходный алгоритм… 10 МБ достаточно для предположения 2,5 М, и 93% ^ 2,5M ≈ 10 ^ -79000 - это поистине ничтожно малая вероятность повторного сканирования. Из-за накладных расходов бинарного поиска, он идет быстрее, если вы используете меньше догадок! Это оптимально как во времени, так и в пространстве.
Potatoswatter
1
@Potatoswatter: хорошо, что вы упомянули бинарный поиск. Это, вероятно, не стоит накладных расходов при использовании только 5 догадок, но это, безусловно, на 10 или более. Вы могли бы даже сделать 2 M догадки, но затем вы должны сохранить их в хэш-наборе, чтобы получить O (1) для поиска.
оставлено около
1
@Potatoswatter Эквивалентный ответ Бена Хейли вверху
Брайан Гордон
1
Мне нравится этот подход, но я бы предложил улучшение экономии памяти: если у вас есть N битов индексированного хранилища плюс некоторое постоянное хранилище, определите настраиваемую обратимую 32-битную функцию скремблирования (перестановку), выберите произвольную перестановку и очистите все индексированные биты. Затем прочитайте каждое число из файла, зашифруйте его, и, если результат меньше N, установите соответствующий бит. Если какой-либо бит не установлен в конце файла, измените функцию скремблирования на его индекс. Имея 64 КБ памяти, можно эффективно проверить доступность более 512 000 номеров за один проход.
суперкат
2
Конечно, в этом алгоритме наихудший случай - это случай, когда числа были созданы тем же генератором случайных чисел, который вы используете. Предполагая, что вы можете гарантировать, что это не так, вашей лучшей тактикой является использование линейного конгруэнтного генератора случайных чисел для генерации вашего списка, чтобы вы проходили через пространство чисел псевдослучайным образом. Это означает, что если вы каким-то образом потерпите неудачу, вы можете продолжать генерировать числа, пока не охватите весь диапазон целых чисел (или нашли пробел), даже не дублируя свои усилия.
Деви Морган,
25

Если в диапазоне [0, 2 ^ x - 1] отсутствует одно целое число, просто скопируйте их все вместе. Например:

>>> 0 ^ 1 ^ 3
2
>>> 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 6 ^ 7
5

(Я знаю, что это не дает точного ответа на вопрос , но это хороший ответ на очень похожий вопрос.)

rfrankel
источник
1
Да, легко доказать [ ], что работает, когда отсутствует одно целое число, но часто происходит сбой, если пропущено более одного. Например, 0 ^ 1 ^ 3 ^ 4 ^ 6 ^ 7равен 0. [ Запись 2 x для 2-й степени и a ^ b для xor b, xor всех k <2 x равно нулю - k ^ ~ k = (2 ^ x) - 1 для k <2 ^ (x-1) и k ^ ~ k ^ j ^ ~ j = 0, когда j = k + 2 ** (x-2) - так что значение xor для всех, кроме одного, является значением пропавшего]
Джеймс Уолдби - jwpat7
2
Как я упоминаю в комментарии к ответу ircmaxell: Проблема не говорит, что «отсутствует одно число», она говорит, что нужно найти число, не включенное в 4 миллиарда чисел в файле. Если мы предположим 32-битные целые числа, то в файле может отсутствовать около 300 миллионов чисел. Вероятность того, что xor чисел, соответствующих отсутствующему числу, составляет всего около 7%.
Джеймс Уолдби - jwpat7
Это тот ответ, о котором я думал, когда впервые прочитал вопрос, но при ближайшем рассмотрении я думаю, что этот вопрос более двусмысленный, чем этот. К вашему сведению, это вопрос, о котором я думал: stackoverflow.com/questions/35185/…
Ли Нетертон
18

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

Павел
источник
4
Вероятно, с более чем 90% возможных значений ваш фильтр Блума, вероятно, должен будет выродиться в битовое поле, поэтому многие ответы уже используют. В противном случае вы просто получите бесполезную полностью заполненную цепочку битов.
Кристофер Кройциг
@Christopher Мое понимание фильтров Bloom заключается в том, что вы не получите заполненный битрейт, пока не достигнете 100%
Пол
... в противном случае вы получите ложные негативы.
Пол
@Paul заполненный массив битов дает вам ложные срабатывания, которые разрешены. В этом случае фильтр Блума, скорее всего, выродится в тот случай, когда решение, которое будет отрицательным, возвращает ложное срабатывание.
Атайлор
1
@Paul: Вы можете получить заполненный битрейр, как только количество хеш-функций, умноженное на количество записей, станет равным длине вашего поля. Конечно, это был бы исключительный случай, но вероятность возрастет довольно быстро.
Кристофер Кройциг
17

Исходя из текущей формулировки исходного вопроса, самое простое решение:

Найдите максимальное значение в файле, затем добавьте 1 к нему.

oosterwal
источник
5
Что если MAXINT включен в файл?
Петр Пеллер
@Petr Peller: библиотека BIGINT по существу снимет ограничения на целочисленный размер.
oosterwal
2
@oosterwal, если этот ответ был разрешен, вам даже не нужно читать файл - просто напечатайте как можно большее число.
Накилон
1
@oosterwal, если ваше случайное огромное число было наибольшим, которое вы могли напечатать, и оно было в файле, то эта задача не может быть решена.
Накилон
3
@Nakilon: +1 Ваша точка зрения принята. Это примерно эквивалентно вычислению общего количества цифр в файле и печати числа с таким количеством цифр.
oosterwal
14

Используйте BitSet. 4 миллиарда целых чисел (при условии до 2 ^ 32 целых чисел), упакованных в BitSet со скоростью 8 на байт, составляют 2 ^ 32/2 ^ 3 = 2 ^ 29 = приблизительно 0,5 Гб.

Чтобы добавить немного больше деталей - каждый раз, когда вы читаете число, установите соответствующий бит в BitSet. Затем выполните обход BitSet, чтобы найти первый номер, которого нет. На самом деле, вы можете сделать это так же эффективно, многократно выбирая случайное число и проверяя его наличие.

На самом деле BitSet.nextClearBit (0) сообщит вам первый не установленный бит.

Если посмотреть на API-интерфейс BitSet, он, по-видимому, поддерживает только 0..MAX_INT, поэтому вам может понадобиться 2 набора BitSet - один для номеров + и один для номеров - но требования к памяти не меняются.

DTY
источник
1
Или, если вы не хотите использовать BitSet... попробуйте массив битов. Делает то же самое;)
jcolebrand
12

Если ограничения по размеру нет, самый быстрый способ - взять длину файла и сгенерировать длину файла + 1 число случайных цифр (или просто «11111 ...»). Преимущество: вам даже не нужно читать файл, и вы можете минимизировать использование памяти почти до нуля. Недостаток: вы напечатаете миллиарды цифр.

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

ВСЗ
источник
11

Если мы предположим, что диапазон чисел всегда будет равен 2 ^ n (четная степень 2), то будет работать исключающее-или (как показано на другом плакате). Насколько, давайте докажем это:

Теория

При наличии любого целого диапазона на основе 0, в котором есть 2^nэлементы с одним отсутствующим элементом, вы можете найти этот отсутствующий элемент, просто скопировав известные значения вместе, чтобы получить пропущенное число.

Доказательство

Давайте посмотрим на n = 2. Для n = 2 мы можем представить 4 уникальных целых числа: 0, 1, 2, 3. Они имеют битовую комбинацию:

  • 0 - 00
  • 1 - 01
  • 2 - 10
  • 3 - 11

Теперь, если мы посмотрим, каждый бит установлен ровно дважды. Следовательно, поскольку оно установлено четное число раз, и исключающее число или число выдаст 0. Если пропущено одно число, исключающее число или выдаст число, которое при исключении числа с отсутствующим числом приведет к 0. Следовательно, пропущенный номер и полученный в результате эксклюзивный номер в точности совпадают. Если мы удалим 2, результирующий xor будет10 (или 2).

Теперь давайте посмотрим на n + 1. Давайте назовем, сколько раз установлен каждый бит n, xи сколько раз установлен каждый бит n+1 y. Значение yбудет равно, y = x * 2потому что есть xэлементы с n+1битом, установленным в 0, и xэлементы с n+1битом, установленным в 1. И так 2xкак всегда будет четным, n+1каждый бит будет всегда установлен четным числом раз.

Поэтому, поскольку n=2работает и n+1работает, метод xor будет работать для всех значений n>=2.

Алгоритм для 0 основанных диапазонов

Это довольно просто. Он использует 2 * n бит памяти, поэтому для любого диапазона <= 32 будут работать 2 32-битных целых числа (без учета любой памяти, используемой дескриптором файла). И это делает один проход файла.

long supplied = 0;
long result = 0;
while (supplied = read_int_from_file()) {
    result = result ^ supplied;
}
return result;

Алгоритм для произвольных диапазонов

Этот алгоритм будет работать для диапазонов от любого начального числа до любого конечного числа, при условии, что общий диапазон равен 2 ^ n ... Это в основном переопределяет диапазон, чтобы иметь минимум на 0. Но это действительно требует 2 прохода через файл (первый для получения минимума, второй для вычисления отсутствующего целого).

long supplied = 0;
long result = 0;
long offset = INT_MAX;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    result = result ^ (supplied - offset);
}
return result + offset;

Произвольные диапазоны

Мы можем применить этот модифицированный метод к набору произвольных диапазонов, поскольку все диапазоны будут пересекать степень 2 ^ n хотя бы один раз. Это работает, только если пропущен один бит. Требуется 2 прохода несортированного файла, но каждый раз он находит пропущенное число:

long supplied = 0;
long result = 0;
long offset = INT_MAX;
long n = 0;
double temp;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    n++;
    result = result ^ (supplied - offset);
}
// We need to increment n one value so that we take care of the missing 
// int value
n++
while (n == 1 || 0 != (n & (n - 1))) {
    result = result ^ (n++);
}
return result + offset;

По сути, повторно основывает диапазон около 0. Затем он подсчитывает количество несортированных значений, которые нужно добавить, когда вычисляет исключающее-или. Затем он добавляет 1 к количеству несортированных значений, чтобы позаботиться о пропущенном значении (подсчитать пропущенное). Затем продолжайте сохранять значение n, увеличивая его на 1 каждый раз, пока n не станет степенью 2. Затем результат возвращается к исходному основанию. Выполнено.

Вот алгоритм, который я тестировал в PHP (используя массив вместо файла, но с той же концепцией):

function find($array) {
    $offset = min($array);
    $n = 0;
    $result = 0;
    foreach ($array as $value) {
        $result = $result ^ ($value - $offset);
        $n++;
    }
    $n++; // This takes care of the missing value
    while ($n == 1 || 0 != ($n & ($n - 1))) {
        $result = $result ^ ($n++);
    }
    return $result + $offset;
}

Поданный в массив с любым диапазоном значений (я тестировал включая отрицательные значения) с одним в этом диапазоне, который отсутствует, он каждый раз находил правильное значение.

Другой подход

Поскольку мы можем использовать внешнюю сортировку, почему бы просто не проверить пробел? Если мы предположим, что файл отсортирован до запуска этого алгоритма:

long supplied = 0;
long last = read_int_from_file();
while (supplied = read_int_from_file()) {
    if (supplied != last + 1) {
        return last + 1;
    }
    last = supplied;
}
// The range is contiguous, so what do we do here?  Let's return last + 1:
return last + 1;
ircmaxell
источник
3
Проблема не говорит «отсутствует один номер», она говорит, чтобы найти число, не включенное в 4 миллиарда чисел в файле. Если мы предположим 32-битные целые числа, то в файле может отсутствовать около 300 миллионов чисел. Вероятность того, что xor чисел, соответствующих отсутствующему числу, составляет всего около 7%.
Джеймс Уолдби - jwpat7
Если у вас есть непрерывный, но отсутствующий единичный диапазон, который не начинается с нуля, добавьте вместо xor. sum(0..n) = n*(n+1)/2, Так missing = nmax*(nmax+1)/2 - nmin*(nmin+1)/2 - sum(input[]). (Идея суммирования из ответа @ Hammar.)
Питер Кордес
9

Вопрос с подвохом, если только он не процитирован неправильно. Просто прочитайте файл один раз, чтобы получить максимальное целое число n, и вернитесь n+1.

Конечно, вам потребуется план резервного копирования на случай n+1переполнения целого числа.

Марк Рэнсом
источник
3
Вот решение, которое работает ... кроме случаев, когда это не так. Полезно! :-)
dty
Если это не было указано неправильно, вопрос не ограничивал тип целого числа или даже используемый язык. Многие современные языки имеют целые числа, ограниченные только доступной памятью. Если наибольшее целое число в файле> 10 МБ, то, к сожалению, задача невозможна для второго случая. Мое любимое решение.
Юрген Штробель
9

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

void maxNum(ulong filesize)
{
    ulong bitcount = filesize * 8; //number of bits in file

    for (ulong i = 0; i < bitcount; i++)
    {
        Console.Write(9);
    }
}

Должно вывести 10 bitcount - 1 , что всегда будет больше 2 bitcount . Технически, число, которое вам нужно побить, равно 2 битам - (4 * 10 9 - 1) , поскольку вы знаете, что в файле есть (4 миллиарда - 1) других целых чисел, и даже при идеальном сжатии они займут как минимум один бит каждый.

Джастин морган
источник
Почему не просто Console.Write( 1 << bitcount )вместо петли? Если в файле n битов, то любое (_n_ + 1) -битное число с ведущей 1 абсолютно гарантированно будет больше.
Эммет
@Emmet - это может привести к переполнению целого числа, если только файл не будет меньше размера типа int (4 байта в C #). C ++ может позволить вам использовать что-то большее, но C #, похоже, не допускает ничего, кроме 32-битных целочисленных значений с <<оператором. В любом случае, если вы не свернете свой собственный гигантский целочисленный тип, это будет очень маленький размер файла. Демонстрация: rextester.com/BLETJ59067
Джастин Морган
8
  • Самый простой подход - найти минимальное число в файле и вернуть на 1 меньше. При этом используется память O (1) и время O (n) для файла из n чисел. Тем не менее, он потерпит неудачу, если диапазон номеров будет ограничен, что может сделать мин-1 не числом.

  • Простой и понятный метод использования растрового изображения уже упоминался. Этот метод использует O (n) время и память.

  • Также был упомянут двухпроходный метод с 2 ^ 16 подсчетами. Он читает 2 * n целых чисел, поэтому использует время O (n) и память O (1), но не может обрабатывать наборы данных с более чем 2 ^ 16 числами. Тем не менее, он легко расширяется до (например) 2 ^ 60 64-разрядных целых чисел, выполняя 4 прохода вместо 2, и легко адаптируется к использованию крошечной памяти, используя только столько бинов, сколько умещается в памяти, и соответственно увеличивая количество проходов в В этом случае время выполнения больше не O (n), а вместо этого O (n * log n).

  • Метод XOR'ирования всех чисел вместе, упомянутый до сих пор rfrankel и в длину ircmaxell, отвечает на вопрос, заданный в stackoverflow # 35185 , как указал ltn100. Он использует O (1) хранилище и O (n) время выполнения. Если на данный момент мы предполагаем 32-разрядные целые числа, XOR имеет 7% вероятности получения различного числа. Обоснование: дано ~ 4G различных чисел XOR'd вместе, и ок. 300M отсутствует в файле, число установленных битов в каждой битовой позиции имеет равную вероятность быть нечетным или четным. Таким образом, 2 ^ 32 числа имеют равную вероятность возникновения как результат XOR, из которых 93% уже находятся в файле. Обратите внимание, что если числа в файле не все различны, вероятность успеха метода XOR возрастает.

Джеймс Уолдби - jwpat7
источник
7

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

Прочитайте первый номер. Дополните его нулями, пока не получите 4 миллиарда бит. Если первый (старший разряд) бит равен 0, выведите 1; else выводит 0. (На самом деле вам не нужно вводить левую клавиатуру: вы просто выводите 1, если в числе недостаточно битов.) Сделайте то же самое со вторым числом, за исключением использования его второго бита. Продолжить через файл таким образом. Вы будете выводить 4-миллиардный бит по одному биту за раз, и это число не будет таким, как в файле. Доказательство: это было то же самое, что и n-е число, тогда они согласились бы с n-ным битом, но не строят.

Джонатан Амстердам
источник
+1 за креативность (и наименьший выход наихудшего случая для однопроходного решения пока).
Хмакхольм покинул Монику
Но диагонали нет 4 миллиардов, есть только 32. В итоге вы получите 32-битное число, которое отличается от первых 32 чисел в списке.
Брайан Гордон
@ Хеннинг Это едва ли один проход; вам все еще нужно конвертировать из унарного в бинарный. Редактировать: Ну, я думаю, это один проход по файлу. Ничего.
Брайан Гордон
@ Брайан, где здесь что-то "одинаковое"? Ответ строит двоичный ответ один бит за раз, и он читает входной файл только один раз, делая его за один проход. (Если требуется десятичный вывод, все становится проблематично - тогда вам, вероятно, лучше построить одну десятичную цифру на три входных числа и принять 10% -ное увеличение в журнале выходного числа).
Хмахолм покинул Монику
2
@Henning Проблема не имеет смысла для произвольно больших целых чисел, потому что, как отмечали многие люди, тривиально просто найти наибольшее число и добавить его, или создать очень длинное число из самого файла. Это решение по диагонализации особенно неуместно, потому что вместо разветвления на iбит можно просто вывести 1 бит 4 миллиарда раз и добавить 1 в конце. Я в порядке, имея в алгоритме произвольно большие целые числа , но я думаю, что проблема заключается в выводе недостающего 32-разрядного целого числа. Это просто не имеет никакого смысла.
Брайан Гордон
6

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

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

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

Шамим Хафиз
источник
0,5 Гб, если вы не переопределили байт в 4 бита ;-)
dty
2
@dty Я думаю, он имеет в виду «удобно», так как в 1Gb будет много места.
CorsiKa
6

Уберите из файла пробел и нечисловые символы и добавьте 1. Теперь ваш файл содержит одно число, отсутствующее в исходном файле.

От Reddit от Carbonetc.

Ashley
источник
Любить это! Хотя это не совсем тот ответ, который он искал ...: D
Иоганн дю Туа
6

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

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

for (integer i = int_min; i <= int_max; ++i)
{
    if (isNotInFile(i)) {
        return i;
    }
}
градус
источник
Вопрос был именно об алгоритме isNotInFileфункции. Пожалуйста, убедитесь, что вы понимаете вопрос, прежде чем ответить.
Aleks G
2
нет, вопрос был "какое целое число отсутствует в файле", а не "целое число x в файле". функция для определения ответа на последний вопрос может, например, просто сравнить каждое целое число в файле с целым числом и вернуть true в совпадении.
град
Я думаю, что это законный ответ. За исключением ввода / вывода, вам нужно только одно целое число и флаг bool.
Брайан Гордон
@ Алекс Г - не понимаю, почему это помечено как неправильное. Мы все согласны с тем, что это самый медленный алгоритм из всех :-), но он работает и ему просто нужно 4 байта для чтения файла. Исходный вопрос не предусматривает, что файл может быть прочитан только один раз, например.
Симон Мурье
1
@ Алекс Г - Верно. Я никогда не говорил, что ты это тоже сказал. Мы просто говорим, что IsNotInFile может быть тривиально реализован с использованием цикла для файла: Open; While Not Eof {Read Integer; Вернуть False, если Integer = i; Else Continue;}. Требуется всего 4 байта памяти.
Саймон Мурье
5

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

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

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

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

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

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

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

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

Жером Верстринг
источник
6
... и как это будет вписываться в 10 МБ?
Хмакхольм покинул Монику
Как насчет: ограничить глубину BTree до того, что вписывается в 10 МБ; это будет означать, что у вас будут результаты в наборе {ложное срабатывание | положительный}, и вы могли бы пройти через это и использовать другие методы, чтобы найти значения.
Джонатан Дикинсон
5

Я отвечу на 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;
    }
}
BobTurbo
источник
4

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

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

Риальто поддерживает Монику
источник
3

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

Одним из способов является устранение битов, однако это может не дать результата (скорее всего, это не так). 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 };

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

Джонатан Дикинсон
источник
3

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

Михаил Сагалович
источник
И как бы вы распечатать результат? Вы не можете поместить это в файл, и печать на экране займет несколько миллиардов лет. Вероятность безотказной работы на современных компьютерах
vsz
никогда не говорится, что нам нужно печатать результат где-либо, просто «сгенерировать» его. так что это зависит от того, что вы подразумеваете под генерацией. во всяком случае, мой ответ - всего лишь уловка, чтобы избежать разработки реального алгоритма :)
Михаил Сагалович
3

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

Если существует ровно 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";
  }
}
Syntaera
источник
@Nakilon и TheDayTurns указали на это в комментариях к первоначальному вопросу
Брайан Гордон
3

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

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

чокнутый урод
источник
Одним из важных моментов является то, что вы должны делать это по ходу дела, так что вы должны читать только один раз. Доступ к физической памяти медленный.
Райан Амос
Внешняя сортировка @ryan в большинстве случаев является сортировкой слиянием, поэтому при последнем слиянии вы можете выполнить проверку :)
ratchet freak
Если данные находятся на диске, они должны быть загружены в память. Это происходит автоматически файловой системой. Если нам нужно найти одно число (в противном случае проблема не указана), то чтение отсортированного файла построчно является наиболее эффективным методом. Он использует мало памяти и не медленнее, чем все остальное - файл должен быть прочитан.
Тони Эннис
Как вы будете сортировать 4 миллиарда целых чисел, когда у вас есть только 1 ГБ памяти? Если вы используете виртуальную память, это займет много времени, так как блоки памяти перемещаются в физическую память и из нее.
Клас Линдбек
4
@klas Merge сортировка предназначена для этого
храповик урод
2

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

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

Питер Гибсон
источник
Я вижу, что это уже было предложено :) голосованием за тех людей
Питер Гибсон
Парадокс дня рождения делает такое решение не стоящим риска, не проверяя файл, чтобы убедиться, что ваше случайное предположение было действительно верным ответом. (Парадокс дня рождения в этом случае неприменим, но повторный вызов этой функции для генерации новых уникальных значений создает ситуацию парадокса дня рождения.)
Питер Кордес
@PeterCordes Случайно сгенерированные 128-битные числа - это именно то, как работают UUID - они даже упоминают парадокс дня рождения при расчете вероятности столкновения на странице UUID
Питер Гибсон,
Вариант: Найти максимум в наборе, добавить 1.
Фил
Я бы быстро отсортировал исходный массив (без дополнительного хранилища), затем прошел бы по массиву и сообщил о первом «пропущенном» целом числе. Выполнено. Ответил на вопрос.
Уровень 42