Container STL nào là tốt nhất cho std :: sort? (Liệu nó có quan trọng không?)

Question

Tiêu đề nói cho chính nó ....

Lựa chọn container có ảnh hưởng đến tốc độ của thuật toán sắp xếp theo mặc định hay không? Ví dụ, nếu tôi sử dụng danh sách, thuật toán sắp xếp chỉ chuyển đổi các nút con trỏ hay nó chuyển toàn bộ dữ liệu trong các nút?

Answer 1

Tôi không nghĩ rằng std::sort hoạt động trên danh sách vì nó yêu cầu trình lặp truy cập ngẫu nhiên không được cung cấp bởi list<>. Lưu ý rằng list<> cung cấp phương thức sort nhưng hoàn toàn tách biệt với std::sort.

Lựa chọn container không quan trọng. STL's std::sort dựa trên các trình vòng lặp để trừu tượng hóa cách thức một kho chứa dữ liệu lưu trữ. Nó chỉ sử dụng các trình vòng lặp mà bạn cung cấp để di chuyển các phần tử xung quanh. Các trình vòng lặp nhanh hơn hoạt động về mặt truy cập và gán một phần tử, nhanh hơn std::sort sẽ hoạt động.

Answer 2

Tùy thuộc vào loại phần tử.

Nếu bạn chỉ lưu trữ con trỏ (hoặc POD) thì vector sẽ nhanh nhất. Nếu bạn đang lưu trữ các đối tượng thì sắp xếp của danh sách sẽ nhanh hơn vì nó sẽ hoán đổi các nút và không phải các phần tử vật lý.

Answer 3

Thuật toán sắp xếp không biết gì về vùng chứa của bạn. Tất cả những gì nó biết là các trình vòng lặp truy cập ngẫu nhiên. Vì vậy, bạn có thể sắp xếp những thứ mà thậm chí không có trong một container STL. Vì vậy, nó sẽ nhanh như thế nào phụ thuộc vào các trình vòng lặp mà bạn cung cấp cho nó và tốc độ của nó là dereference và sao chép những gì chúng trỏ đến.

std :: sắp xếp sẽ không hoạt động trên std :: danh sách, vì sắp xếp yêu cầu trình vòng lặp truy cập ngẫu nhiên. Bạn nên sử dụng một trong các hàm std :: list's list cho trường hợp đó. Các hàm thành viên đó sẽ hoán đổi hiệu quả các con trỏ danh sách được liên kết thay vì sao chép các phần tử.

Answer 4

std::list chắc chắn không phải là lựa chọn tốt (hợp lệ) cho std::sort(), vì std::sort() yêu cầu trình vòng lặp truy cập ngẫu nhiên. std::map và bạn bè cũng không tốt vì vị trí của một phần tử không thể được thực thi; có nghĩa là, vị trí của một phần tử trong bản đồ không thể được thực thi bởi người dùng với việc chèn vào một vị trí cụ thể hoặc một trao đổi. Trong số các vùng chứa tiêu chuẩn, chúng tôi xuống đến std::vector và std::deque.

std::sort() giống như các thuật toán chuẩn khác ở chỗ nó chỉ hoạt động bằng cách hoán đổi các giá trị của các phần tử xung quanh (*t = *s). Vì vậy, ngay cả khi danh sách kỳ diệu sẽ hỗ trợ O (1) truy cập vào các liên kết sẽ không được tổ chức lại nhưng thay vào đó giá trị của chúng sẽ được hoán đổi.

Vì std::sort() không thay đổi kích thước của vùng chứa nên không có sự khác biệt về hiệu suất thời gian chạy cho dù bạn sử dụng std::vector hoặc std::deque. Các mảng nguyên thủy cũng phải nhanh để sắp xếp, thậm chí có thể nhanh hơn các thùng chứa tiêu chuẩn - nhưng tôi không mong đợi sự khác biệt về tốc độ đủ đáng kể để biện minh cho việc sử dụng chúng.

Answer 5

