std :: bản đồ nhận giá trị - tìm vs vòng lặp thủ công

Question

Tôi có một đối tượng bản đồ std :: map<string , Property*> _propertyMap, trong đó string là tên của thuộc tính và Property* chứa các giá trị thuộc tính.

tôi cần phải xử lý các giá trị tài sản và chuyển đổi chúng sang một dữ liệu cụ thể format- mỗi tài sản có định dạng riêng của mình, ví dụ như nếu khởi tạo bản đồ là như sau:.

_propertyMap["id"] = new Property(Property::UUID, "12345678"); 
_propertyMap["name"] = new Property(Property::STRING, "name"); 
.... 

sau đó "id" nên được xử lý khác nhau hơn "name", v.v.

Điều này có nghĩa là tôi cần tìm mỗi thuộc tính trong bản đồ và xử lý các giá trị của nó cho phù hợp.

Tôi đã nghĩ về hai cách để thực hiện điều đó.

One, sử dụng std::map::find phương pháp để có được một tài sản cụ thể, như thế:

map<string , Property*>::iterator it1 = _propertyMap.find("id"); 
if(it1 != _propertyMap.end()) 
{ 
    //element found - process id values 
} 
map<string , Property*>::iterator it2 = _propertyMap.find("name"); 
if(it2 != _propertyMap.end()) 
{ 
    //element found - process name values 
} 
.... 

Hai, lặp bản đồ và cho mỗi mục kiểm tra những gì tên của bất động sản là gì và tiến hành cho phù hợp:

for (it = _propertyMap.begin(); it != _propertyMap.end(); ++it) 
    { 
     //if it is events - append the values to the matching nodes 
     if (it->first == "id") 
     { 
      //process id values 
     } 
     else if (it->first == "name") 
       { 
        //process name values 
       } 
     ..... 
    } 

Cho rằng Time complexity of std::map::find is O(logN), độ phức tạp của giải pháp đầu tiên là O(NlogN). Tôi không chắc chắn về sự phức tạp của giải pháp thứ hai, bởi vì nó lặp lại bản đồ một lần (O(N)), nhưng thực hiện rất nhiều if-else mỗi lần lặp lại. Tôi đã cố gắng để google phổ biến map::find() câu hỏi, nhưng không thể tìm thấy bất kỳ thông tin hữu ích; hầu hết trong số họ chỉ cần lấy một giá trị từ bản đồ và sau đó find() thực hiện điều này với độ phức tạp cao hơn (O(logN) vs O(N)).

Phương pháp tiếp cận tốt hơn là gì? hoặc có lẽ có một cái khác mà tôi không nghĩ đến?

Ngoài ra, nói kiểu mã, mã nào tốt hơn và rõ ràng hơn?

Answer 1

tôi nhìn thấy một vài khác nhau trường hợp sử dụng ở đây, tùy thuộc vào những gì bạn có trong tâm trí:

thuộc tính cố định

(Chỉ cần cho đầy đủ, tôi đoán nó không phải là những gì bạn muốn) Nếu cả hai tên và loại tài sản có thể cần được cố định, phiên bản tốt nhất là sử dụng một lớp đơn giản/struct, có thể sử dụng boost::optional (std::optional với C++ 17) cho các giá trị có thể có mặt hoặc không

struct Data{ 
    int id = 0; 
    std::string name = ""; 
    boost::optional<int> whatever = boost::none; 
} 

Ưu điểm:

• All "tra cứu" được giải quyết tại thời gian biên dịch

Nhược điểm:

• Không linh hoạt để mở rộng trong thời gian chạy

Process chỉ tùy chọn cụ thể tùy thuộc vào chính họ

Nếu bạn muốn xử lý chỉ một tập hợp con cụ thể của o ptions, nhưng giữ tùy chọn để có (chưa qua chế biến) các phím tùy chỉnh các phương pháp của bạn có vẻ phù hợp.

Trong trường hợp này hãy nhớ rằng bằng cách sử dụng tìm thấy như thế này:

it1 = _propertyMap.find("id"); 

có độ phức tạp O (logN) nhưng được sử dụng M lần, với M beeing số tuỳ chọn xử lý. Đây không phải là kích thước của bản đồ của bạn, đó là số lần bạn sử dụngfind()để nhận được một thuộc tính cụ thể. Trong ví dụ (rút ngắn), điều này có nghĩa là độ phức tạp của O (2 * logN), vì bạn chỉ tìm 2 khóa. Vì vậy, về cơ bản sử dụng M-times find() cân tốt hơn so với vòng lặp khi chỉ có kích thước của bản đồ tăng lên, nhưng tệ hơn nếu bạn tăng số lượng tìm thấy theo cách tương tự. Nhưng chỉ hồ sơ có thể cho bạn biết cái nào là nhanh hơn cho kích thước và trường hợp sử dụng của bạn.

