c++ - map数据结构的multimap

Question

我正在解析一个包含近 10 亿条（或可能是万亿条）记录的文件。我在用着

 struct ltstr
 {
    bool operator()(const char* s1, const char* s2) const
    {
        return strcmp(s1, s2) < 0;
    }
 };

 multimap<char*, map<char*, char*, ltsr>,ltstr > m;

这是在 C++ 中使用上述数据结构的有效方法吗？

问候

Answer 1

不，这不对。数十亿，更不用说数万亿的记录将不适合当今计算机的操作内存。请记住，10 亿条记录将消耗 32 GB 的映射开销，另外 16 GB 用于指向键和值的指针，显然还有n个 GB，其中n是实际数据的键和值的平均长度（假设 64 位系统；在 32 位系统中只有一半，但不适合 3 GB 地址空间限制）。世界上只有少数大型服务器具有如此大的内存。

处理如此大量数据的唯一选择是小批量处理它们。如果可以分别对每个元素进行处理，则只需一次加载一个元素，处理并丢弃它。无论数据大小如何，流式处理总是更快，因为它只需要固定数量的内存，因此可以有效地利用 CPU 缓存。

如果不能这样处理，因为需要特定的顺序或者您需要查找条目或其他内容，您需要将数据准备到适当的外部（磁盘上）结构。即使用外部合并排序（将分区写入临时文件）对它们进行排序，使用 B-tree 或哈希等对它们进行索引。这是很多工作。但幸运的是，有几个库可以实现这些算法。我会建议：

• *DMB，外部散列库，如GDBM 、 Berkeley DB或 ndbm。这些只提供地图的外部模拟，最简单，但 API 是基于 C 的。
• stxxl提供了几个外部容器的外部变体和适用于它们的算法。最大的优点是 API 与标准库集合相同。
• 对于更复杂的数据操作，只需使用sqlite即可。它同样快速且更复杂的数据处理更容易用 SQL 表达。