Tối ưu hóa mã C++ (sử dụng UnorderedMap và Vector)

Question

Tôi đang cố gắng tối ưu hóa một số phần của mã C++ mất nhiều thời gian (phần sau của mã mất khoảng 19 giây cho số lượng dữ liệu X và Tôi đang cố gắng hoàn thành toàn bộ quá trình trong vòng chưa đầy 5 giây cho cùng một lượng dữ liệu - dựa trên một số điểm chuẩn mà tôi có). Tôi có một chức năng "thêm" mà tôi đã viết và sao chép mã ở đây. Tôi sẽ cố gắng giải thích càng nhiều càng tốt mà tôi nghĩ là cần thiết để hiểu mã. Xin vui lòng cho tôi biết nếu tôi đã bỏ lỡ một cái gì đó.

Thêm hàm sau đây được gọi là X lần cho số lượng mục nhập dữ liệu 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

Bạn đang làm rất nhiều hoạt động vô ích ... nếu tôi hiểu đúng, một hình thức đơn giản có thể là đơn giản :

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

Điều này hoạt động vì

• Một bản đồ khi truy cập sử dụng operator[] sẽ tạo ra một giá trị mặc định khởi tạo nếu nó không phải là đã có trong bản đồ
• Giá trị (một std::vector) được trả lại bằng cách tham khảo để bạn có thể trực tiếp push_back điểm đến với nó . Điều này std::vector sẽ là một trong những mới được chèn vào hoặc một trước đó đã tồn tại nếu chìa khóa đã có trong bản đồ.

Cũng lưu ý rằng, tùy thuộc vào kích thước của PointObject và các yếu tố khác, nó có thể là có thể hiệu quả hơn để vượt qua vector theo giá trị thay vì bằng const PointObject&. Đây là loại tối ưu hóa vi mô mà tuy nhiên yêu cầu hồ sơ phải được thực hiện một cách hợp lý.

Answer 2

Thay vì gọi hashTableMap.count(combinedHash) và hashTableMap.find(combinedHash), tốt hơn chỉ cần chèn yếu tố mới và kiểm tra những gì insert() trả về:

Trong các phiên bản (1) và (2), hàm trả về một đối tượng cặp mà đầu tiên phần tử là một trình vòng lặp trỏ hoặc phần tử mới được chèn vào trong vùng chứa hoặc thành phần có khóa tương đương, và giá trị bool cho biết thành phần có thành công hay không được chèn vào hay không.

Ngoài ra, không được chuyển đối tượng theo giá trị mà bạn không phải làm. Tốt hơn là vượt qua nó bằng con trỏ hoặc bằng cách tham khảo. Điều này:

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

không hiệu quả vì nó sẽ tạo bản sao vector không cần thiết.

Answer 3

Nếu không có sự if, cố gắng để chèn một mục trống trên bảng băm:

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

Hoặc một mục trống mới sẽ được thêm vào, hoặc các mục nhập đã hiện diện sẽ được lấy ra. Trong trường hợp của bạn, bạn không cần phải kiểm tra mà nó như vậy, bạn chỉ cần phải thực hiện lặp lại và thêm các yếu tố mới:

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

Answer 4

lớn nhất của bạn vấn đề là bạn sao chép toàn bộ vector (và mọi phần tử trong vector) hai lần ở phần khác:

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

Điều này có nghĩa rằng mỗi khi bạn đang thêm một yếu tố để một vector hiện tại bạn đang sao chép rằng toàn bộ vector.

Nếu bạn sử dụng một tham chiếu đến vector mà bạn muốn làm tốt hơn rất nhiều:

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

---

Trên một mặt lưu ý, trong bạn unordered_map bạn đang băm giá trị của bạn là chìa khóa của bạn. Thay vào đó, bạn có thể sử dụng một hàm unordered_set với hàm băm của mình.

Answer 5

Sử dụng std::unordered_map dường như không thích hợp ở đây - bạn sử dụng int từ hash là chìa khóa (mà có lẽ) là các hash của PointObject hơn PointObject riêng của mình. Về cơ bản, băm đôi.Và nếu bạn cần PointObject để tính toán khóa bản đồ thì đó thực sự không phải là chìa khóa! Có lẽ std::unordered_multiset sẽ là một lựa chọn tốt hơn?

Đầu tiên xác định hình thức hàm băm PointObject

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

Sau đó, một cái gì đó giống như

#include <unordered_set> 

using HashTable = std::unordered_multiset<PointObject>; 

int main() 
{ 
    HashTable table {}; 

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

    table.emplace(/* whatever */); 

    return 0; 
} 

Answer 6

Giả sử rằng PointObject lớn và làm cho bản sao của nó là tốn kém, std::move là bạn của bạn ở đây. Bạn sẽ muốn đảm bảo rằng PointObject là di chuyển-nhận thức (hoặc không xác định một nhà điều hành hủy hoặc sao chép, hoặc cung cấp một di chuyển-constructor và di chuyển-nhà điều hành chuyển nhượng chính mình).

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); 
     } 
    } 
} 

Answer 7

.count() này là hoàn toàn hưởng ứng nhiệt liệt, bạn có thể đơn giản hóa chức năng của bạn để:

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)); 
    } 
} 

Bạn cũng đang thực hiện hoạt động sao chép ở khắp mọi nơi. Việc sao chép một đối tượng tốn thời gian, tránh làm điều đó. Cũng sử dụng tài liệu tham khảo và gợi ý khi có thể:

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)); 
    } 
} 

Mã này có lẽ có thể được tối ưu hóa hơn nữa, nhưng nó sẽ đòi hỏi phải biết hash(), biết đường đi hashTableMap công trình (bằng cách này, tại sao nó không phải là một std::map?) Và một số thử nghiệm.

Nếu hashTableMap là một std::map<int, std::vector<pointVectorList>>, bạn có thể đơn giản hóa chức năng của bạn như thế này:

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

Và nếu đó là một std::map<int, std::vector<pointVectorList*>> (con trỏ), bạn thậm chí có thể tránh điều đó hoạt động sao chép cuối cùng.