100 만개의 전화 번호 저장

100 만개의 전화 번호 저장

---

백만 개의 전화 번호를 저장하는 가장 효율적인 메모리 방식은 무엇입니까?

분명히 이것은 Google의 인터뷰 질문입니다. 아이디어를 알려주세요.

---

메모리가 가장 큰 고려 사항이라면 숫자를 전혀 저장할 필요가 없습니다. i와 i + 1 사이의 델타 만 있으면됩니다.

이제 숫자 범위가 200 0000-999 9999이면 가능한 전화 번호는 7,999,999 개입니다. 백만 개의 숫자가 있고 균등하게 분포되어 있다고 가정하면 순차 숫자 n_i와 n_i + 1 사이의 예상 거리는 E = n_i + 1-n_i ~ 8 (3 비트)입니다. 따라서 32 비트 int의 경우 잠재적으로 최대 10 개의 순차적 오프셋 (~ 400kb 최적 총 메모리 풋 프린트)을 저장할 수 있지만 8보다 큰 오프셋이 필요한 경우가있을 수 있습니다 (아마도 400 개 또는 1500 ??). 어떤 경우에는 int의 처음 2 비트를 헤더로 예약 할 수 있습니다. 헤더로 저장하는 비트를 읽는 데 사용하는 프레임 크기를 알려줍니다. 예를 들어, 00 = 3x10, 01 = 5x6, 10 = 7x4, 11 = 1 * 30을 사용할 수 있습니다.

---

공백으로 구분하여 ASCII로 작성하십시오.

선호하는 압축 알고리즘을 사용하여 결과 문자열을 압축합니다. 순서가 중요하지 않은 경우 먼저 정렬하면 압축에 도움이 될 수 있으며 더 가깝게 반복 할 수 있습니다.

아, 효율적인 랜덤 액세스를 원 하셨나요? 그럼 당신은 말 했어야 했어요.

---

가능한 해결책은

1. 숫자 정렬
2. 한 숫자에서 다음 숫자로 델타 인코딩

델타 주파수 분포는 매우 왜곡됩니다.

나는 7 + 3 + 3 + ... 비트 인코딩을 사용하는 델타에 대해 간단한 BER-like 패킹 접근법을 사용하여 실험을했다. 인코딩 기능은

def delta_write(x, b1, b2):
    lim = 1 << (b1 - 1)
    if x < lim:
        bit_write(x, b1)
    else:
        bit_write(lim + (x & (lim - 1)), b1)
        delta_write(x >> (b1 - 1), b2, b2)

(두 개의 매개 변수 7과 3은 실험적으로 결정되었습니다)

이 접근 방식을 사용하면 숫자 당 평균 8.83 비트 (포장 크기 1104188)의 1,000 개의 임의 접두사에서 선택한 처음 5 자리의 10 자리 숫자 100 만개를 얻었습니다.

---

숫자 블록에 대한 Huffman 코딩은 아마도 매우 좋은 결과를 제공 할 것입니다. 숫자가 혼합 된 유형 (예 : 일부 미국, 일부 해외 액세스 코드 포함) 인 경우 어떤 유형인지 (따라서 사용할 블록)을 지정하기 위해 또 다른 몇 비트가 필요합니다.

숫자가 작은 범위 (예 : 7 자리)에있는 경우이를 저장하는 가장 간단한 방법은 정수로 처리하고 정렬 한 다음 값의 차이를 저장 (허프만 인코딩)하는 것입니다. 예를 들어 7 자리 (10 ^ 7 가능성)의 10 ^ 6 숫자를 사용하면 log2 (10) ~ = 3.3 비트가 필요합니다.

---

처음에는 0이 이스케이프 문자로 사용되기 때문에 0으로 시작하지 않습니다. 그래서 간단히 전화 번호를 정수로 간주 할 수 있습니다. 그렇지 않은 경우 숫자 앞에 "1"을 추가 한 다음 정수로 변환합니다. 이것은 코딩 효율성에 큰 영향을 미치지 않습니다 (아마도 몇 바이트의 지속적인 오버 헤드). 전화 번호 안에 10 자리 이외의 다른 문자가 있으면 10보다 큰 밑수로 인코딩하면됩니다. 그래도 효율성이 떨어집니다.

