Оптимизация кода на С++ (который использует UnorderedMap и Vector)

Ответ 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&. Это такая микро-оптимизация, что, однако, требует, чтобы профилирование выполнялось разумно.

Ответ 2

Вместо вызова hashTableMap.count(combinedHash) и hashTableMap.find(combinedHash) лучше вставить новый элемент и проверить, что insert() возвращено:

В версиях (1) и (2) функция возвращает парный объект, чья Первый элемент - это итератор, указывающий либо на вновь вставленный элемент в контейнере или элемент, ключ которого эквивалентен, и значение bool, указывающее, был ли элемент успешно вставлен или нет.

Кроме того, не передавайте объекты по значению, где вам не нужно. Лучше передать его указателем или ссылкой. Это:

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

неэффективен, так как он создаст ненужную копию вектора.

Ответ 3

Без if попробуйте вставить пустую запись в хеш-таблицу:

auto ret = hashTableMap.insert(
   std::make_pair(combinedHash, std::vector<PointObject>());

Будет добавлена ​​новая пустая запись или будет получена уже существующая запись. В вашем случае вам не нужно проверять, в чём дело, вам просто нужно взять возвращенный итератор и добавить новый элемент:

auto &pointVectorList = *ret.first;
pointVectorList.push_back(vector);

Ответ 4

Этот .count() абсолютно не нужен, вы можете упростить свою функцию:

void HashTable::add(PointObject vector)
{
    int combinedHash = hash(vector);
    auto it = hashTableMap.find(combinedHash);
    if (it != hashTableMap.end())
    {
        std::vector<PointObject> pointVectorList = it->second;
        pointVectorList.push_back(vector);
        it->second = pointVectorList;
    }
    else
    {
        std::vector<PointObject> pointVectorList;
        pointVectorList.push_back(vector);
        hashTableMap.insert(std::make_pair(combinedHash, pointVectorList));
    }
}

Вы также выполняете операции копирования во всем мире. Копирование объекта требует много времени, не делайте этого. Также используйте ссылки и указатели, если это возможно:

void HashTable::add(PointObject& vector)
{
    int combinedHash = hash(vector);
    auto it = hashTableMap.find(combinedHash);
    if (it != hashTableMap.end())
    {
        it->second.push_back(vector);
    }
    else
    {
        std::vector<PointObject> pointVectorList;
        pointVectorList.push_back(vector);
        hashTableMap.insert(std::make_pair(combinedHash, pointVectorList));
    }
}

Этот код, вероятно, может быть оптимизирован дальше, но для этого потребуется знание hash(), зная, как работает hashTableMap (кстати, почему это не std::map?) и некоторые эксперименты.

Если hashTableMap был std::map<int, std::vector<pointVectorList>>, вы могли бы упростить свою функцию:

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

И если это был std::map<int, std::vector<pointVectorList*>> (указатель), вы даже можете избежать этой последней операции копирования.

Ответ 5

Ваша самая большая проблема заключается в том, что вы копируете весь вектор (и каждый элемент этого вектора) дважды в части else:

std::vector<PointObject> pointVectorList = it->second;  // first copy
pointVectorList.push_back(vector);
it->second = pointVectorList;                           // second copy

Это означает, что каждый раз, когда вы добавляете элемент в существующий вектор, вы копируете весь вектор.

Если вы использовали ссылку на этот вектор, вы бы сделали намного лучше:

std::vector<PointObject> &pointVectorList = it->second;
pointVectorList.push_back(vector);
//it->second = pointVectorList; // don't need this anymore.

На стороне примечания, в вашем unordered_map вы хешируете свое значение как ваш ключ. Вместо этого вы можете использовать unordered_set с вашей хеш-функцией.

Ответ 6

Использование std::unordered_map здесь не представляется возможным - вы используете int from hash в качестве ключа (предположительно) хеш PointObject, а не PointObject. Существенно двойное хеширование. А также, если вам нужен PointObject, чтобы вычислить ключ карты, это не совсем ключ! Может быть, std::unordered_multiset будет лучшим выбором?

Сначала определите форму хэш-функции PointObject

namespace std
{
    template<>
    struct hash<PointObject> {
        size_t operator()(const PointObject& p) const {
            return ::hash(p);
        }
    };
}

Затем что-то вроде

#include <unordered_set>

using HashTable = std::unordered_multiset<PointObject>;

int main()
{
    HashTable table {};

    PointObject a {};
    table.insert(a);

    table.emplace(/* whatever */);

    return 0;
}

Ответ 7

Предполагая, что PointObject большой, а копии его дороги, std::move - ваш друг здесь. Вы хотите убедиться, что PointObject поддерживает перемещение (либо не определяет деструктор, либо оператор копирования, либо сам оператор move-constructor и move-assign).

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(std::move(vector));
        hashTableMap.insert(std::make_pair(combinedHash, std::move(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(std::move(vector));
            it->second = std::move(pointVectorList);
        }
   }
}