많은 양의 데이터를 저장할 데이터 구조를 디자인하십시오.

Question

인터뷰에서 다음 질문을 받았는데,이 질문에 대한 답변을 찾을 수 없었습니다. 매우 도움이 될 것입니다.

각각 크기가 10MB 인 파일이 100 개 있습니다. 각 파일의 내용은 정수 값으로 매핑되는 일부 문자열입니다. = 정수 값

a=5 
ba=7 
cab=10 etc.. 

사용할 수있는 실제 RAM 공간

string_key 25 MB입니다. 어떻게 데이터 구조를 설계 할 것 같은 그 :

For any duplicate string_key, the integer values can be added 
Display the string_key=integer value sorted in a alphabetical format 

제약 :

All the entries of a file could be unique. All of the 10*1000MB of data could be unique string_key mapping to an integer value. 

해결 방법 1 :

내가 다른 후 각 파일을로드하고 저장에 대해 생각했다 정보는 해시 맵에 저장되지만,이 해시 맵은 매우 거대하며 모든 파일에 고유 데이터가 포함되어 있으면 RAM에 충분한 메모리가 없습니다.

다른 아이디어?

noSqldb를 사용하는 것은 옵션이 아닙니다.

Answer 1

여기에 내 찌르다. 기본적으로 아이디어는 소량의 바이너리 트리를 사용하여 정렬 된 데이터를 저장하고 메모리를 절약하기 위해 즉시 디스크에 저장하고 저장하며 연결된 트리를 사용하여 트리를 정렬합니다.

손으로 웨이브 형 버전 :

는 항목의 키를 기반으로 알파벳 순으로 정렬 이진 트리를 만듭니다. 각 항목에는 키와 값이 있습니다. 각 트리에는 첫 번째 키와 마지막 키의 이름이 속성으로 있습니다. 각 파일을 개별적으로로드하고 트리별로 항목을 한 줄씩 삽입하여 자동으로 정렬합니다. 나무의 내용물의 크기가 10MB에 이르면 우리는 나무를 각각 5mb의 나무 두 개로 나눕니다. 이 두 나무를 디스크에 저장합니다. 우리의 나무를 추적하기 위해, 우리는 나무의 배열과 이름/위치, 첫 번째와 마지막 속성의 이름을 유지합니다. 이제부터는 파일 N의 각 행에 대해 목록을 사용하여 적절한 트리를 찾아서 삽입하고 트리를 메모리로로드 한 다음 필요한 작업을 수행합니다. 우리는 끝날 때까지이 과정을 계속합니다.

이 방법을 사용하면 메모리에로드되는 최대 데이터 양은 25MB를 넘지 않습니다. 로드되는 파일 (10MB),로드 된 트리 (최대 10MB) 및 트리의 배열/목록 (희망 사항으로 5MB를 초과하지 않음)이 항상 있습니다.

약간 더 엄격한 알고리즘 :

1. 누구의 항목 (key, value) 튜플이다 정렬 된 이진 트리 B 초기화, 항목 '속성 key을 기반으로 name는 어떤 임의의 고유 한 문자열과 size입니다 속성 name, size, first_key, last_key을 가지고 소트 바이트 단위의 사이즈

2. 입력 항목의 속성이 first_key 인 경우 (tree_name, first_key) 정렬 된 기본 형식의 튜플 인 정렬 된 연결 목록 L을 초기화합니다. 이것은 우리의 나무 목록입니다. 튜플 (B.name, B.first_key)을 L에 추가하십시오.

3. 파일 이름이 file1, file2, ..., file100이라고 가정하면 파이썬과 매우 유사한 유사 코드로 작성된 다음 알고리즘을 진행합니다.

for i in [1..100]: 
    f = open("file" + i) # 10 mb into memory 
    for line in file: 
     (key, value) = separate_line(line) 

     if key < B.first_key or key > B.last_key: 
      B = find_correct_tree(L, key) 

     if key.size + value.size + B.size > 10MB: 
      (A, B) = B.split()  # supp A is assigned a random name and B keeps its name 
      L.add(A.name, A.first_key) 
      if key < B.first_key: 
       save_to_disk(B) 
       B = A  # 5 mb out of memory 
      else: 
       save_to_disk(A) 

     B.add(key) 
save_to_disk(B) 

그런 다음 우리가 목록을 반복하고 각 관련 트리를 출력 (I 내가 여기 사용하는 선언되지 않은 함수는 자체 설명이 희망) :

for (tree_name, _) in L: 
     load_from_disk(tree_name).print_in_order() 

이 다소 불완전 예 이 일을하기 위해서 항상 L 목록을 업데이트해야합니다. first_key 변경; 나는 이것이 25 메가 바이트를 수학적으로 사용한다는 것을 엄격하게 증명하지 못했습니다. 하지만 제 직관은 이것이 가능할 것이라고 말합니다. 정렬 된 링크 된 목록 (해시 테이블 일 수도 있겠습니까?)을 유지하는 것보다 나무를 정렬하는 것이 더 효율적입니다.