Найти целое число не среди четырех миллиардов заданных
Это вопрос интервью:
Учитывая входной файл с четырьмя миллиардами целых чисел, предоставьте алгоритм для генерации целого числа, которое не содержится в файле. Предположим, у вас есть 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 миллионов бит
Solution: For all possible 16-bit prefixes, there are 2^16 number of
integers = 65536, we need 2^16 * 4 * 8 = 2 million bits. We need build
65536 buckets. For each bucket, we need 4 bytes holding all possibilities because
the worst case is all the 4 billion integers belong to the same bucket.
step1: Build the counter of each bucket through the first pass through the file.
step2: Scan the buckets, find the first one who has less than 65536 hit.
step3: Build new buckets whose high 16-bit prefixes are we found in step2
through second pass of the file
step4: Scan the buckets built in step3, find the first bucket which doesnt
have a hit.
The code is very similar to above one.
Вывод: мы уменьшаем память за счет увеличения пропускной способности файла.
Уточнение для тех, кто опаздывает: в вопросе, как его спрашивают, не говорится, что в файле нет ровно одного целого числа - по крайней мере, большинство людей его не так интерпретируют. Однако многие комментарии в ветке комментариев касаются этого варианта задачи. К сожалению, комментарий, который представил его в ветке комментариев, был позже удален его автором, так что теперь он выглядит так, как будто потерянные ответы на него просто неправильно поняли все. Это очень запутанно. Сожалею.
38 ответов
Предполагая, что "целое число" означает 32 бита: наличия 10 МБ свободного места более чем достаточно для подсчета количества чисел во входном файле с любым заданным 16-разрядным префиксом для всех возможных 16-разрядных префиксов за один проход входной файл. По крайней мере, одно из ведер будет поражено менее 2^16 раз. Сделайте второй проход, чтобы узнать, какие из возможных чисел в этом сегменте уже используются.
Если это означает больше, чем 32 бита, но все еще ограниченного размера: сделайте, как указано выше, игнорируя все входные числа, которые выпадают из 32-битного диапазона (со знаком или без знака; на ваш выбор).
Если "целое число" означает математическое целое число: прочитайте один раз вход и отследите наибольшую длину числа самого длинного числа, которое вы когда-либо видели. Когда вы закончите, выведите максимум плюс одно случайное число, которое имеет еще одну цифру. (Одно из чисел в файле может быть bignum, для точного представления которого требуется более 10 МБ, но если входными данными является файл, то вы можете по крайней мере представить длину всего, что в него вписывается).
Статистически обоснованные алгоритмы решают эту проблему, используя меньше проходов, чем детерминированные подходы.
Если разрешены очень большие целые числа, то можно сгенерировать число, которое, вероятно, будет уникальным за время O(1). Псевдослучайное 128-разрядное целое число, такое как GUID, будет сталкиваться только с одним из существующих четырех миллиардов целых в наборе менее чем в одном из каждых 64 миллиардов миллиардов случаев.
Если целые числа ограничены 32 битами, то можно создать число, которое, вероятно, будет уникальным за один проход, используя намного меньше, чем 10 МБ. Вероятность того, что псевдослучайное 32-разрядное целое число столкнется с одним из 4 миллиардов существующих целых чисел, составляет около 93% (4e9 / 2^32). Вероятность того, что все 1000 псевдослучайных целых будут сталкиваться, составляет менее одного на 12 000 миллиардов миллиардов миллиардов (вероятность одного столкновения - 1000). Поэтому, если программа поддерживает структуру данных, содержащую 1000 псевдослучайных кандидатов, и перебирает известные целые числа, исключая совпадения из кандидатов, то почти наверняка найдется хотя бы одно целое число, которого нет в файле.
Подробное обсуждение этой проблемы обсуждалось в книге Джона Бентли "Колонка 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 Ting соответствующий бит в массиве, а затем проверяет этот массив с помощью test макрос выше, чтобы найти пропущенный номер.
Если объем доступной памяти меньше 0,466 ГБ, Bentley предлагает алгоритм k-pass, который делит входные данные на диапазоны в зависимости от доступной памяти. Возьмем очень простой пример: если был доступен только 1 байт (т.е. память для обработки 8 чисел), а диапазон был от 0 до 31, мы делим это на диапазоны от 0 до 7, 8-15, 16-22 и т. Д. и обрабатывать этот диапазон в каждом из 32/8 = 4 проходит.
НТН.
Поскольку проблема не указывает на то, что нам нужно найти наименьшее возможное число, которого нет в файле, мы могли бы просто сгенерировать число, которое длиннее, чем сам входной файл.:)
Для варианта RAM объемом 1 ГБ вы можете использовать битовый вектор. Вам нужно выделить 4 миллиарда битов == 500 МБ байтового массива. Для каждого числа, которое вы читаете с входа, установите соответствующий бит на "1". Как только вы закончите, переберите биты и найдите первый, который все еще равен 0. Его индекс является ответом.
Если они являются 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 МБ ОЗУ; поэтому любой небольшой диапазон целых имеет небольшую вероятность не содержать числа.
Если вам было гарантировано, что каждое целое число в списке уникально, вы можете сложить числа и вычесть сумму с одним пропущенным # до полной суммы (1/2)(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
Зачем делать это так сложно? Вы спрашиваете целое число, которого нет в файле?
Согласно указанным правилам, единственное, что вам нужно сохранить, - это наибольшее целое число, которое вы встречали в файле. Как только весь файл будет прочитан, верните число 1 больше этого.
Нет риска попасть в maxint или что-либо еще, потому что в соответствии с правилами нет ограничений на размер целого числа или числа, возвращаемого алгоритмом.
Это может быть решено в очень небольшом пространстве, используя вариант двоичного поиска.
Начните с допустимого диапазона чисел,
0в4294967295,Рассчитайте среднюю точку.
Переберите файл, посчитав, сколько чисел было равно, меньше или больше значения средней точки.
Если никакие числа не были равны, все готово. Число средней точки является ответом.
В противном случае выберите диапазон с наименьшим числом и повторите с шага 2 этот новый диапазон.
Для этого потребуется до 32 линейных сканирований по файлу, но для хранения диапазона и количества будет использоваться только несколько байтов памяти.
По сути, это то же самое, что и решение Хеннинга, за исключением того, что вместо 16 КБ используются две корзины.
РЕДАКТИРОВАТЬ Хорошо, это не совсем продумано, поскольку предполагается, что целые числа в файле следуют некоторому статическому распределению. По-видимому, им не нужно, но даже тогда нужно попробовать это:
Есть ≈4,3 миллиарда 32-битных целых. Мы не знаем, как они распределяются в файле, но наихудший случай - это случай с самой высокой энтропией Шеннона: равное распределение. В этом случае вероятность того, что одно целое число не появится в файле, равна
( (2³²-1)/2³²)⁴ ⁰⁰⁰ ⁰⁰⁰ ⁰⁰⁰ ≈ .4
Чем ниже энтропия Шеннона, тем выше эта вероятность в среднем, но даже в этом наихудшем случае у нас есть шанс на 90% найти одноразовое число после 5 догадок со случайными целыми числами. Просто создайте такие числа с помощью псевдослучайного генератора, сохраните их в списке. Затем прочитайте int за int и сравните его со всеми вашими догадками. Когда есть совпадение, удалите эту запись списка. После того, как вы просмотрели весь файл, скорее всего, у вас останется более одного предположения. Используйте любой из них. В редком (10%, даже в худшем случае) событии без догадок остаётся получить новый набор случайных целых чисел, возможно, больше на этот раз (10->99%).
Потребление памяти: несколько десятков байт, сложность: O(n), накладные расходы: не учитывается, так как большая часть времени будет потрачена на неизбежные обращения к жесткому диску, а не на сравнение целых чисел в любом случае.
На самом деле наихудший случай, когда мы не предполагаем статическое распределение, состоит в том, что каждое целое число встречается макс. один раз, потому что тогда в файле не встречается только 1 - 4000000000/2³² ≈ 6% всех целых чисел. Так что вам понадобится еще несколько догадок, но это все равно не будет стоить вредного количества памяти.
Если в диапазоне [0, 2 ^x - 1] отсутствует одно целое число, просто скопируйте их все вместе. Например:
>>> 0 ^ 1 ^ 3
2
>>> 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 6 ^ 7
5
(Я знаю, что это не дает точного ответа на вопрос, но это хороший ответ на очень похожий вопрос.)
Они могут посмотреть, слышали ли вы о вероятностном фильтре Блума, который может очень эффективно абсолютно точно определить, не является ли значение частью большого набора (но может только с высокой вероятностью определить, что он является членом набора).
Исходя из текущей формулировки исходного вопроса, самое простое решение:
Найдите максимальное значение в файле, затем добавьте 1 к нему.
Использовать 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 - один для номеров + и один для номеров - но требования к памяти не меняются.
Если ограничения по размеру нет, самый быстрый способ - взять длину файла и сгенерировать длину файла +1 число случайных цифр (или просто "11111..."). Преимущество: вам даже не нужно читать файл, и вы можете минимизировать использование памяти почти до нуля. Недостаток: вы напечатаете миллиарды цифр.
Однако, если бы единственным фактором было минимизация использования памяти, и ничто иное не важно, это было бы оптимальным решением. Это может даже принести вам награду за "худшее нарушение правил".
Если мы предположим, что диапазон чисел всегда будет равен 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+1y, Значение 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;
Вопрос с подвохом, если только он не был процитирован неправильно. Просто прочитайте файл один раз, чтобы получить максимальное целое число n, и вернуться n+1,
Конечно, вам нужен план резервного копирования на случай, если n+1 вызывает целочисленное переполнение.
Проверьте размер входного файла, затем выведите любое число, которое слишком велико, чтобы быть представленным файлом такого размера. Это может показаться дешевым трюком, но это творческое решение проблемы с собеседованием, оно аккуратно обходит проблему с памятью, и технически это 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 * 109 - 1), так как вы знаете, что в файле есть (4 миллиарда - 1) других целых чисел, и даже при идеальном сжатии они займут как минимум один бит каждый.
Самый простой подход - найти минимальное число в файле и вернуть на 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, отвечает на вопрос, заданный в stackru # 35185, как указал ltn100. Он использует O(1) хранилище и O(n) время выполнения. Если на данный момент мы предполагаем, что 32-разрядные целые числа, XOR имеет 7% -ную вероятность создания различного числа. Обоснование: дано ~ 4G различных чисел XOR'd вместе, и ок. 300M отсутствует в файле, число установленных битов в каждой битовой позиции имеет равную вероятность быть нечетным или четным. Таким образом, 2^32 числа имеют равную вероятность возникновения как результат XOR, из которых 93% уже находятся в файле. Обратите внимание, что если числа в файле не все различны, вероятность успеха метода XOR возрастает.
Почему-то, как только я прочитал эту проблему, я подумал о диагонализации. Я предполагаю сколь угодно большие целые числа.
Прочитайте первый номер. Дополните его нулями, пока не получите 4 миллиарда бит. Если первый (старший разряд) бит равен 0, выведите 1; else выводит 0. (На самом деле вам не нужно вводить левую клавиатуру: вы просто выводите 1, если в числе недостаточно битов.) Сделайте то же самое со вторым числом, за исключением того, что используете его второй бит. Продолжить через файл таким образом. Вы будете выводить 4-миллиардный бит по одному биту за раз, и это число не будет таким же, как в файле. Доказательство: это было то же самое, что и n-е число, тогда они согласились бы с n-ным битом, но не по построению.
Уберите из файла пробел и нечисловые символы и добавьте 1. Теперь ваш файл содержит одно число, отсутствующее в исходном файле.
От Reddit от Carbonetc.
Просто для полноты, вот еще одно очень простое решение, которое, скорее всего, займет очень много времени, но использует очень мало памяти.
Пусть все возможные целые числа будут в диапазоне от int_min в int_max, а такжеbool isNotInFile(integer) функция, которая возвращает истину, если файл не содержит определенного целого числа, и ложь иначе (сравнивая это определенное целое число с каждым целым числом в файле)
for (integer i = int_min; i <= int_max; ++i)
{
if (isNotInFile(i)) {
return i;
}
}
Вы можете использовать битовые флаги, чтобы отметить, присутствует ли целое число или нет.
После обхода всего файла отсканируйте каждый бит, чтобы определить, существует номер или нет.
Предполагая, что каждое целое число является 32-разрядным, они будут удобно помещаться в 1 ГБ ОЗУ, если будет выполнена маркировка битов.
Я отвечу на 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;
}
}
Для ограничения памяти 10 МБ:
- Преобразуйте число в его двоичное представление.
- Создайте двоичное дерево, где left = 0 и right = 1.
- Вставьте каждое число в дереве, используя его двоичное представление.
- Если номер уже был вставлен, листья будут уже созданы.
Когда закончите, просто выберите путь, который не был создан ранее, чтобы создать запрошенный номер.
Число 4 миллиарда = 2^32, что означает, что 10 МБ может быть недостаточно.
РЕДАКТИРОВАТЬ
Оптимизация возможна, если два конечных листа созданы и имеют общего родителя, то их можно удалить, а родительский флаг помечается как не решение. Это сокращает ветви и уменьшает потребность в памяти.
РЕДАКТИРОВАТЬ II
Нет необходимости строить дерево полностью. Вам нужно только строить глубокие ветви, если числа похожи. Если мы тоже обрежем ветки, то это решение может сработать.
Пока мы делаем креативные ответы, вот еще один.
Используйте внешнюю программу сортировки для числовой сортировки входного файла. Это будет работать для любого количества памяти, которое у вас может быть (при необходимости будет использоваться хранилище файлов). Прочитайте отсортированный файл и выведите первое пропущенное число.
Как сказал Райан, отсортируйте файл, а затем просмотрите целые числа, и когда значение будет пропущено, вы получите его:)
РЕДАКТИРОВАТЬ в downvoters: OP упомянул, что файл может быть отсортирован, так что это правильный метод.
Исключение битов
Одним из способов является устранение битов, однако это может не дать результата (скорее всего, это не так). 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 };
Просмотрите каждое значение в файле и попробуйте удалить его из текущего диапазона. У этого метода нет гарантий памяти, но он должен работать довольно хорошо.
Я думаю, что это решенная проблема (см. Выше), но есть интересный побочный случай, который нужно иметь в виду, потому что его могут спросить:
Если существует ровно 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";
}
}
2128 * 1018 + 1 (то есть (28)16 * 1018 + 1) - не может ли это быть универсальным ответом на сегодня? Это число, которое не может быть сохранено в файле 16 EB, что является максимальным размером файла в любой текущей файловой системе.
Если вы не принимаете 32-битное ограничение, просто верните случайно сгенерированное 64-битное число (или 128-битное, если вы пессимист). Вероятность столкновения 1 in 2^64/(4*10^9) = 4611686018.4 (примерно 1 на 4 миллиарда). Вы были бы правы большую часть времени!
(Шучу... вроде.)