[algorithm] 수천 개의 전화 번호를 저장하는 가장 효율적인 방법

다음은 aix의 답변에 대한 개선 사항 입니다. 데이터 구조에 세 개의 “계층”을 사용하는 것을 고려하십시오. 첫 번째는 처음 5 자리 (17 비트)에 대한 상수입니다. 이제부터 각 전화 번호는 나머지 5 자리 만 남습니다. 나머지 5 자리를 17 비트 이진 정수로보고 한 가지 방법을 사용하여 해당 비트 중 k 를 저장 하고 다른 방법으로 17- k = m 을 저장 하여 필요한 공간을 최소화하기 위해 끝에 k 를 결정 합니다.

먼저 전화 번호를 정렬합니다 (모두 10 진수 5 자리로 축소됨). 그런 다음 우리는 첫 번째로 구성된 이진수하는 얼마나 많은 전화 번호 계산 m의 비트는 첫번째 얼마나 많은 전화 번호를 모두 0 m의 얼마나 많은 전화 번호를 처음 들어 … 0 대부분에 비트가 01 m 비트는 최대 0 … 10 등이며, 첫 번째 m 비트가 1 … 11 인 전화 번호 수까지입니다. 이 마지막 수는 1000 (십진수)입니다. 이러한 개수 는 2 ^ m 개이고 각 개수는 최대 1000 개입니다. 마지막 숫자를 생략하면 (어쨌든 1000 개라는 것을 알기 때문에)이 모든 숫자를 (2 ^ m -1) 의 연속 블록에 저장할 수 있습니다. * 10 비트. (1024 미만의 숫자를 저장하려면 10 비트이면 충분합니다.)

모든 (축소 된) 전화 번호 의 마지막 k 비트는 메모리에 연속적으로 저장됩니다. 그래서 만약 K가 인 마지막 7 비트의 메모리의 블록의 다음 제 7 비트 (비트 0-6을 통해) 제 (감소) 전화 번호의 최종 7 비트에 대응하는 비트 7 내지 13에 대응 통해, 7 말 두 번째 (축소 된) 전화 번호 등. 이를 위해서는 총 17 + (2 ^ (17- k )-1) * 10 + 1000 * k에 대해 1000 * k 비트 가 필요합니다 . 이는 k = 10에 대해 최소 11287에 도달합니다 . 따라서 모든 전화 번호를 ceil (에 저장할 수 있습니다. 11287/8) = 1411 바이트.

추가 공간은 1111111 (이진수)로 시작할 수있는 숫자가 없다는 것을 관찰함으로써 절약 할 수 있습니다. 그로 시작하는 가장 낮은 숫자는 130048이고 십진수 5 자리 만 있기 때문입니다. 이를 통해 첫 번째 메모리 블록에서 몇 개의 항목을 줄일 수 있습니다. 2 ^ m -1 카운트 대신 ceil (99999 / 2 ^ k ) 만 필요합니다 . 즉 공식이

17 + ceil (99999 / 2 ^ k ) * 10 + 1000 * k

놀랍게도 k = 9 및 k = 10 또는 ceil (10997/8) = 1375 바이트에 대해 최소 10997을 얻습니다 .

특정 전화 번호가 세트에 있는지 알고 싶다면 먼저 처음 5 자리 이진수가 저장 한 5 자리 숫자와 일치하는지 확인합니다. 그런 다음 나머지 5 자리를 상위 m = 7 비트 (즉, m 비트 수 M )와 하위 k = 10 비트 (수 K ) 로 나눕니다 . 우리는 지금 번호를 찾을 수 [M-1] 처음있는 감소 된 전화 번호 m의 숫자가 가장에있는 M 1, 및 수 – [M] 처음있는 감소 된 전화 번호 m의 숫자가 가장에있는 M을 , 둘 다 첫 번째 비트 블록에서 가져온 것입니다. 이제 우리 는[M-1] 번째 및 A는 [M]가의 번째 시퀀스 유전율 우리가 발견되면 메모리의 제 2 블록 내의 비트보고 K를 ; 최악의 경우 1000 개의 시퀀스가 ​​있으므로 이진 검색을 사용하면 O (log 1000) 연산을 완료 할 수 있습니다.

1000 개의 숫자를 모두 인쇄하기위한 의사 코드는 다음과 같습니다. 여기서 첫 번째 메모리 블록의 K 번째 k 비트 항목을 a [K] 로 액세스하고 두 번째 메모리 블록의 M ‘번째 m 비트 항목을 b [M]으로 액세스합니다. (둘 다 작성하는 데 지루한 몇 가지 작업이 필요합니다). 처음 5 자리 숫자는 c 입니다.

i := 0;
for K from 0 to ceil(99999 / 2^k) do
  while i < a[K] do
    print(c * 10^5 + K * 2^k + b[i]);
    i := i + 1;
  end do;
end do;

K = ceil (99999 / 2 ^ k ) 의 경계 케이스에 문제가있을 수 있지만 수정하기에는 쉽습니다.

마지막으로, 엔트로피 관점에서 10 ^ 5보다 작은 10 ^ 3 양의 정수의 하위 집합을 ceil (log [2] (binomial (10 ^ 5, 10 ^ 3)) 미만으로 저장할 수 없습니다. ) = 8073. 처음 5 자리에 필요한 17 개를 포함하여 여전히 10997-8090 = 2907 비트의 간격이 있습니다. 상대적으로 효율적으로 숫자에 액세스 할 수있는 더 나은 솔루션이 있는지 확인하는 것은 흥미로운 도전입니다!

답변

17 (prefix) + 1,782 (counts) + 7,000 (offsets) = 8,799 bits = 1100 bytes

Size in bits = 17 (prefix) + 1,000 + 99,999/2^x + x * 1,000