hiệu suất bản đồ stl?

Question

Tôi đang sử dụng map<MyStruct, I*> map1;. Rõ ràng 9% tổng thời gian ứng dụng của tôi được chi tiêu trong đó. Cụ thể trên một dòng của một trong những chức năng chính của tôi. Bản đồ không phải là rất lớn (< 1k hầu như luôn luôn, < 20 là phổ biến).

Có triển khai thay thế nào mà tôi có thể muốn sử dụng không? Tôi nghĩ rằng tôi không nên viết của riêng tôi nhưng tôi có thể nếu tôi nghĩ rằng đó là một ý tưởng tốt.

Thông tin bổ sung: Tôi luôn kiểm tra trước khi thêm phần tử. Nếu một khóa tồn tại tôi cần báo cáo một vấn đề. Hơn sau một thời điểm tôi sẽ sử dụng bản đồ rất nhiều cho tra cứu và sẽ không thêm bất kỳ yếu tố nào nữa.

Answer 1

Sẽ nhanh hơn khi chỉ cần thực hiện insert và kiểm tra xem pair.second có phải là false nếu khóa đã tồn tại không?

như thế này

if (myMap.insert(make_pair(MyStruct, I*)).second == false) 
{ 
    //report error 
} 
else 
    // inserted new value 

chứ không phải làm một cuộc gọi find mỗi lần?

Answer 2

Cách bạn đang sử dụng bản đồ, bạn đang thực hiện tra cứu trên cơ sở cá thể MyStruct và tùy thuộc vào việc triển khai cụ thể của bạn, so sánh được yêu cầu có thể hoặc không tốn kém.

Answer 3

Nó có thể là một cảnh quay dài, nhưng đối với các bộ sưu tập nhỏ, đôi khi yếu tố quan trọng nhất là hiệu suất cache.

Kể từ std::map thực hiện một cây đỏ-đen, đó là [AFAIK] không phải là rất nhớ cache hiệu quả - có thể thực hiện bản đồ dưới dạng std::vector<pair<MyStruct,I*>> sẽ là một ý tưởng tốt, và sử dụng tìm kiếm nhị phân có [thay vì bản đồ look-up] , ít nhất nó sẽ hiệu quả một khi bạn bắt đầu chỉ tìm kiếm [ngừng chèn các yếu tố], vì std::vector có nhiều khả năng phù hợp với bộ nhớ cache hơn so với map.

Yếu tố này [cpu-cache] thường bị bỏ qua và được ẩn là hằng số trong ký hiệu O lớn, nhưng đối với các bộ sưu tập lớn, nó có thể có tác động lớn.

Answer 4

Có triển khai thay thế nào mà tôi có thể muốn sử dụng không? Tôi nghĩ rằng tôi không nên viết của riêng tôi nhưng tôi có thể nếu tôi nghĩ rằng đó là một ý tưởng tốt.

Nếu bạn hiểu vấn đề đủ tốt, bạn nên nêu chi tiết cách triển khai của bạn sẽ vượt trội.

Có phải cấu trúc thích hợp là map? Nếu có, thì việc triển khai thư viện chuẩn của bạn sẽ có chất lượng tốt (được tối ưu hóa tốt).

Có thể đơn giản hóa việc so sánh MyStruct không?

Sự cố - thay đổi kích thước ở đâu? tra cứu?

Bạn có thu nhỏ bản sao và chỉ định chi phí cho cấu trúc của mình không?

Answer 5

Thay vì map bạn có thể thử unordered_map sử dụng khóa băm thay cho cây để tìm phần tử. This answer đưa ra một số gợi ý khi thích unordered_map trên map.

Answer 6

Trước tiên, bạn cần phải hiểu bản đồ là gì và các hoạt động mà bạn đang thực hiện đại diện. A std::map là cây nhị phân cân bằng, tra cứu sẽ thực hiện các hoạt động O(log N), mỗi thao tác là so sánh các phím cộng với một số phụ mà bạn có thể bỏ qua trong hầu hết các trường hợp (quản lý con trỏ). Chèn mất khoảng thời gian tương tự để xác định vị trí điểm chèn, cộng với phân bổ của nút mới, chèn thực tế vào cây và cân bằng lại. Độ phức tạp lại một lần nữa là O(log N) mặc dù các hằng số ẩn cao hơn.

Khi bạn cố gắng xác định xem liệu khóa có nằm trong bản đồ trước khi chèn hay không, bạn sẽ phải trả chi phí tra cứu và nếu nó không thành công, chi phí giống nhau để xác định vị trí chèn. Bạn có thể tránh chi phí thêm bằng cách sử dụng std::map::insert trả về một cặp với một trình lặp và một bool cho bạn biết liệu việc chèn thực sự xảy ra hay phần tử đã có sẵn. Ngoài ra, bạn cần phải hiểu cách so sánh các khóa của mình tốn kém, những gì nằm ngoài câu hỏi hiển thị (MyStruct có thể chỉ giữ một int hoặc một nghìn trong số đó), đó là thứ bạn cần phải đưa vào tài khoản. Cuối cùng, có thể là trường hợp mà map không phải là cấu trúc dữ liệu hiệu quả nhất cho nhu cầu của bạn và bạn có thể cân nhắc sử dụng std::unordered_map (bảng băm) đã dự kiến ​​chèn thời gian liên tục (nếu hàm băm không phải là khủng khiếp) hoặc cho các tập dữ liệu nhỏ ngay cả một mảng được sắp xếp đơn giản (hoặc std::vector) mà bạn có thể sử dụng tìm kiếm nhị phân để xác định vị trí các yếu tố (điều này sẽ giảm số lượng phân bổ, với chi phí chèn tiền đắt hơn) các loại được tổ chức đủ nhỏ có thể đáng giá)

Như thường lệ với hiệu suất, đo lường và sau đó cố gắng hiểu thời gian đang được sử dụng. Cũng lưu ý rằng 10% thời gian dành cho một hàm hoặc cấu trúc dữ liệu cụ thể có thể là rất nhiều hoặc gần như không có gì, tùy thuộc vào ứng dụng của bạn là gì. Ví dụ: nếu ứng dụng của bạn chỉ thực hiện tra cứu và chèn vào bộ dữ liệu và chỉ mất 10% CPU bạn có rất nhiều để tối ưu hóa ở mọi nơi khác!

Answer 7

Như đã nêu trong các nhận xét, không có mã thích hợp, có rất ít câu trả lời phổ quát để cung cấp cho bạn. Tuy nhiên, nếu MyStruct thực sự rất lớn, việc sao chép ngăn xếp có thể tốn kém. Có lẽ nó làm cho tinh thần để lưu trữ các con trỏ tới MyStruct và thực hiện so sánh cơ chế của riêng bạn:

template <typename T> struct deref_cmp { 
    bool operator()(std::shared_ptr<T> lhs, std::shared_ptr<T> rhs) const { 
    return *lhs < *rhs; 
    } 
}; 

std::map<std::shared_ptr<MyStruct>, I*, deref_cmp<MyStruct>> mymap; 

Tuy nhiên, đây là một cái gì đó bạn sẽ phải cấu. Nó có thể tăng tốc độ.

Bạn sẽ nhìn lên một yếu tố như

template <typename T> struct NullDeleter { 
    void operator()(T const*) const {} 
}; 
// needle being a MyStruct 
mymap.find(std::shared_ptr<MyStruct>(&needle,NullDeleter())); 

Không cần điều này để nói, có nhiều tiềm năng để tối ưu hóa.