Nó chắc chắn không quan trọng, chỉ vì các thùng chứa khác nhau có các mẫu truy cập bộ nhớ khác nhau, vv có thể đóng vai trò.

Tuy nhiên, std::sort không hoạt động trên std::list<>::iterators vì đây không phải là RandomAccessIterators. Hơn nữa, mặc dù nó sẽ có thể thực hiện một chuyên môn cho std::list<> mà sẽ shuffle con trỏ của các nút, nó có lẽ sẽ có những hậu quả ngữ nghĩa kỳ lạ và đáng ngạc nhiên - ví dụ.nếu bạn có một vòng lặp trong phạm vi được sắp xếp trong một vectơ, giá trị của nó sẽ thay đổi sau khi sắp xếp, điều này sẽ không đúng với chuyên môn này.

Answer 6

Lựa chọn không tạo sự khác biệt, nhưng dự đoán vùng chứa nào hiệu quả nhất là rất khó. Cách tiếp cận tốt nhất là sử dụng vùng chứa dễ nhất để ứng dụng của bạn làm việc với (có thể là std :: vector), xem liệu sắp xếp có đủ nhanh với vùng chứa đó hay không và nếu nó dính vào nó. Nếu không, hãy lập hồ sơ hiệu suất về vấn đề phân loại của bạn và chọn vùng chứa khác nhau dựa trên dữ liệu tiểu sử.

Là một cựu giảng viên và cựu huấn luyện viên, đôi khi tôi cảm thấy cá nhân chịu trách nhiệm về ý tưởng chung rằng danh sách được liên kết có các đặc tính nâng cao hiệu suất thần bí. Lấy nó từ một người biết: lý do duy nhất một danh sách liên kết xuất hiện trong rất nhiều sách và hướng dẫn là vì nó là giao ước cho những người đã viết những cuốn sách và hướng dẫn đó để có cấu trúc dữ liệu có thể minh họa con trỏ, bộ nhớ động mangement, đệ quy , tìm kiếm và sắp xếp tất cả trong một - nó không liên quan gì đến hiệu quả.

Answer 7

std :: sắp xếp yêu cầu trình vòng lặp truy cập ngẫu nhiên, do đó, các tùy chọn duy nhất của bạn để sử dụng đó là véc tơ hoặc deque. Nó sẽ trao đổi các giá trị, và tại một vector đoán có thể sẽ thực hiện nhanh hơn một chút so với deque vì nó thường có cấu trúc dữ liệu cơ bản đơn giản hơn. Sự khác biệt là rất có thể rất mặc dù.

Nếu bạn sử dụng tiêu đề :: danh sách, có một chuyên môn (std :: list :: sort) sẽ trao đổi con trỏ thay vì giá trị. Tuy nhiên vì nó không truy cập ngẫu nhiên, nó sẽ sử dụng mergesort thay vì quicksort, điều này có thể có nghĩa là thuật toán tự nó chậm hơn một chút.

Dù sao, tôi nghĩ câu trả lời thường là vectơ. Nếu bạn có các lớp học lớn cho mỗi phần tử để sao chép chi phí chiếm ưu thế trong quá trình sắp xếp, danh sách có thể đánh bại nó. Hoặc cách khác bạn có thể lưu trữ con trỏ cho chúng trong một vectơ và cung cấp một vị từ tùy chỉnh để sắp xếp chúng một cách thích hợp.

Answer 8

Vector.

Luôn sử dụng vector làm mặc định của bạn. Nó có chi phí đầu vào không gian thấp nhất và truy cập nhanh nhất của bất kỳ vùng chứa nào khác (trong số các ưu điểm khác như bố cục tương thích với C và trình vòng lặp truy cập ngẫu nhiên).

Bây giờ, hãy tự hỏi - bạn đang làm gì khác với vùng chứa của mình? Bạn có cần bảo đảm ngoại lệ mạnh mẽ không? Danh sách, thiết lập và bản đồ có thể là lựa chọn tốt hơn (mặc dù tất cả đều có thói quen sắp xếp riêng của họ). Bạn có cần thường xuyên thêm các phần tử vào mặt trước của vùng chứa không? Hãy xem xét deque. Vùng chứa của bạn có cần luôn luôn được sắp xếp không? Đặt và bản đồ có thể phù hợp hơn.

