C++: Cách nhanh nhất để sắp xếp danh sách số và chỉ mục của chúng

Question

Tôi có một câu hỏi có vẻ rất cơ bản, nhưng trong ngữ cảnh "mọi dấu tích CPU" (đây là một phần của thuật toán lớn hơn được sử dụng trên các siêu máy tính).

Vấn đề khá đơn giản: cách nhanh nhất để sắp xếp danh sách các số int dài chưa ký và chỉ mục gốc của chúng là gì? (. Lúc đầu, các unsigned long int số dài đang ở trong một trật tự hoàn toàn ngẫu nhiên)

Example : 
Before 
Numbers: 32 91 11 72 
Indexes: 0 1 2 3 
After 
Numbers: 11 32 72 91 
Indexes: 2 0 3 1 

By "Cách nhanh nhất", tôi có nghĩa là: những gì thuật toán sử dụng: std :: sort, C qsort, hay cách khác thuật toán sắp xếp có sẵn trên web? Những gì container để sử dụng (mảng C, std :: vector, std :: map ...)? Làm thế nào để sắp xếp các chỉ mục cùng một lúc (sử dụng cấu trúc, std :: pair, std :: map ...)?

Cảm ơn bạn rất nhiều!

CHỈNH SỬA: có bao nhiêu phần tử cần sắp xếp? -> thường là 4Go số

Answer 1

Điểm khởi đầu rõ ràng sẽ là một cấu trúc với operator< định nghĩa cho nó:

struct data { 
    unsigned long long int number; 
    size_t index; 
}; 

struct by_number { 
    bool operator()(data const &left, data const &right) { 
     return left.number < right.number; 
    } 
}; 

... và một std :: vector để giữ dữ liệu:

std::vector<data> items; 

và std::sort để làm phân loại:

std::sort(items.begin(), items.end(), by_number()); 

Sự thật đơn giản là, rằng container bình thường (và như vậy) là đủ hiệu quả mà sử dụng chúng không làm cho mã của bạn đáng kể kém hiệu quả. Bạn có thể có thể làm tốt hơn bằng cách viết một số phần theo cách khác, nhưng bạn có thể dễ dàng làm tồi tệ hơn. Bắt đầu từ rắn và dễ đọc, và thử nghiệm - không (cố gắng) tối ưu hóa sớm.

Chỉnh sửa: tất nhiên trong C++ 11, bạn có thể sử dụng một biểu thức lambda thay vì:

std::sort(items.begin(), items.end(), 
      [](data const &a, data const &b) { return a.number < b.number; }); 

này thường là thuận tiện hơn một chút để viết. Dễ đọc phụ thuộc - cho một cái gì đó đơn giản như thế này, tôi muốn nói sort ... by_number là khá dễ đọc, nhưng điều đó phụ thuộc (rất nhiều) vào tên bạn cung cấp cho các nhà điều hành so sánh. Lambda làm cho các tiêu chí phân loại thực tế dễ tìm hơn, do đó bạn không cần phải chọn một tên cẩn thận để mã có thể đọc được.

Answer 2

Sử dụng std::vector và std::sort. Điều đó sẽ cung cấp phương pháp sắp xếp nhanh nhất. Để Tìm chỉ mục gốc tạo cấu trúc.

struct A { 
    int num; 
    int index; 
} 

Sau đó thực hiện so sánh của riêng Bạn Phân loại để so sánh số trong cấu trúc.

struct Predicate { 
    bool operator()(const A first, const A second) { 
     return first.num < second.num; 
    } 
} 

std::sort(vec.begin(), vec.end(), Predicate())

Answer 3

struct SomeValue 
{ 
    unsigned long long val; 
    size_t index; 
    bool operator<(const SomeValue& rhs)const 
    { 
     return val < rhs.val; 
    } 
} 

#include <algorithm> 
std::vector<SomeValue> somevec; 
//fill it... 
std::sort(somevec.begin(),somevec.end()); 

Answer 4

std::pair và std::sort phù hợp với yêu cầu của bạn lý tưởng: nếu bạn đặt giá trị vào pair.first và chỉ số trong pair.second, bạn chỉ có thể gọi một sort trên một vector của pair s, như thế này:

// This is your original data. It does not need to be in a vector 
vector<long> orig; 
orig.push_back(10); 
orig.push_back(3); 
orig.push_back(6); 
orig.push_back(11); 
orig.push_back(2); 
orig.push_back(19); 
orig.push_back(7); 
// This is a vector of {value,index} pairs 
vector<pair<long,size_t> > vp; 
vp.reserve(orig.size()); 
for (size_t i = 0 ; i != orig.size() ; i++) { 
    vp.push_back(make_pair(orig[i], i)); 
} 
// Sorting will put lower values ahead of larger ones, 
// resolving ties using the original index 
sort(vp.begin(), vp.end()); 
for (size_t i = 0 ; i != vp.size() ; i++) { 
    cout << vp[i].first << " " << vp[i].second << endl; 
} 