Process tất cả các tùy chọn tùy thuộc vào loại

Kể từ khi bản đồ của bạn trông rất giống các phím có thể tùy chỉnh nhưng các loại đến từ một nhóm nhỏ, hãy xem xét Looping trên bản đồ và sử dụng các loại thay vì những cái tên để xác định cách xử lý chúng. Một cái gì đó như thế này:

for (it = _propertyMap.begin(); it != _propertyMap.end(); ++it) 
{ 
    if (it->first.type() == Property::UUID) 
    { 
     //process UUID values 
    } 
    else if (it->first.type() == Property::STRING) 
    { 
     //process STRING values 
    } 
    ..... 
} 

Điều này có lợi thế là bạn không cần bất kỳ thông tin nào về các phím trên bản đồ của bạn, chỉ những loại nào có thể lưu trữ.

Answer 2

Giả sử chúng tôi có bản đồ thuộc tính N và chúng tôi đang tìm kiếm một tập hợp con các thuộc tính P. Dưới đây là một phân tích thô, không biết sự phân bố thống kê của các phím:

• Trong cách tiếp cận bản đồ tinh khiết bạn tìm kiếm P lần với độ phức tạp O (log (n)), đó là O (p * log (n))

• Trong phương pháp xích-nếu bạn sẽ duyệt qua một khi bản đồ. Đó là O (N).Nhưng bạn không nên quên rằng một chuỗi if-then cũng là một (hiden) traversal của danh sách các phần tử P. Vì vậy, đối với tất cả các phần tử N bạn đang thực hiện tìm kiếm các phần tử có khả năng lên tới P. Vì vậy, bạn có ở đây một sự phức tạp của O (p * n).

Điều này có nghĩa là cách tiếp cận bản đồ sẽ làm tốt hơn quá trình truyền tải của bạn và khoảng cách hiệu suất sẽ tăng đáng kể với n. Tất nhiên điều này không tính đến chi phí cuộc gọi chức năng tài khoản trong bản đồ mà bạn không có trong if-chain. Vì vậy, nếu P và N là nhỏ, cách tiếp cận của bạn vẫn có thể đứng so sánh lý thuyết.

Điều cuối cùng bạn có thể làm để tăng hiệu suất hơn là sử dụng unordered_map, là O (1) phức tạp, giảm độ phức tạp của vấn đề xuống O (P).

Answer 3

Có một tùy chọn khác kết hợp tốt nhất cả hai. Với một hàm như thế này (đó là một sự thích nghi của std::set_intersection):

template<class InputIt1, class InputIt2, 
     class Function, class Compare> 
void match(InputIt1 first1, InputIt1 last1, 
      InputIt2 first2, InputIt2 last2, 
      Function f, Compare comp) 
{ 
    while (first1 != last1 && first2 != last2) { 
     if (comp(*first1,*first2)) { 
      ++first1; 
     } else { 
      if (!comp(*first2,*first1)) { 
       f(*first1++,*first2); 
      } 
      ++first2; 
     } 
    } 
} 

Bạn có thể sử dụng nó để xử lý tất cả tài sản của bạn trong thời gian O (N + M) thời gian. Dưới đây là ví dụ:

#include <map> 
#include <string> 
#include <functional> 
#include <cassert> 

using std::map; 
using std::string; 
using std::function; 

struct Property { 
    enum Type { UUID, STRING }; 
    Type type; 
    string value; 
}; 

int main() 
{ 
    map<string,Property> properties; 
    map<string,function<void(Property&)>> processors; 

    properties["id"] = Property{Property::UUID,"12345678"}; 
    properties["name"] = Property{Property::STRING,"name"}; 

    bool id_found = false; 
    bool name_found = false; 

    processors["id"] = [&](Property&){ id_found = true; }; 
    processors["name"] = [&](Property&){ name_found = true; }; 

    match(
     properties.begin(),properties.end(), 
     processors.begin(),processors.end(), 
     [](auto &a,auto &b){ b.second(a.second); }, 
     [](auto &a,auto &b) { return a.first < b.first; } 
    ); 

    assert(id_found && name_found); 
} 

Bản đồ processors có thể được xây dựng riêng và sử dụng lại để giảm chi phí.