2

次の問題があります。

std::string から boost::variant にマップする n 個のハッシュマップ (それらを 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. 【キープレゼント】一番大きなマップで次のアイテムへ。

それで全部です。O(n) + O(m*n) となり、これは O(m*n) に等しくなります。@ Woot4Moo のアルゴリズムのステップ (2) には O(m*n)*log(m*n) が必要なので、これは @ Woot4Moo のアルゴリズムよりも少ないようです。

簡単な方法で O(m*n) よりも高速にできるかどうかはわかりません。これをより速く行うには、オンザフライ処理が必要になると思います。しかし！！！この種のキャッシュはあまり安全ではありません。したがって、最初は単純なアルゴリズムを検討してください。アプリのボトルネックにはならないかもしれません。

于 2013-03-29T15:34:33.800 に答える