дизайн структуры данных для хранения большого количества данных

Question

Мне был задан следующий вопрос на собеседовании, который я не смог решить, указав на это, было бы очень полезно.

У меня есть 100 файлов размером 10 МБ, содержимое каждого из них представляет собой некоторое преобразование строк в целочисленное значение.

string_key = целое значение

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

физическое пространство ОЗУ доступно 25 Мб. Как структура данных будет разработана таким образом, что:

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

Constraint:

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:

Я думал о загрузке каждого из файлов один за другим и хранение информация в хэшмапе, но этот хэш-файл будет чрезвычайно огромным, и в ОЗУ не будет достаточной памяти, если все файлы содержат уникальные данные.

Любые другие идеи?

Использование noSqldb не является вариантом.

Answer 1

Вот мой удар по нему. В основном идея состоит в том, чтобы использовать серию небольших двоичных деревьев для хранения отсортированных данных, создания и сохранения их на диске «на лету» для сохранения памяти и связанного списка для сортировки самих деревьев.

версия Ручной Волнистые:

Создать бинарное дерево в алфавитном порядке на основе ключа из его записей. Каждая запись имеет ключ и значение. Каждое дерево имеет в качестве атрибута имена его первого и последнего ключей. Мы загружаем каждый файл по отдельности, а строка за строкой вставляем запись в дерево, которая сортирует его автоматически. Когда размер содержимого дерева достигает 10 мб, мы разбиваем дерево на два дерева по 5 мб каждый. Мы сохраняем эти два дерева на диске. Чтобы отслеживать наши деревья, мы сохраняем массив деревьев и их имя/местоположение и имена их первого и последнего атрибутов. С этого момента для каждой строки в файлеN мы используем наш список, чтобы найти соответствующее дерево для его вставки, загрузить это дерево в память и выполнить необходимые операции. Мы продолжаем этот процесс, пока не достигнем конца.

С помощью этого метода максимальный объем данных, загружаемых в память, будет не более 25 мб. Всегда загружается файлN (10 МБ), загружается дерево (не более 10 МБ) и массив/список деревьев (которые, надеюсь, не превысят 5 МБ).

Немного более строгий алгоритм:

1. Инициализировать отсортированное бинарное дерево B, элементы которой является (key, value) кортежем, сортирует на основе собственности метки записей в key и имеет свойство name, size, first_key, last_key где name является некоторой произвольной уникальной строкой и size является размер в байтах.

2. Инициализировать отсортированный связанный список L, элементы которой являются кортежи вида (tree_name, first_key) отсортирован BASEC на имущество метки записей в first_key. Это наш список деревьев. Добавьте кортеж (B.name, B.first_key) в L.

3. Предположим, что файлы называются file1, file2, ..., file100, мы переходим к следующему алгоритму, написанному в псевдокоде, который похож на python. (Я надеюсь, что необъявленные функции я использую здесь самообъясняющие)

   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) 
   

Тогда мы просто пройти по списку и распечатать каждое связанное дерево:

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

Это несколько неполное, например для выполнения этой работы вам придется постоянно обновлять список L каждый раз, когда изменения first_key; и я строго не доказал, что это математически использует 25 мб. Но моя интуиция подсказывает мне, что это, вероятно, сработает. Есть также, вероятно, более эффективные способы сортировки деревьев, чем сохранение отсортированного связанного списка (может быть, хэш-таблица?).