优化C++代码(使用UnorderedMap和Vector)

Question

我正在尝试优化需要很长时间的C++代码的某些部分(对于X数据量,代码的以下部分需要大约19秒,并且我试图在不到5秒的时间内完成整个过程相同数量的数据 - 基于我的一些基准测试.我有一个函数"add",我已经编写并复制了代码.我将尝试尽可能多地解释我认为需要理解代码.如果我错过了什么,请告诉我.

对于X数据条目,以下函数add被称为X次.

void HashTable::add(PointObject vector)   // PointObject is a user-defined object
{
    int combinedHash = hash(vector);   // the function "hash" takes less than 1 second for X amount of data

   // hashTableMap is an unordered_map<int, std::vector<PointObject>>

   if (hashTableMap.count(combinedHash) == 0)
   {
        // if the hashmap does not contain the combinedHash key, then 
        //  add the key and a new vector
        std::vector<PointObject> pointVectorList;
        pointVectorList.push_back(vector);
        hashTableMap.insert(std::make_pair(combinedHash, pointVectorList));
   }
   else
   {
        // otherwise find the key and the corresponding vector of PointObjects and add the current PointObject to the existing vector
        auto it = hashTableMap.find(combinedHash);
        if (it != hashTableMap.end())
        {
            std::vector<PointObject> pointVectorList = it->second;
            pointVectorList.push_back(vector);
            it->second = pointVectorList;
        }
   }
}

Answer 1

你正在做很多无用的操作......如果我理解正确,简化形式可能只是:

void HashTable::add(const PointObject& vector) {
   hashTableMap[hash(vector)].push_back(vector);    
}

这是因为

• 使用时的地图operator[]将创建默认初始化值(如果地图中尚未显示)
• 值(a std::vector)通过引用返回,因此您可以直接push_back将传入点指向它.std::vector如果密钥已经在地图中,这将是新插入的或先前存在的.

还要注意,根据大小PointObject和其他因素,传递vector值而不是传递可能更有效const PointObject&.这是一种微观优化,但需要进行合理的分析.

Answer 2

而不是调用hashTableMap.count(combinedHash)和hashTableMap.find(combinedHash)更好的只是插入新的元素和检查什么insert()返回:

在版本(1)和(2)中,函数返回一个对象对象,其第一个元素是一个迭代器,指向容器中新插入的元素或指向其键等效的元素,以及一个bool值,指示元素是否为是否成功插入.

此外,不要在不需要的地方按值传递对象.最好通过指针或引用传递它.这个:

std::vector<PointObject> pointVectorList = it->second;

是低效的,因为它会创建一个不必要的向量副本.