Answer 5

std::sort đã được chứng minh là nhanh hơn so với cũ qsort vì thiếu sự vô hướng và khả năng nội tuyến các hoạt động quan trọng.

Việc triển khai std::sort có khả năng được tối ưu hóa cao và khó đánh bại, nhưng không phải là không thể. Nếu dữ liệu của bạn có độ dài cố định và ngắn bạn có thể tìm thấy Radix sort để nhanh hơn. Timsort tương đối mới và đã mang lại kết quả tốt cho Python.

Bạn có thể giữ mảng chỉ mục tách biệt khỏi mảng giá trị, nhưng tôi nghĩ mức độ gián tiếp bổ sung sẽ chứng minh là kẻ giết người tốc độ. Tốt hơn là giữ chúng lại với nhau trong một cấu trúc hoặc std::pair.

Như mọi khi với bất kỳ ứng dụng quan trọng tốc độ nào, bạn phải thử một số triển khai thực tế và so sánh chúng để biết chắc chắn đó là nhanh nhất.

Answer 6

Điều này sẽ được sử dụng trên các siêu máy tính?

Trong trường hợp đó, bạn có thể muốn xem xét các thuật toán sắp xếp song song. Điều đó sẽ chỉ có ý nghĩa cho việc sắp xếp các tập dữ liệu lớn, nhưng chiến thắng nếu bạn cần nó là đáng kể.

Answer 7

Bạn có thể tìm thấy this để đọc thú vị. Tôi sẽ bắt đầu với loại STL và chỉ sau đó thử và cải thiện nó nếu tôi có thể. Tôi không chắc chắn nếu bạn có quyền truy cập vào một trình biên dịch C++ 11 (như gcc4.7) trên siêu máy tính này, nhưng tôi sẽ đề nghị rằng std :: sort với std :: futures và std :: threads sẽ giúp bạn khá một chút cách có liên quan đến việc song song vấn đề theo một cách duy trì.

Đây là another question so sánh std :: sort with qsort.

Cuối cùng, có this article trong Dr. Dobb so sánh hiệu suất của các thuật toán song song.

Answer 8

Nó thể có giá trị tách số và lập chỉ mục và sau đó chỉ số chỉ sắp xếp, như thế này:

#include <vector> 
#include <algorithm> 
#include <iostream> 

void PrintElements(const std::vector<unsigned long long>& numbers, const std::vector<size_t>& indexes) { 

    std::cout << "\tNumbers:"; 
    for (auto i = indexes.begin(); i != indexes.end(); ++i) 
     std::cout << '\t' << numbers[*i]; 
    std::cout << std::endl; 

    std::cout << "\tIndexes:"; 
    for (auto i = indexes.begin(); i != indexes.end(); ++i) 
     std::cout << '\t' << *i; 
    std::cout << std::endl; 

} 

int main() { 

    std::vector<unsigned long long> numbers; 
    std::vector<size_t> indexes; 

    numbers.reserve(4); // An overkill for this few elements, but important for billions. 
    numbers.push_back(32); 
    numbers.push_back(91); 
    numbers.push_back(11); 
    numbers.push_back(72); 

    indexes.reserve(numbers.capacity()); 
    indexes.push_back(0); 
    indexes.push_back(1); 
    indexes.push_back(2); 
    indexes.push_back(3); 

    std::cout << "BEFORE:" << std::endl; 
    PrintElements(numbers, indexes); 

    std::sort(
     indexes.begin(), 
     indexes.end(), 
     [&numbers](size_t i1, size_t i2) { 
      return numbers[i1] < numbers[i2]; 
     } 
    ); 

    std::cout << "AFTER:" << std::endl; 
    PrintElements(numbers, indexes); 

    return EXIT_SUCCESS; 

} 

này in:

BEFORE: 
     Numbers:  32  91  11  72 
     Indexes:  0  1  2  3 
AFTER: 
     Numbers:  11  32  72  91 
     Indexes:  2  0  3  1 

Ý tưởng được rằng các yếu tố được sắp xếp nhỏ và do đó rất nhanh để di chuyển trong khi sắp xếp. Tuy nhiên, trên các CPU hiện đại, ảnh hưởng của truy cập gián tiếp đến numbers trên bộ nhớ đệm có thể làm hỏng những lợi ích này, vì vậy tôi khuyên bạn nên đánh giá số lượng dữ liệu thực tế trước khi đưa ra quyết định cuối cùng để sử dụng nó.