c++ 用于制作计数器的更高效的数据结构和算法。我用查表

Question

我的问题是：我给出了一系列查询和一系列参考，我想计算它们之间所述键的出现次数，但前提是它们具有匹配的键。我选择使用 LUT 是因为我认为它可以有效地帮助我，但我不确定是否有更好的方法，或者我使用 LUT 的方式不够有效。

我有以下数据结构。

unordered_map <int, set<int>> Reference_map1, Reference_map2, ... , Reference_mapM;
// to story all the reference maps by their neightas
unordered_map <string, unordered_map <int, set<int>>> ReferenceMaps;
unordered_map <int, set<string>> LUT // look up table
// N is significantly greater than M
unordered_map <int, set<int>> query_map1, query_map2, ... , query_mapN;

Reference_mapi 和 query_mapj

的示例

Reference_map1[111] = {0, 1, 2};
Reference_map1[333] = {1, 2, 3};
Reference_map1[888] = {2, 8, 0};

Reference_map2[111] = {1, 5, 9};
Reference_map2[999] = {0, 7, 4};

ReferenceMaps['Reference_map1']=Reference_map1;
ReferenceMaps['Reference_map2']=Reference_map2;

query_map1[111] = {8, 2, 6};
query_map1[333] = {4, 7, 3};

query_map2[222] = {3, 6, 8};
query_map2[999] = {2, 3, 5};

我如何存储我的查询 table LUT 这样一来，对于我从 'query_mapj' 获得的任何密钥，我只会获得必要的 Reference_mapis

LUT[111] = {'Reference_map1', 'Reference_map2'}
LUT[333] = {'Reference_map1'}
LUT[888] = {'Reference_map1'}
LUT[999] = {'Reference_map2'}

例如，query_map1 中的 111 给出了 'Reference_map1'、'Reference_map2'，因为它们具有密钥 111。另一方面，query_map2 中的 999 只给出 'Reference_map2' 因为只有它有密钥 999.

所以它会像这样：

unordered_map<string, int> MakeCounter(
    unordered_map <int, set<int>> &query_map, 
    unordered_map <string, unordered_map <int, set<int>>> &ReferenceMaps
    ){
    unordered_map<string, int> RefName_Counter;
    set<string> ReferenceNameSet;
    // Update the RefName_Counter
    for (const auto &key2nameset:query_map) {
        // Check if this hash is in the LUT
        if (LUT.count(key2nameset.first) <= 0){ continue; }
        // Update Counter
        ReferenceNameSet = LUT[key2nameset.first];
        for (const auto &it : ReferenceNameSet){
            if (RefName_Counter.count(it) > 0)
                RefName_Counter[it]++;
            else
                RefName_Counter[it] = 1;
        }
    }
    return RefName_Counter;
}

// The results should be like this
Counter1 = MakeCounter(query_map1, ReferenceMaps);
/*
    Counter1['Reference_map1'] = 2; // because they share keys : 111 and 333
    Counter1['Reference_map2'] = 1; // because they share keys : 111
*/
Counter2 = MakeCounter(query_map2, ReferenceMaps);
/*
    Counter1['Reference_map2'] = 1; // because they share keys : 999
*/

是否有更好的方法为每个 query_mapi 获取 Counteri？

Answer 1

这是一条评论；我正在使用“answer”来正确格式化代码片段。

这会搜索您的 LUT 两次：

// Check if this hash is in the LUT
if (LUT.count(key2nameset.first) <= 0){ continue; }
// Update Counter
ReferenceNameSet = LUT[key2nameset.first];

它还无缘无故地复制了一套。

我认为索引地图中的 non-existing 元素会插入该元素，所以

if (RefName_Counter.count(it) > 0)
    RefName_Counter[it]++;
else
    RefName_Counter[it] = 1;

有效：

RefName_Counter[it]++;

所以你的外部 for 循环变为：

for (const auto &key2nameset:query_map) {
    // Check if this hash is in the LUT
    auto iter = LUT.find(key2nameset.first);
    if(iter == LUT.end()) { continue; }
    // Update Counter
    for (const auto &it : *iter){
        RefName_Counter[it]++;
}

Answer 2

考虑到我上面的评论，这是我得到的。

进行了调整以保留原始数据，但这感觉像是一个额外的功劳:)

unordered_map<int,int> MakeCounter(const unordered_map <int, set<int>>& qs, 
  const vector<unordered_map <int, set<int>>>& refs)
{
  unordered_map<int, int> counters;
  for (size_t i = 0;  i < refs.size(); ++i)
  {
    for (auto q : qs)
    {
      if (refs[i].find(q.first) != refs[i].end())
        counters[i]++;
    }
  }
  return counters;
}

int main()
{
  vector<unordered_map <int, set<int>>> References = {
    { {111, { 0, 1, 2 } },
      {333, { 1, 2, 3 } },
      {888, { 2, 8, 0 } },
    },
    { {111, { 1, 5, 9 } },
      {999, { 0, 7, 4 } },
    }
  };

  vector<unordered_map <int, set<int>>> Queries = {
    { {111, { 8, 2, 6 } },
      {333, { 4, 7, 3 } },
    },
    { {222, { 3, 6, 8 } },
      {999, { 2, 3, 5 } },
    }
  };
  unordered_map<int, int> m0 = MakeCounter(Queries[0], References);
  unordered_map<int, int> m1 = MakeCounter(Queries[1], References);
}

c++ 用于制作计数器的更高效的数据结构和算法。我用查表

c++ More efficient data structure and algorithm for making a Counter. i used look up tables

c++

lookup

counter

unordered-map

hashmap