Tại sao std :: nth_element trả về các vectơ sắp xếp cho các vectơ đầu vào với N <33 phần tử?

Question

Tôi đang sử dụng nth_element để có được một (xấp xỉ đúng) giá trị so với một phần trăm của một vector, như vậy:

double percentile(std::vector<double> &vectorIn, double percent) 
{ 
    std::nth_element(vectorIn.begin(), vectorIn.begin() + (percent*vectorIn.size())/100, vectorIn.end()); 

    return vectorIn[(percent*vectorIn.size())/100]; 
} 

tôi nhận thấy rằng cho độ dài vectorIn lên đến 32 yếu tố, các vector được hoàn toàn được sắp xếp. Bắt đầu từ 33 yếu tố, nó không bao giờ được sắp xếp (như mong đợi).

Không chắc chắn liệu điều này có quan trọng hay không nhưng chức năng nằm trong mã "Matlab-) mex C++" được biên dịch qua Matlab bằng cách sử dụng "Microsoft Windows SDK 7.1 (C++)".

EDIT:

Cũng xem biểu đồ sau đây của độ dài của các khối được sắp xếp dài nhất trong vectơ 1e5 truyền cho hàm (vectơ chứa các yếu tố ngẫu nhiên 1e4 và một phần trăm ngẫu nhiên đã được tính toán). Lưu ý đỉnh ở các giá trị rất nhỏ.

Answer 1

này sẽ thay đổi từ việc thực hiện tiêu chuẩn thư viện để thực hiện tiêu chuẩn thư viện (và có thể khác nhau dựa trên các yếu tố khác) nhưng trong điều kiện chung:

• std :: nth_element được phép sắp xếp lại hộp chứa đầu vào khi nó thấy vừa vặn, với điều kiện là nth_element nằm ở vị trí n và vùng chứa được phân đoạn tại vị trí n.

• Đối với các thùng chứa nhỏ, thường là nhanh hơn để thực hiện sắp xếp đầy đủ hơn so với chọn nhanh, ngay cả khi không thể mở rộng.

Kể từ thư viện tác giả tiêu chuẩn thường sẽ lựa chọn giải pháp nhanh nhất, hầu hết các trường nth_element (và, cho rằng vấn đề, sắp xếp triển khai) sử dụng các thuật toán tùy chỉnh cho đầu vào nhỏ (hoặc cho các phân đoạn nhỏ ở dưới cùng của đệ quy) , có thể sắp xếp container mạnh hơn có vẻ cần thiết. Đối với các vectơ có giá trị vô hướng, việc sắp xếp chèn cực kỳ nhanh, vì nó tận dụng tối đa bộ nhớ cache. Với các phần mở rộng trực tuyến, có thể tăng tốc độ lên nhiều hơn bằng cách so sánh song song.

Bằng cách này, bạn có thể tiết kiệm một lượng nhỏ tính bằng cách chỉ tính toán các iterator ngưỡng một lần, mà có thể dễ đọc hơn:

double percentile(std::vector<double> &vectorIn, double percent) 
{ 
    auto nth = vectorIn.begin() + (percent*vectorIn.size())/100; 
    std::nth_element(vectorIn.begin(), nth, vectorIn.end()); 
    return *nth; 
}