tr1 :: hash for boost :: thread :: id?

Question

Tôi bắt đầu sử dụng lớp unordered_set từ không gian tên tr1 để tăng tốc truy cập vào đồng bằng (dựa trên cây) STL map. Tuy nhiên, tôi muốn lưu trữ các tham chiếu đến các chuỗi ID trong tăng (boost::thread::id) và nhận ra rằng API của các số nhận dạng đó mờ đục đến nỗi bạn không thể có được một mã băm của nó.

Đáng ngạc nhiên, tăng cường thực hiện các phần của tr1 (bao gồm hash và unordered_set), nhưng nó không xác định một lớp băm có thể băm ID luồng.

Nhìn vào tài liệu của boost::thread::id tôi thấy rằng ID chủ đề có thể xuất ra một dòng suối, vì vậy giải pháp của tôi để làm băm là loại:

struct boost_thread_id_hash 
{ 
    size_t operator()(boost::thread::id const& id) const 
    { 
     std::stringstream ostr; 
     ostr << id; 
     std::tr1::hash<std::string> h; 
     return h(ostr.str()); 
    } 
}; 

Đó là, serialize nó, áp dụng các hash đến chuỗi kết quả. Tuy nhiên, điều này có vẻ kém hiệu quả hơn so với sử dụng STL map<boost::thread::id>.

Vì vậy, câu hỏi của tôi: Bạn có tìm cách làm tốt hơn không? Có một sự mâu thuẫn rõ ràng trong cả tăng và tr1 không ép buộc sự tồn tại của một lớp học hash<boost::thread::id>?

Cảm ơn.

Answer 1

Chi phí của việc xâu chuỗi thread::id (chỉ để tính toán chuỗi băm sau) là, như bạn gần như đã nói, thiên văn so với bất kỳ lợi ích hiệu suất nào có thể là tr1::unordered_map. Vì vậy, câu trả lời ngắn sẽ là: dính với std :: map < chủ đề :: id, ...>

Nếu bạn hoàn toàn phải sử dụng container có thứ tự, cố gắng sử dụng native_handle_type thay vì thread::id nếu có thể , tức là thích tr1::unordered_map< thread::native_handle_type, ... >, hãy gọi thread::native_handle() thay vì thread::get_id() khi insert ing và find ing.

KHÔNG cố gắng bất cứ điều gì giống như sau:

struct boost_thread_id_hash { 
    // one and only member of boost::thread::id is boost::thread::id::thread_data 
    // of type boost::detail::thread_data_ptr; 
    // boost::thread::id::operator==(const id&) compares boost::thread::id::thread_data's 
    size_t operator()(boost::thread::id const& id) const { 
     const boost::detail::thread_data_ptr* pptdp = \ 
     reinterpret_cast< boost::detail::thread_data_ptr* >(&id); 
     return h(pptdp->get()); 
    } 
}; 

Nó có thể làm việc, nhưng là cực kỳ giòn và một timebomb gần như được đảm bảo. Nó giả định kiến ​​thức thân mật của các hoạt động bên trong của việc thực hiện thread::id. Nó sẽ khiến bạn bị các nhà phát triển khác nguyền rủa. Đừng làm điều đó nếu khả năng bảo trì là bất kỳ mối quan ngại nào! Thậm chí vá boost/thread/detail/thread.hpp để thêm size_t hash_value(const id& tid) làm bạn của thread::id là "tốt hơn". :)

Answer 2

Tại sao bạn muốn lưu trữ các bộ này trong một bộ. Trừ khi bạn làm điều gì đó bình thường, sẽ có một số lượng nhỏ các chủ đề. Chi phí của việc duy trì một bộ có lẽ cao hơn so với việc đặt chúng vào một véc tơ và thực hiện tìm kiếm tuyến tính.

Nếu tìm kiếm sẽ xảy ra thường xuyên hơn việc thêm và xóa, bạn chỉ có thể sử dụng véc tơ được sắp xếp. Có một toán tử < được định nghĩa để tăng :: thread :: id, vì vậy bạn có thể sắp xếp vectơ (hoặc chèn vào đúng vị trí) sau mỗi lần thêm hoặc xóa và sử dụng lower_bound() để thực hiện tìm kiếm nhị phân. Đây là sự phức tạp tương tự như tìm kiếm một tập hợp và phải có chi phí thấp hơn cho một lượng nhỏ dữ liệu.

Nếu bạn vẫn cần phải làm điều này, làm thế nào về việc xử lý nó như là một sizeof (boost :: thread: id) byte, và hoạt động trên những người.