크기 오름차순으로 주문하겠습니다. 그런 다음 차이를 계산하십시오. 그런 다음 protobuf를 패킹 된 반복 필드로 사용하여 차이점을 직렬화합니다.

이 방법은 허프만 인코더를 통해 protobuf의 게으른 솔루션을 사용한다는 점을 제외하면 RexKerr의 방법과 유사합니다. protobuf 정수 인코딩이 범용이고 전화 번호의 확률 분포를 고려하지 않기 때문에 아마도 조금 더 큽니다. 하지만 기존 protobuf serializer를 사용하기 만하면되므로 코딩이 훨씬 쉽습니다. UInt64의 크기를 초과하면 문제가 발생합니다. 즉, 전화 번호가 19 자리보다 긴 경우입니다. 파일 형식은 여전히 ​​지원하지만 대부분의 구현은 지원하지 않습니다.

인덱스가 없으면 액세스 시간이 상당히 나쁘지만 다소 간결해야합니다.

---

특수 트라이 데이터 구조 인 삼항 검색 트리는 메모리 효율적이며 여전히 부분 일치를 활성화합니다.

http://en.wikipedia.org/wiki/Ternary_search_tree

---

북미 번호 매기기 계획 의 데이터 필드 표현을 살펴보면 1+ NPA + NXX + xxxx 의 미국 전화 번호가 각 지역 번호의 전화 번호 필드 당 22 비트 미만으로 저장 될 수 있다는 결론을 내릴 수 있습니다. 지역 코드를 추가하고 미국 (캐나다 포함) 전화 번호를 나타내는 데이터를 32 비트에 편안하게 맞출 수 있습니다. 이것은 정수가 아닌 비트 필드 표현입니다.

그러나 이에 대한 귀하의 생각은 US Centric이 아니어야합니다. 확실히 문제는 단지 연습이 100 만개의 전화 번호를 가능한 한 적은 비트로 압축하는 것이 아닙니다.

미국 전화 번호는 3 자리 (내부 PBX 다이얼 플랜)에서 22 자리 (1 + NPA + NXX + xxxx + 11 자리 내부 PBX 다이얼 플랜)까지 짧을 수 있습니다. 전화 번호가 ITU 지정 숫자 형식 으로 제한되어있는 경우 최대 15 자리와 '+'에 1 비트가 있습니다.

그런 다음 3 자리에서 22 자리 (또는 ITU의 경우 15 자리) 사이의 전화 번호에 대한 가변 비트 필드 표현을 정의해야하며 각 비트 필드에는 필드 형식을 나타내는 X 비트 헤더 필드가 있습니다.

그런 다음이 비트 필드를 압축 된 비트 배열에 넣습니다 . 잠재적으로 해당 비트 배열은 trie 또는 다른 방법 으로 인덱싱 될 수 있습니다 .

이 기능의 효율성은 100 만 개의 전화 번호 형식, 액세스 속도, 향후 다양한 형식의 더 많은 전화 번호에 대한 데이터 구조의 유연성에 따라 결정됩니다. "올바른"대답 IMHO에 대한 비트를 계산하는 것이 아닙니다.

---

각 전화 번호가 (3 자리 지역 코드)-(7 자리 숫자)의 미국 형식과 일치한다고 가정합니다.

이것은 10 자리 숫자입니다.

그러나 전화 번호를 다룰 때 참여 규칙이 있습니다. 하나는 드물기 때문에 가능한 모든 지역 번호가 사용되는 것은 아닙니다. 이 경우 간단한 트리는 괜찮습니다. 생각해보세요. 캐나다에는 269 + 26 만 있으면됩니다. 꽤 작으며 많은 공간을 절약하고 검색 시간을 늘 렸습니다. 뿐만 아니라 위치 정보를 위해 증강 될 수 있습니다.

