2

我有以下问题：

我有 n 个从 std::string 映射到 boost::variant 的哈希图（我们称它们为 A.1、A.2、...、An），我想将它们合并为一个哈希图（我们称其为 B ） 如下：

  1. 如果 A.1, A.2, ... An 包含与键 K 相同的值，则 B 应包含与键 K 相同的值。
  2. 如果存在映射 A.1、A.2、... An 之一中不存在的某个键 K，则 B 应包含从键 K 到值 boost::blank 的映射。
  3. 如果 A.1、A.2、...An 中的键 K 存在某个与其他值不同的值，则 B 应包含从键 K 到值 boost::blank 的映射。

我必须这样做很多，我知道这将成为一个瓶颈。实现这一目标的最有效方法是什么？任何库支持像这样合并哈希图？

编辑：如果另一个数据结构更合适，请告诉我。但是，我确实需要 O(1) 查找

4

2 回答 2

1

如果我阅读正确，您正在寻找O(N log N)解决方案。如果没有 C++ 经验来编写正确的实现，您想要做的事情是这样的： 

1) Push all of the elements from every map into a `Set`   `O(N) + overhead of checking existence O(1)`  
   A)  define the elements of the set by a hash value generated by `Key + Value`   
      a)  that is `A:hello`  creates a different value than `B:hello`  
2) Perform a merge sort `O(N log N)` based on the values  
3) Start at the beginning of your `sorted set` and iterate over the values.  
   A) If a value is found multiple times this satisfies your `3` step  
   B) Your `2` step can be satisifed in `O(1)` time by looking up the key
于 2013-03-29T14:12:39.950 回答
1

这是我的算法（只是迭代所有元素）：

  1. std::unordered_map<string, variant> result
  2. 选择其中包含大多数条目的地图 O(n)。
  3. 遍历最大地图的每个元素 -> O(m)
    1. result[current_key] = current_value
    2. 对于彼此的地图 -> O(n-1)
      1. 查找键 -> O(1)
      2. 如果键不存在 -> result[current_key] = blank。进入最大地图中的下一个项目。
      3. [关键存在] 如果current_value != map[key]-> result[current_key] = blank。进入最大地图中的下一个项目。
      4. [key present] 到最大地图中的下一个项目。

就这样。你得到了 O(n) + O(m*n)，它等于 O(m*n)。这似乎不如@Woot4Moo 的算法，因为@Woot4Moo 的算法的步骤（2）需要 O(m*n)*log(m*n)。

我不确定是否有可能以直接的方式使其比 O(m*n) 更快。我想您需要一些即时处理才能更快地完成此操作。但！！！这些缓存不是很安全。所以，首先考虑简单的算法。也许它不会成为您的应用程序的瓶颈。

于 2013-03-29T15:34:33.800 回答