Ví dụ này giả định rằng kích thước tăng :: thread :: id là bội số của kích thước của int và không có đóng gói và không có chức năng ảo. Nếu điều đó không đúng, nó sẽ phải được sửa đổi, hoặc sẽ không hoạt động chút nào.

EDIT: Tôi đã xem qua lớp boost::thread::id và có một thành viên là boost::shared_pointer<>, vì vậy mã bên dưới bị hỏng khủng khiếp. Tôi nghĩ giải pháp duy nhất là để các tác giả của boost::thread thêm hàm băm. Tôi để lại ví dụ chỉ trong trường hợp nó hữu ích trong một số bối cảnh khác.

boost::thread::id id; 
unsigned* data; 
// The next line doesn't do anything useful in this case. 
data = reinterpret_cast<unsigned *>(&id); 
unsigned hash = 0; 

for (unsigned int i = 0; i < sizeof(boost::thread::id)/4; i++) 
    hash ^= data[i]; 

Answer 3

Câu hỏi đặt ra là tại sao bạn lại muốn thực sự sử dụng một băm?

Tôi hiểu vấn đề với map/set đối với mã quan trọng hiệu suất, thực sự những vùng chứa đó không thân thiện với bộ nhớ cache vì các mục có thể được cấp phát tại các vị trí bộ nhớ rất khác nhau. Như KeithB đề xuất (Tôi sẽ không bình luận về việc sử dụng biểu diễn nhị phân vì không có gì đảm bảo rằng 2 id có cùng biểu diễn nhị phân sau tất cả ...), sử dụng một sắp xếp vector có thể tăng tốc mã trong trường hợp có rất vài mục.

Sắp xếp các vectơ/deques thân thiện với bộ nhớ cache hơn nhiều, tuy nhiên chúng phải chịu sự phức tạp của O (N) khi chèn/xóa vì sao chép liên quan. Một khi bạn đạt đến một vài trăm chủ đề (không bao giờ thấy rằng nhiều bằng cách này), nó có thể bị tổn thương.

Tuy nhiên, cấu trúc dữ liệu cố gắng kết hợp các lợi ích từ bản đồ và vectơ được sắp xếp: B+Tree.

Bạn có thể xem nó dưới dạng bản đồ mà mỗi nút sẽ chứa nhiều hơn một phần tử (theo thứ tự được sắp xếp). Chỉ có các nút lá được sử dụng.

Để nhận được một số hiệu suất hơn bạn có thể:

• Liên kết lá tuyến tính: tức là gốc lưu trữ một con trỏ đến lá đầu tiên và cuối cùng và lá được kết nối với nhau mình, do đó du lịch tuyến tính hoàn toàn bỏ qua các interal nút.
• Cache lá được truy cập cuối cùng vào thư mục gốc, sau khi tất cả có khả năng cũng sẽ là lá tiếp theo được truy cập.

Biểu diễn tiệm cận giống với bản đồ vì nó được thực hiện như một cây nhị phân cân bằng, nhưng vì giá trị được đóng gói theo nhóm, nên mã của bạn có thể nhanh hơn theo hằng số.

Khó khăn thực sự là điều chỉnh kích thước của từng "nhóm", bạn sẽ cần một số lược tả cho điều đó, vì vậy sẽ tốt hơn nếu triển khai của bạn cho phép một số tùy chỉnh ở đó (vì nó sẽ phụ thuộc vào kiến ​​trúc mà mã được thực hiện).

Answer 4

bạn có thể tạo lớp ánh xạ giữa thread :: id và một cái gì đó (ví dụ: số nguyên), mà bạn có thể sử dụng làm băm. hạn chế duy nhất là bạn phải đảm bảo chỉ có một thể hiện của đối tượng ánh xạ trong hệ thống.

Answer 5

Một số năm cuối để trả lời câu hỏi này, nhưng điều này cho thấy là một trong những có liên quan nhất khi cố gắng để đặt một tăng :: thread :: id trong một std :: unordered_map là chìa khóa.Bắt xử lý gốc là một gợi ý tốt trong câu trả lời được chấp nhận ngoại trừ việc nó không có sẵn cho this_thread.

Thay vì đẩy mạnh cho đôi khi có một hash_value cho chủ đề :: id, vì vậy đây đã làm việc tốt cho tôi:

namespace boost { 
    extern std::size_t hash_value(const thread::id &v); 
} 

namespace std { 
    template<> 
    struct hash<boost::thread::id> { 
    std::size_t operator()(const boost::thread::id& v) const { 
     return boost::hash_value(v); 
    } 
    }; 
} 

Tất nhiên, cần phải liên kết với thư viện libboost_thread.