c++ - 这个问题有更好的数据结构和算法选择吗？

Question

对于以下问题，请提出更好的解决方案(在时间复杂度方面)。我在最后解释了我的方法。

有一个文件包含以下格式的记录:-RecordType;Symbol;price;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 是作为输入提供的整数。

要记住的要点:

• 每条记录都有唯一的 ID(即记录中的倒数第二个字段)
• 对于符号匹配的 A 和 M 记录应该在同一个较小的文件中。

例如，如果示例文件被拆分成至少包含 2 行的文件，那么以下记录应该在一个文件中:

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

我解决问题的方法:

1. 使用的数据结构:

   • 队列:这将包含对象，其中键为 id(它们是父对象)，对象中的值将是一个包含子项列表的 vector 。
   • Unordered_map 1: Key: id(即最后一个字段中记录值为0的id)，value: string(即从文件中读取的那个id的记录)
   • Unordered_map 2: Key: id(即记录在最后一个字段中具有非 0 值的 id)，value:string(即从文件中读取的该 id 的记录)

2. 算法:

   • 逐行读取文件
   • 解析最后 2 个记录字段
   • 检查 id 是否为父级(即记录的最后一个字段是否为 0)如果是:创建对象{id, vactor< int >} 放入队列向 unordered_map 1 添加 id 和 string 记录如果不:在队列中搜索父 ID 并在 vector 中添加子 ID(这可以进行恒定时间搜索)向unordered_map添加id和string记录2
   • 执行上述步骤直到文件结束。
   • 现在开始弹出队列，并为每个 id(即父级)从 Unordered_map 中获取记录字符串 1 写入一个新文件，同样对于它的 child (在 vector 中可用)从 Unordered_map 2 中获取记录字符串写入文件。在这里，我将检查最小行数。
   • 根据 Y 的值，从 unsorted_map 中获取 ids(parent)和 children 的记录并写入新文件。

如果我考虑声明中提到的示例文件，应用我的算法数据结构后将具有以下值:-

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

您问题的以下陈述:

"Such a file contains millions of records."
"Every record has unique id (i.e. second last field in the record)"

.. 断言我建议您使用 SQL 数据库。这样，您可以将所有内容保存在单个文件中以便于访问。您将来可以高效地选择、插入、更新、删除，而不会失去从第一天开始就获得的灵 active 。

SQLite确实是一个轻量级的选择。