16

我正在研究输入非常大的数据结构，几乎 1 TB。我需要将数据加载到关联容器中。

数据有一些重复的整体，所以我正在使用多图，但有人建议我使用向量图而不是使用它。我可以知道性能方面的差异是什么吗？

 map<const char*, const char*, cmptr> mulmap;

 map <const char*, vector <const char*> ,cmptr> mmap;
4

2 回答 2

22

您正在浪费时间考虑mapvs multimap。假设 bin 的数量为 N，每个 bin 的平均项目数为 M。

Astd::multimap<Key, Val>通常使用具有重复键的 RB 树。

  • 获取是 O(log N + log M)
  • 插入是 O(log N + log M)
  • 删除是 O(log N + log M)
  • 迭代是 O(1)

Astd::map<Key, std::vector<Val>>通常使用具有唯一键的 RB 树。

  • 获取是 O(log N)
  • 插入是 O(log N)
  • 删除是 O(log N)
  • 迭代是 O(1)

如您所见，除非 M 非常大，否则差异不值得讨论。

但是，两者的存储都受到 RAM 的限制。1 TB 对于大多数系统来说根本不可行，而且我听说没有主板支持它。

您最好使用数据库来存储 1 TB 的数据。您可以为此任务选择几乎任何数据库。 京都内阁很简单，做你想做的，但你也可以使用PostgreSQL，MySQL，Sqlite，Dynamo，Redis，MongoDB，Cassandra，Voldemort...

于 2013-02-18T08:29:13.737 回答
5

有 1 TB 的输入，我都不会使用。很可能，您没有足够的 RAM。使用一些磁盘数据结构，如B-tree。

于 2013-02-18T08:31:35.233 回答