32 비트 정수인 경우 (2 ^32에 가까운 ~ 40 억 숫자 선택에서와 같이) 40 억 숫자 의 목록은 가능한 정수의 최대 93 %를 차지합니다 (4 * 10 ⁹ / (2 ³² ) ). 따라서 각 비트가 0으로 초기화 된 2 ³² 비트의 비트 배열을 만들면 (2 ²⁹ 바이트 ~ 500 MB의 RAM이 필요합니다. 바이트 = 2 ^3을 기억하십시오. 비트 = 8 비트를 하십시오) 정수 목록을 읽고 각각의 int에 대해 대응하는 비트 어레이 요소를 0 내지 1로 설정하고; 그런 다음 비트 배열을 읽고 여전히 0 인 첫 번째 비트를 반환하십시오.

RAM이 적 으면 (~ 10MB)이 솔루션을 약간 수정해야합니다. 10 MB ~ 83886080 비트는 여전히 0에서 83886079 사이의 모든 숫자에 대해 비트 배열을 수행하기에 충분합니다. 따라서 int 목록을 읽을 수 있습니다. 비트 배열에서 0에서 83886079 사이의 레코드 번호 만 기록하십시오. 숫자가 무작위로 분포 된 경우; (이 약 100 %의 차이 확률이 압도적으로 (10) ^-2592069 )를) 누락 INT를 찾을 수 있습니다. 실제로 1에서 2048까지의 숫자 (256 바이트의 RAM 만 있음) 만 선택하면 시간의 압도적 비율 (99.99999999999999999999999999999999999999999999999999999999999995 %)이 여전히 누락 된 숫자임을 알 수 있습니다.

그러나 약 40 억 개의 숫자 대신에 2 ^32-1 숫자와 10MB 미만의 RAM이 있습니다. 따라서 작은 범위의 정수는 숫자를 포함하지 않을 가능성이 적습니다.

당신이 목록의 각 INT 고유 것을 보장한다면, 당신은 숫자를 합계 한 # 전체 합계 (½)에 누락 된 합을 빼기 수 (2 ³² ) (2 ³² – 1)의 누락 INT를 찾을 수 = 9223372034707292160 . 그러나 int가 두 번 발생하면이 방법은 실패합니다.

그러나 항상 나누고 정복 할 수 있습니다. 순진한 방법은 배열을 읽고 전반 (0 ~ 2 ^31-1 )과 후반 (2 ³¹ , 2 ³² )에 있는 숫자의 수를 세는 것 입니다. 그런 다음 더 적은 수의 범위를 선택하고 해당 범위를 반으로 나누십시오. (말 (2 적은 수의 두이 있다면 ⁽³¹⁾ , 2 ⁽³²⁾ ) 다음, 다음 검색은 범위의 숫자 (2 카운트 것 ⁽³¹⁾ , 3 * 2 ³⁰ -1), (3 * 2 ⁽³⁰⁾ , 2 ⁽³²⁾ ). 계속 숫자가 0 인 범위를 찾을 때까지 반복하고 답을 얻으십시오. 배열을 통해 O (lg N) ~ 32 읽기를 가져와야합니다.

그 방법은 비효율적이었습니다. 각 단계에서 2 개의 정수만 사용하거나 4 바이트 (32 비트) 정수를 갖는 약 8 바이트의 RAM을 사용합니다. 더 나은 방법은 sqrt (2 ³² ) = 2 ¹⁶ = 65536 bin 으로 나누는 것입니다 . 각 bin에는 65536 개의 숫자가 있습니다. 각 저장소에는 카운트를 저장하는 데 4 바이트가 필요하므로 2 ¹⁸ 바이트 = 256kB 가 필요합니다 . 빈 0이되어, (0 (2) = 65535 ⁽¹⁶⁾ -1), 빈 1 (2, ¹⁶ = 65536 (2) * 2 ⁽¹⁶⁾ , 빈 (2) -1 = 131,071) (2 * 2 ¹⁶ = 131072 3 2 * ¹⁶ – 1 = 196607). 파이썬에서는 다음과 같은 것이 있습니다.

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)

~ 40 억 개의 정수 목록을 읽습니다. 2 ^{개의 16 개} 빈 각각에 몇 개의 정수가 있는지 계산 하고 65536 개의 숫자가 모두없는 incomplete_bin을 찾으십시오. 그런 다음 40 억 개의 정수 목록을 다시 읽습니다. 그러나 이번에는 정수가 그 범위에있을 때만 주목할 것입니다. 당신이 그들을 찾을 때 조금 뒤집어.

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

답변