Tại sao vector nhanh hơn bản đồ trong một thử nghiệm, nhưng không phải là bản đồ kia?

Question

Tôi đã luôn luôn được nói với vectơ là nhanh chóng, và trong những năm kinh nghiệm lập trình của tôi, tôi chưa bao giờ thấy bất cứ điều gì để ký hợp đồng đó. Tôi quyết định (tối ưu hóa sớm và) viết một lớp kết hợp mà là một wrapper mỏng xung quanh một container tuần tự (cụ thể là ::std::vector và cung cấp giao diện tương tự như ::std::map. Hầu hết các mã đã thực sự dễ dàng, và tôi đã nhận nó làm việc với ít khó khăn. Tuy nhiên, trong các thử nghiệm của tôi về các loại POD có kích thước khác nhau (4 đến 64 byte) và std::strings, với số lượng thay đổi từ tám đến hai nghìn, ::std::map::find nhanh hơn ::associative::find của tôi, thường nhanh hơn khoảng 15%, cho hầu hết tất cả các thử nghiệm Tôi đã thực hiện một số Short, Self Contained, Correct (Compilable), Example cho thấy rõ ràng điều này at ideone Tôi đã kiểm tra việc thực hiện MSVC9 của ::std::map::find và xác nhận rằng nó khớp với mã số vecfind và ::std::lower_bound của mình khá chặt chẽ, và không thể giải thích tại sao số ::std::map::find chạy nhanh hơn, ngoại trừ một cuộc thảo luận về Stack Overflow, nơi mọi người suy đoán rằng phương thức tìm kiếm nhị phân không có lợi gì cả từ địa phương của vector cho đến lần so sánh cuối cùng (làm cho nó không nhanh hơn), và nó yêu cầu số học con trỏ mà các nút ::std::map không yêu cầu, làm cho nó chậm hơn.

Hôm nay có người thách thức tôi về vấn đề này và cung cấp this code at ideone, khi tôi kiểm tra, cho thấy véc tơ nhanh gấp hai lần.

Các lập trình viên của StackOverflow có muốn khai sáng cho tôi về sự khác biệt rõ ràng này không? Tôi đã đi qua cả hai bộ mã, và họ có vẻ euqivalent với tôi, nhưng có lẽ tôi mù từ chơi với cả hai người trong số họ rất nhiều.

(Footnote: đây là rất gần-one of my previous questions, nhưng mã của tôi đã có một vài lỗi mà đã được giải quyết Do thông tin mới/code, tôi cảm thấy đây là khác nhau, đủ để biện minh cho một câu hỏi riêng biệt Nếu không, tôi.. . ll việc sáp nhập chúng)

Answer 1

Tôi thấy một số vấn đề với mã (http://ideone.com/41iKt) mà bạn đã đăng trên ideone.com. (ideone thực sự hiển thị vector nhanh hơn, nhưng bản dựng cục bộ với Bản xem trước dành cho nhà phát triển Visual Studio 11 hiển thị nhanh hơn map).

Trước tiên, tôi đã di chuyển biến bản đồ và sử dụng nó để khởi tạo vectơ để nhận được cùng một phần tử đặt hàng và sắp xếp, sau đó tôi đã cung cấp lower_bound so sánh tùy chỉnh chỉ so sánh first, vì đó là bản đồ sẽ làm. Sau khi những thay đổi này Visual Studio 11 cho thấy vectơ nhanh hơn cho cùng 100.000 phần tử (mặc dù thời gian ideone không thay đổi đáng kể). http://ideone.com/b3OnH

Với test_size giảm xuống còn 8 bản đồ vẫn nhanh hơn. Điều này không có gì ngạc nhiên vì đây là cách mà thuật toán phức tạp hoạt động, tất cả các hằng số trong hàm thực sự mô tả vấn đề thời gian chạy với N. nhỏ. Tôi phải tăng test_size lên khoảng 2700 để vectơ kéo và thậm chí trước bản đồ hệ thống này.

Answer 2

Một sắp xếp std :: vector có hai ưu điểm so với std :: bản đồ:

địa phương

• Better dữ liệu: các cửa hàng vector tất cả dữ liệu liên tục kế nhau trong bộ nhớ
• nhỏ hơn bộ nhớ: vector không cần nhiều sổ sách kế toán ta (ví dụ: không có đối tượng nút cây)

Liệu hai hiệu ứng này có phụ thuộc vào kịch bản hay không. Có hai yếu tố có khả năng có tác động lớn:

Data type

Đó là một lợi thế cho các std :: vector nếu các yếu tố là loại nguyên thủy như số nguyên. Trong trường hợp đó, địa phương thực sự hữu ích vì tất cả dữ liệu cần thiết cho việc tìm kiếm nằm ở vị trí tiếp giáp trong bộ nhớ.

Nếu các phần tử là chuỗi, thì địa phương không giúp ích nhiều. Bộ nhớ vector liền kề hiện chỉ lưu trữ các đối tượng con trỏ có khả năng trên toàn bộ vùng heap.

kích thước dữ liệu

Nếu std :: vector phù hợp với một cấp bộ nhớ cache cụ thể nhưng std :: bản đồ không, std :: vector sẽ có một lợi thế. Đây là đặc biệt là trường hợp nếu bạn tiếp tục lặp lại thử nghiệm trên cùng một dữ liệu.

Answer 3

Điều gì khiến bạn nghĩ rằng mapfind() nhanh hơn vecfind()?

Đầu ra ideone cho mã của bạn báo cáo thêm 50% số lần truy cập cho mapfind() so với vecfind(). Chạy mã ở đây (x86_64 linux, g ++ - 4.5.1), mapfind() mất khoảng hai lần miễn là vecfind().

Làm cho bản đồ/vectơ lớn hơn theo hệ số 10, chênh lệch tăng lên khoảng 3 ×.

Lưu ý rằng tổng của các thành phần thứ hai là khác nhau. Bản đồ chỉ chứa một cặp với bất kỳ thành phần đầu tiên nào (với PRNG cục bộ của tôi, tạo ra một bản đồ hai phần tử ngắn), trong khi vector có thể chứa nhiều cặp như vậy.

Answer 4

Số lượng phần tử bạn đưa vào vùng chứa thử nghiệm nhiều hơn số lượng kết quả có thể từ rand() trong Microsoft, do đó bạn sẽ nhận được số lặp lại. Các vector được sắp xếp sẽ chứa tất cả chúng trong khi map sẽ ném ra các bản sao. Kiểm tra kích thước sau khi điền chúng - vector sẽ có 100000 phần tử, bản đồ 32768. Vì bản đồ ngắn hơn nhiều, tất nhiên nó sẽ có hiệu suất tốt hơn.

Hãy thử một multimap để so sánh táo-to-táo.