c++ - 使用 Hash Maps 表示一个非常大的数据源

Question

我有一个非常大的可能数据集，我正试图立即可视化。该集合本身由数十万个段组成，每个段都映射到一个 id。

我收到了第二个数据源，它为每个段提供了更多实时信息，但 id 与我拥有的 id 不对应。

我有一个 1:1 的数据 id（9 个字符的字符串）映射到当前的 id（长整数）。问题是有很多 id，并且进来的数据没有特定的顺序。

我想出的解决方案是有一个哈希映射，将字符串映射到道路 ID。问题是我不知道哈希映射是否足够高效以拥有所有 166k 数据条目。

有没有人可以为此使用任何建议和/或散列算法？

score 1 · Accepted Answer

Judy 数组是为这类事情而设计的：“Judy 的主要优点是可扩展性、高性能和内存效率。[...] Judy 可以替换许多常见的数据结构，例如数组、稀疏数组、哈希表、B 树、二叉树、线性列表、跳过列表、其他排序和搜索算法以及计数函数。”

score 1 · Accepted Answer

如果您只处理数十万个数据点，那么采用幼稚的方式并坚持使用哈希映射可能不会有问题。

即使您有 500,000 个 9 字符的字符串和相同数量的longs，每个项目仍然只有 16 个字节，或总共 8,000,000 个字节。即使您将开销翻倍，16 MB 也不会太大而无法一次存储在内存中。

基本上，首先尝试简单的方法，只有当您的分析告诉您它花费的时间太长时才担心它。

score 1 · Accepted Answer

由于对该问题的评论表明主要问题可能是内存使用情况：

使用池化或其他小对象优化分配器；假设您可以使用boost，您可能会在Pool中找到一个替代品。使用更好的小对象分配器可能是您会发现的最大的内存胜利。
如果您知道您的字符串是固定宽度的，您可能需要确保只分配足够的空间来存储它们。例如，使用自定义比较运算符包裹在固定长度 char[] 周围的结构可能比 std::string 更好。std::string 带有额外的动态分配（并为相应的指针使用空间）以及一些额外的大小和容量跟踪开销。（一般来说，尽量减少保留的分配数量；它会减少开销。）
（假设 STL）查看 std::map 和 std::unordered_map 之间的开销差异（后者目前可能对您可用，也可能不可用）；基于RBtree 的 std::map可能与您的“哈希图”的查找性能特征足够接近，并且可能（或可能不会）更节省内存，具体取决于您的标准库实现。

您采取的路线应该受到您可以收集的信息的影响——尝试了解分配的数量和分配大小/对齐开销。

您可以检测您的分配器或插入一些元素，并与您认为在内存使用方面应该做的相比，看看您的表现如何。

score 0 · Accepted Answer

由于您的字符串是预先知道的并且具有固定长度，因此理论上和实际上最好的解决方案是完美的哈希。您可以使用cmph来生成它。

根据 Wikipedia，您的密钥需要 2.5 位/密钥，或大约 50KB。与 664KB 的值相比，这可以忽略不计。

score 0 · Accepted Answer

0

虽然 166k 数据条目是相当小的 IMO 你可以看看google-sparsehash

于 2012-01-11T21:27:20.173 回答

5 回答 5