그 후 7 자리 숫자를 얻었습니다. 이것은 단일 32 비트 정수로 저장할 수 있습니다. 삽입에 따라 정렬하면 나머지 숫자에 대해 이진 검색을 수행 할 수 있으므로 검색을위한 매우 빠른 메커니즘이 있습니다.

---

서명되지 않은 Int32 또는 국제 번호의 경우 서명되지 않은 Int64

4MB가되는 32 비트 서명되지 않은 int 사용

---

저장된 데이터베이스에서 실행하려는 작업에 따라 다릅니다.

사소한 접근 방식은 부호없는 정수를 사용하는 것입니다. 저장해야하는 경우 사전을 사용하는 원시 텍스트 표현에 대한 압축이 더 작을 수 있습니다.

---

면접에서이 질문의 요점은 지원자의 문제 해결 능력을 키우는 것입니다. 질문의 초점이 메모리 효율성 이기 때문에 제 생각에 정답은 면접관에게 "전화 번호가 국제적입니까, 아니면 단일 국가로 제한되어 있습니까?"라고 묻는 것입니다. 번호가 단일 국가로 제한되면 각 국가가 주 및 도시별로 전화 번호를 배포하는 간단한 규칙이 있다는 사실로 인해 메모리 효율성을 극대화하는 작업이 단순화됩니다.

---

여기서 1 백만 크기의 비트 벡터를 사용할 수 있다고 생각합니다.

자바 예 :

private BitSet dir = new BitSet(1000000);

public void addTelephoneNumber(int number)
{
    dir.set(number);
}


public void removeTelephoneNumber(int number)
{
    if (dir.get(number))
    {
        dir.flip(number);
    }
}


public boolean isNumberPresent(int number)
{
    return dir.get(number);
}

---

8 백만 개의 숫자 중 하나에 대해 각 비트 1 (사용됨) 또는 0 (사용 가능)의 8 백만 비트 예

100 0000
900 0000
= 8 million phone numbers, bit 1 = 1000000 and bit 8 million = 9000000 

---

/******************************************************************************** 

  Filename: Phone_Numbers.c
    Author: Paul Romsky
   Company: Autoliv AEL
      Date: 11 MAR 2013

   Problem: What is the most efficient way, memory-wise, to store 1 million 
            phone numbers?

   Caveats: There is no mention if the numbers are contiguous or not, so, to save 
            space the numbers should be contiguous.  The problem (as a specification) 
            is rather vague and leaves a lot to interpretation, so many different 
            methods may be desired, but which one(s) desired is not surely known.

            Are the phone numbers just the extension (last four digits), or do they
            include the exchange (the leading 3 digits), or do they also include 
            area code and/or international numbers?

            There is no mention of the first number, only the range of numbers, so 
            the first number 000-0000 is used.  Although many numbers are not 
            normally used, they could in fact be used as valid number sequences 
            within the phone companies and are thus phone numbers nonetheless.

  Solution: A simple algorithm. If the numbers are not contiguous a fractal algorithm
            could be used.

            A standard ANSI C compiler should pack this program into a very small
            assembly module of only a few bytes.

 Revisions:

 Rev Date        By                   Description
 --- ----------- -------------------- -------------------------------------------
  -  11 MAR 2013 P. Romsky            Initial Coding

 ********************************************************************************/

/* Includes */

#include <stdio.h>


/* Functions */

/******************************************************************************** 
 *
 * Main Entry Point
 *
 ********************************************************************************/
int main()
{
  unsigned int Number;

  /* 1,000,000 Phone Number Storage 000-0000 through 999-9999 */

  for(Number = 0000000; Number < 10000000; Number++)
  {
    /* Retrieve Numbers */

    printf("%07u\n", Number);
  }

  return 0;
}

/* End */

참고 URL : https://stackoverflow.com/questions/5262465/storing-1-million-phone-numbers