c++：有更快的方法得到地图/无序地图的交集吗？

Question

在c++中是否有更快的方法来实现下面的内容，这样我就可以超过python的实现了吗？

对于这些相交的键，useful:

• hash_DICT1

• 得到两个map/unordered_map键

• 的交集，计算它们各自集合/无序_set的元素之间的成对差，这些信息可能是有大约O(10000)键，关于O(10)元素在每个set.
• hash_DICT2中大约有O(1,000个)键，以及每个集合中大约有O(1)个元素。

例如：

    map <int,set<int>> hash_DICT1;
        hash_DICT1[1] = {1,2,3};
        hash_DICT1[2] = {4,5,6};
    map <int,set<int>> hash_DICT2;
        hash_DICT2[1] = {11,12,13};
        hash_DICT2[3] = {4,5,6};

    vector<int> output_vector
        = GetPairDiff(hash_DICT1, hash_DICT2)
        = [11-1,12-1,13-1, 
           11-2,12-2,13-2, 
           11-3,12-3,13-3] // only hashkey=1 is intersect, so only compute pairwise difference of the respective set elements.
        = [10, 11, 12, 
            9, 10, 11, 
            8,  9, 10] // Note that i do want to keep duplicates, if any. Order does not matter.

GetPairDiff函数

    vector<int> GetPairDiff(
    unordered_map <int, set<int>> &hash_DICT1,
    unordered_map <int, set<int>> &hash_DICT2) {
      // Init
        vector<int> output_vector;
        int curr_key;
        set<int> curr_set1, curr_set2;

      // Get intersection
        for (const auto &KEY_SET:hash_DICT2) {
          curr_key = KEY_SET.first;
          // Find pairwise difference
          if (hash_DICT1.count(curr_key) > 0){
            curr_set1 = hash_DICT1[curr_key];
            curr_set2 = hash_DICT2[curr_key];
            for (auto it1=curr_set1.begin(); it1 != curr_set1.end(); ++it1) {
              for (auto it2=curr_set2.begin(); it2 != curr_set2.end(); ++it2) {
                output_vector.push_back(*it2 - *it1);
              }
            }
          }
        }
    }

主运行

    int main (int argc, char ** argv) {
        // Using unordered_map
        unordered_map <int,set<int>> hash_DICT_1;
            hash_DICT_1[1] = {1,2,3};
            hash_DICT_1[2] = {4,5,6};
        unordered <int,set<int>> hash_DICT_2;
            hash_DICT_2[1] = {11,12,13};
            hash_DICT_2[3] = {4,5,6};
        GetPairDiff(hash_DICT_1, hash_DICT_1);
    }

像这样编译

g++ -o ./CompareRunTime.out -Ofast -Wall -Wextra -std=c++11

其他数据结构也受到欢迎，如map或unordered_set。然而，我确实尝试了所有4种排列，并发现GetPairDiff给出的排列运行最快，但速度远不及python的实现：

hash_DICT1 = { 1 : {1,2,3},      2 : {4,5,6} }
hash_DICT2 = { 1 : {11,12,13},   3 : {4,5,6} }

def GetPairDiff(hash_DICT1, hash_DICT2):
    vector = []
    for element in hash_DICT1.keys() & hash_DICT2.keys():
        vector.extend(
            [db_t-qry_t 
            for qry_t in hash_DICT2[element] 
            for db_t in hash_DICT1[element] ])
    return vector

output_vector = GetPairDiff(hash_DICT1, hash_DICT2)

业绩比较：

python  : 0.00824 s
c++     : 0.04286 s

c++的实现大约需要5倍的时间！

Answer 1

在应该使用const&.

• You的地方复制大量的
• ，不要保存搜索结果。您应该使用result.
• push_back而不是count，如果事先知道需要存储的元素的数量，则使用reserve()可以使vector的使用速度更快。

解决这些问题可能会导致类似的情况(需要C++17)：

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using container = std::unordered_map<int, std::unordered_set<int>>;

std::vector<int> GetPairDiff(const container& hash_DICT1,
                             const container& hash_DICT2) {
    // Init
    std::vector<int> output_vector;

    // Get intersection
    for(auto& [curr_key2, curr_set2] : hash_DICT2) {
        // use find() instead of count()
        if(auto it1 = hash_DICT1.find(curr_key2); it1 != hash_DICT1.end()) {
            auto& curr_set1 = it1->second;

            // Reserve the space you know you'll need for this iteration. Note:
            // This might be a pessimizing optimization so try with and without it.
            output_vector.reserve(curr_set1.size() * curr_set2.size() +
                                  output_vector.size());

            // Calculate pairwise difference
            for(auto& s1v : curr_set1) {
                for(auto& s2v : curr_set2) {
                    output_vector.emplace_back(s2v - s1v);
                }
            }
        }
    }
    return output_vector;
}

int main() {
    container hash_DICT1{{1, {1, 2, 3}}, 
                         {2, {4, 5, 6}}};
    container hash_DICT2{{1, {11, 12, 13}},
                         {3, {4, 5, 6}}};

    auto result = GetPairDiff(hash_DICT1, hash_DICT2);

    for(int v : result) {
        std::cout << v << '\n';
    }
}

这是用g++ -std=c++17 -O3编译的计算机上用于这些容器的python版本的8倍多。

下面是同一个程序的C++11版本：

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using container = std::unordered_map<int, std::unordered_set<int>>;

std::vector<int> GetPairDiff(const container& hash_DICT1,
                             const container& hash_DICT2) {
    // Init
    std::vector<int> output_vector;

    // Get intersection
    for(auto& curr_pair2 : hash_DICT2) {
        auto& curr_key2 = curr_pair2.first;
        auto& curr_set2 = curr_pair2.second;
        // use find() instead of count()
        auto it1 = hash_DICT1.find(curr_key2);
        if(it1 != hash_DICT1.end()) {
            auto& curr_set1 = it1->second;

            // Reserve the space you know you'll need for this iteration. Note:
            // This might be a pessimizing optimization so try with and without it.
            output_vector.reserve(curr_set1.size() * curr_set2.size() +
                                  output_vector.size());

            // Calculate pairwise difference
            for(auto& s1v : curr_set1) {
                for(auto& s2v : curr_set2) {
                    output_vector.emplace_back(s2v - s1v);
                }
            }
        }
    }
    return output_vector;
}

int main() {
    container hash_DICT1{{1, {1, 2, 3}}, 
                         {2, {4, 5, 6}}};
    container hash_DICT2{{1, {11, 12, 13}},
                         {3, {4, 5, 6}}};

    auto result = GetPairDiff(hash_DICT1, hash_DICT2);

    for(int v : result) {
        std::cout << v << '\n';
    }
}