Есть ли лучший выбор структур данных и алгоритмов для этой проблемы?

Question

Для следующей проблемы, пожалуйста, предложите лучшее решение (с точки зрения сложности времени). Мой подход я объяснил в последний раз.

Есть файл с записями в следующем формате: - RecordType; Symbol; цена; id; parentId

Пример файла выглядит как -

RecordType;Symbol;price;id;parentId

 - A;BANK_X;20;2345;0
 - A;BANK_Y;30;2346;0
 - A;BANK_Z;40;2347;0
 - M;BANK_X;50;2348;2345
 - M;BANK_Y;10;2349;2346 
 - A;BANK_X;20;2350;0 
 - A;BANK_E;40;2351;0 
 - M;BANK_X;45;2352;2345 
 - M;BANK_X;20;2353;2350

Такой файл содержит миллионы записей. Цель состоит в том, чтобы написать эффективную программу на C ++, чтобы разбить файл на несколько файлов таким образом, чтобы каждый файл меньшего размера содержал Y записей, где Y - целое число, указанное в качестве входных данных.

Указания, которые следует запомнить:

• Каждая запись имеет уникальный идентификатор (т. Е. Второе последнее поле в записи)
• Для символов, соответствующих A и M, записи должны находиться в одном и том же меньшем файле.

ДляНапример, если файл примера разбит на файлы, содержащие минимум 2 строки, то в одном файле должны быть следующие записи:

 - A;BANK_X;20;2345;0
 - M;BANK_X;50;2348;2345
 - M;BANK_X;45;2352;2345

Мой подход к решению проблемы:

1. Используемая структура данных:

   • Очередь: в ней будут объекты, ключом которых будет id (это родители), а значением в объекте будет вектор, в котором будет список дочерних элементов.
   • Unordered_map 1: Key: id (т.е. идентификаторы, чья запись имеет значение 0 в последнем поле), value: string (т.е. запись этого идентификатора считывается из файла)
   • Unordered_map 2: Key: id (т.е. идентификаторычья запись не имеет0 значение в последнем поле), значение: строка (то есть запись этого идентификатора, считанная из файла)

2. Алгоритм:

   • Чтение строки файлапо строке
   • Анализировать последние 2 поля записи
   • Проверить, является ли id родительским (то есть, если последнее поле записи равно 0). Если YES: создать объект {id, vactor } и вставитьочередь Добавить идентификатор и строковую запись в unordered_map 1 Если НЕТ: Найти родительский идентификатор в очереди и добавить дочерний идентификатор в векторе (Это можно сделать при поиске с постоянным временем) Добавить идентификатор и строковую запись в unordered_map 2
   • Выполнитьописанные выше шаги до конца файла.
   • Теперь начните добавлять очередь в очередь и для каждого идентификатора (который является родительским) получить строку записи из Unordered_map 1, записать в новый файл, также для его дочерних элементов (которые доступны в векторе) получить строку записи из Unordered_map 2 записать в файл. Здесь я проверю минимальные строки.
   • На основе значения Y получите запись для идентификаторов (parent) и потомков из unsorted_map и запишите в новые файлы.

Если я рассмотрю образец файла, упомянутый в утверждении, после применения моих структур данных algo будут следующие значения: -

Queue< int, std::vector < int> >: [ {2345, <2348, 2352>}, {2346, <2349>}, {2347, <empty>}, {2350, <2353>}, {2351, <empty>}]
Unordered_map 1 < int, std::string >: [{2345, "A;BANK_X;20;2345;0"}, {2346, "A;BANK_Y;30;2346;0"}, {2347, "A;BANK_Z;40;2347;0"}, {2350, "A;BANK_X;20;2350;0"}, {2351, "A;BANK_E;40;2351;0"}]
Unordered_map 2 < int, std::string >: [{2348, "M;BANK_X;50;2348;2345"}, {2349, "M;BANK_Y;10;2349;2346"}, {2352, "M;BANK_X;45;2352;2345"}, {2353, "M;BANK_X;20;2353;2350"}]

Answer 1

Следующие утверждения из вашего вопроса:

"Такой файл содержит миллионы записей."
"Каждая запись имеет уникальный идентификатор (то есть второй последнийполе в записи) "

.. напишите мне, чтобы я посоветовал вам использовать базу данных SQL. При этом вы можете хранить все в одном файле для удобства доступа. В будущем вы можете эффективно select, insert, update, delete без потери гибкости, которую вы получаете с первого дня.

SQLite - действительно легкая альтернатива.

Answer 2

Низкобюджетный способ сделать это:

1. Просмотрите файл и выведите два файла: один со всеми родителями (идентификатор-родителя равен 0), а второй со всеми детьми,Назовите их parent.txt и children.txt.
2. Сортировка parent.txt по идентификатору.
3. Сортировка children.txt по идентификатору родителя в качестве первичного ключа и идентификатора в качестве вторичного ключа.
4. Напишите программу, которая объединяет два файла, сопоставляя детей с родителями. Вы можете выводить их по мере чтения, разрывая их, чтобы создать новый файл после того, как вы достигли порогового значения, которое вы определили.

Это определенно не самый быстрый способ сделать это с точки зрения обработкивремя, но это очень просто. Вероятно, существует существующая программа, которая выполнит шаг 1. Если нет, написание программы для этого тривиально. Шаги 2 и 3 легко выполняются с помощью поставляемой ОС утилиты сортировки. Программа для реализации последнего шага, объединяющая файлы, также очень проста.

Если вы просто заинтересованы в выполнении работы с минимальными усилиями, то этот метод я бы порекомендовал. Это легко реализовать, требует мало памяти и легко доказать правильность.

Answer 3

ОБНОВЛЕНИЕ:

Я придумал лучшее решение. Поскольку похоже, что идентификаторы расположены в отсортированном порядке, вы можете записать в файл сразу после обработки каждой строки. Для каждой дочерней записи просто напишите в файл, где находится ее родитель. Только нужно помнить, что вы записываете родительскую запись, в какой файл.

unordered_map<int, int> id_to_file_id;

---

На самом деле вам не нужно хранить всю строку на карте, вам нужно только сохранить, какая строка этов. Это позволит сэкономить половину используемого вами пространства.

И использовать структуру данных, подобную этой:

unordered_map<int, int> id_to_line;
map<int, vector<int>> groups; // map<parent_id, vector<child_id>>

Answer 4

Вы можете сделать это используя вектор и карту. объявляйте вектор [SIZE_OF_SYMBLE] .map для символов с целыми числами. Затем каждый раз, когда вы получаете запись, сначала получите сопоставленное значение int для символа из карты и вставьте запись в этот вектор.

struct record{string recordType;char symbol;double price;int id;};
map<char,int> symbmol_to_int;
vector<record> piles[SIZE_OF_SYMBOL];