Если это 32-разрядные целые числа (вероятно, из выбора ~ 4 миллиардов чисел, близких к 2 32 ), ваш список из 4 миллиардов чисел займет не более 93% возможных целых чисел (4 * 10 9 / (2 32 )).Таким образом, если вы создаете битовый массив из 2 32 бит с каждым битом, инициализированным в ноль (который займет 2 29 байт ~ 500 МБ ОЗУ; запомните, что байт = 2 3 бит = 8 бит), прочитайте список целых чисел и для каждого целого установите соответствующий элемент массива битов от 0 до 1;а затем прочитайте ваш битовый массив и верните первый бит, который по-прежнему равен 0.
В случае, когда у вас меньше ОЗУ (~ 10 МБ), это решение необходимо слегка изменить.10 МБ ~ 83886080 битов все еще достаточно для создания битового массива для всех чисел от 0 до 83886079. Таким образом, вы можете прочитать свой список целых чисел;и только записи #, которые находятся между 0 и 83886079 в вашем битовом массиве.Если числа распределены случайным образом;с подавляющей вероятностью (она отличается на 100% примерно на 10 -2592069 ) вы найдете пропущенный int).Фактически, если вы выбираете только числа от 1 до 2048 (только с 256 байтами оперативной памяти), вы все равно найдете пропущенное число в подавляющем проценте (99.99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999995%) того времени.
Но, скажем, вместооколо 4 миллиардов номеров;у вас было что-то вроде 2 32 - 1 цифра и менее 10 МБ ОЗУ;поэтому любой небольшой диапазон целых имеет небольшую вероятность не содержать числа.
Если вам было гарантировано, что каждое целое в списке уникально, вы можете сложить числа и вычесть сумму с одним пропущенным # до полной суммы (½) (2 32 ) (2 32 - 1) = 9223372034707292160, чтобы найти отсутствующий int.Однако, если int встречался дважды, этот метод потерпит неудачу.
Однако вы всегда можете разделить и победить.Наивным способом было бы прочитать массив и подсчитать количество чисел, которые находятся в первой половине (от 0 до 2 31 -1) и во второй половине (2 31 ,2 * 32 * тысяча тридцать восемь * +1039 *).Затем выберите диапазон с меньшим числом чисел и повторите деление этого диапазона пополам.(Скажем, если в (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 кБ. Таким образом, интервал 0 равен (от 0 до 65535 = 2 16 -1), интервал 1 равен (2 16) = от 65536 до 2 * 2 16 -1 = 131071), корзина 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