Cuối cùng, tìm hiểu cụ thể những gì "tốt nhất" là dành cho bạn và sau đó chọn vùng chứa thích hợp nhất và đo lường cách thức hoạt động cho nhu cầu của bạn.

Answer 9

Tôi hoàn toàn đồng ý với các tuyên bố mà những người đã đăng ở trên. Nhưng cách tốt nhất để học những điều mới là gì? Chào!!!! chắc chắn không đọc văn bản và học thuộc lòng nhưng .... VÍ DỤ: D Như Gần đây tôi đã đắm mình trong container quy định tại STL, đây là mã kiểm tra nhanh chóng mà là tự giải thích, tôi hy vọng:

#include <iostream> 
#include <vector> 
#include <deque> 
#include <array> 
#include <list> 
#include <iterator> 
#include <cstdlib> 
#include <algorithm> 
#include "Timer.h" 

constexpr int SIZE = 1005000; 

using namespace std; 

void test(); 

int main(){ 
    cout<<"array allocates "<<static_cast<double>(SIZE)/(1024*1024)<<" MB\n"; 
    test(); 


    return 0; 
} 


void test(){ 
    int values[SIZE]; 
    int size = 0; 

    //init values to sort: 
    do{ 
     values[size++] = rand() % 100000; 
    }while(size < SIZE); 

    //feed array with values: 
    array<int, SIZE> container_1; 
    for(int i = 0; i < SIZE; i++) 
     container_1.at(i) = values[i]; 

    //feed vector with values 
    vector<int> container_2(begin(values), end(values)); 
    list<int> container_3(begin(values), end(values)); 
    deque<int> container_4(begin(values), end(values)); 

    //meassure sorting time for containers 
    { 
     Timer t1("sort array"); 
     sort(container_1.begin(), container_1.end()); 
    } 

    { 
     Timer t2("sort vector"); 
     sort(container_2.begin(), container_2.end()); 
    } 

    { 
     Timer t3("sort list"); 
     container_3.sort(); 
    } 

    { 
     Timer t4("sort deque"); 
     sort(container_4.begin(), container_4.end()); 
    } 

} 

Và mã cho timer:

#include <chrono> 
#include <string> 
#include <iostream> 

using namespace std; 

class Timer{ 

public: 
    Timer(string name = "unnamed") : mName(name){ mStart = chrono::system_clock::now();} 
    ~Timer(){cout<<"action "<<mName<<" took: "<< 
      chrono::duration_cast<chrono::milliseconds>(
        chrono::system_clock::now() - mStart).count()<<"ms"<<endl;} 
private: 
    chrono::system_clock::time_point mStart; 
    string mName; 
}; 

Dưới đây là kết quả khi không tối ưu hóa được sử dụng (g ++ --std = C++ 11 file.cpp -o a.ou t):

mảng phân bổ 0,958443 MB
hành động kiểu mảng mất: 183ms
hành động loại vector mất: 316ms
hành động danh sách loại mất: 725ms
hành động loại deque mất: 436ms

và tối ưu hóa (g ++ -O3 --std = C++ 11 tệp.cpp -o a.out):

mảng phân bổ 0.958443 MB
hành động kiểu mảng mất: 55ms
hành động loại vector mất: 57ms
hành động danh sách loại mất: 264ms
hành động loại deque mất: 67ms

Chú ý rằng mặc dù vector và mảng có tương tự lần phân loại cho trường hợp này, kích thước mảng bị giới hạn vì nó được cho là được khởi tạo trên ngăn xếp (theo mặc định, không sử dụng phân bổ của riêng v.v.)

Vì vậy, nó cũng phụ thuộc vào việc bạn sử dụng tối ưu hóa cho trình biên dịch. thấy sự khác biệt đáng chú ý.