सी ++: संख्या और उनकी अनुक्रमणिका की सूची क्रमबद्ध करने का सबसे तेज़ तरीका

Question

मेरे पास एक प्रश्न है जो बहुत बुनियादी प्रतीत हो सकता है, लेकिन यह एक संदर्भ में है जहां "हर सीपीयू टिक मायने रखता है" (यह एक बड़े एल्गोरिदम का हिस्सा है सुपरकंप्यूटर पर इस्तेमाल किया जाना चाहिए)।

समस्या काफी सरल है: हस्ताक्षरित लंबी लंबी int संख्याओं और उनकी मूल अनुक्रमणिका की सूची को सॉर्ट करने का सबसे तेज़ तरीका क्या है? (। शुरुआत में, अहस्ताक्षरित लंबे int संख्या एक पूरी तरह से यादृच्छिक क्रम में हैं)

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

द्वारा "सबसे तेज़ तरीका है", मेरा मतलब है: क्या एल्गोरिथ्म का उपयोग करें: std :: प्रकार, सी qsort, या किसी अन्य वेब पर उपलब्ध एल्गोरिदम सॉर्टिंग? उपयोग करने के लिए क्या कंटेनर (सी सरणी, std :: वेक्टर, std :: मानचित्र ...)? इंडेक्स को एक ही समय में कैसे सॉर्ट करें (संरचनाओं का उपयोग करें, std :: pair, std :: map ...)?

बहुत बहुत धन्यवाद!

संपादित करें: सॉर्ट करने के लिए कितने तत्व हैं? -> आम तौर पर संख्याओं का 4Go

Answer 1

स्पष्ट प्रारंभिक बिंदु इसके लिए परिभाषित operator< के साथ एक संरचना होगा:

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; 
    } 
}; 

... और एक std :: वेक्टर डेटा रखने के लिए:

std::vector<data> items; 

और std::sort छंटाई करने के लिए:

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

साधारण तथ्य यह है, कि सामान्य कंटेनर (और इस तरह के) पर्याप्त रूप से कुशल है कि उन्हें का उपयोग कर अपने कोड को काफी हद तक कम कुशल नहीं है कर रहे हैं। आप कुछ हिस्सों को एक अलग तरीके से लिखकर बेहतर करने में सक्षम हो सकते हैं, लेकिन आप आसानी से और भी खराब हो सकते हैं। ठोस और पठनीय से शुरू करें, और परीक्षण - समय-समय पर ऑप्टिमाइज़ करने का प्रयास न करें।

संपादित करें:

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

यह आमतौर पर एक छोटे से अधिक सुविधाजनक लिखना है: सी ++ 11 में निश्चित रूप से, आप के बजाय एक लैम्ब्डा अभिव्यक्ति का उपयोग कर सकते हैं। पठनीयता इस बात पर निर्भर करती है - इस तरह के कुछ सरल के लिए, मैं कहूंगा कि sort ... by_number बहुत पठनीय है, लेकिन यह आपके द्वारा तुलना ऑपरेटर को दिए गए नाम पर निर्भर करता है (भारी)। लैम्ब्डा वास्तविक सॉर्टिंग मानदंडों को ढूंढना आसान बनाता है, इसलिए कोड को पढ़ने योग्य होने के लिए आपको सावधानी से नाम चुनने की आवश्यकता नहीं है।

Answer 2

std::vector और std::sort का उपयोग करें। यह सबसे तेज़ सॉर्ट विधि प्रदान करना चाहिए। मूल अनुक्रमणिका ढूंढने के लिए एक संरचना बनाएँ।

struct A { 
    int num; 
    int index; 
} 

फिर अपनी खुद की तुलना करें इस तरह की तुलना करें कि संरचना में संख्या की तुलना करें।

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 और std::sort आदर्श रूप में अपनी आवश्यकताओं फिट: यदि आप pair.first और pair.second में सूचकांक में मूल्य डाल, तो आप बस pair रों का एक वेक्टर पर एक sort कॉल कर सकते हैं, इस तरह:

// 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 संकेतों की कमी और महत्वपूर्ण परिचालनों को रेखांकित करने की संभावना के कारण पुराने qsort की तुलना में तेज़ साबित हुआ है।

std::sort के कार्यान्वयन को अत्यधिक अनुकूलित और कठिन होने की संभावना है, लेकिन असंभव नहीं है। यदि आपका डेटा लंबाई और छोटा तय किया गया है तो आपको तेजी से Radix sort मिल सकता है। Timsort अपेक्षाकृत नया है और पाइथन के लिए अच्छे परिणाम दिए हैं।

आप इंडेक्स सरणी को मूल्य सरणी से अलग रख सकते हैं, लेकिन मुझे लगता है कि संकेत का अतिरिक्त स्तर एक गति हत्यारा साबित होगा। उन्हें एक संरचना या std::pair में एक साथ रखने के लिए बेहतर है।

हमेशा किसी भी गति महत्वपूर्ण अनुप्रयोग के साथ, आपको कुछ वास्तविक कार्यान्वयन करने की कोशिश करनी चाहिए और यह सुनिश्चित करने के लिए उनकी तुलना करें कि सबसे तेज़ कौन सा है।

Answer 6

यह सुपरकंप्यूटर पर उपयोग किया जाएगा?

उस स्थिति में आप समांतर सॉर्टिंग एल्गोरिदम में देखना चाह सकते हैं। यह केवल बड़े डेटा सेट को सॉर्ट करने के लिए समझ में आएगा, लेकिन यदि आपको इसकी आवश्यकता है तो जीत पर्याप्त है।

Answer 7

आपको एक दिलचस्प पढ़ने के लिए this मिल सकता है। मैं एसटीएल के प्रकार से शुरू करूंगा और केवल तभी प्रयास कर सकता हूं जब मैं कर सकूं। मुझे यकीन नहीं है कि क्या आपके पास इस सुपर कंप्यूटर पर सी ++ 11 कंपाइलर (जैसे gcc4.7) तक पहुंच है, लेकिन मैं सुझाव दूंगा कि std :: fdures और std :: threads के साथ std :: sort आपको काफी मिल जाएगा एक बनाए रखने योग्य तरीके से समस्या को समानांतर करने के संबंध में वहां कुछ रास्ता है।

यहां another question है जो qsort के साथ std :: sort की तुलना करता है।

अंत में, डॉ। डॉबब में this article है जो समांतर एल्गोरिदम के प्रदर्शन की तुलना करता है।

Answer 8

यह संख्या और अनुक्रमित और फिर बस छँटाई अनुक्रमित को अलग करने, इस तरह के लायक हो सकता है:

#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; 

} 

यह प्रिंट:

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

विचार है कि है तत्वों अनुसार क्रमबद्ध किया जा रहा इस तरह के दौरान घूमने के लिए छोटे और इस प्रकार तेज़ होते हैं। आधुनिक CPUs पर, कैशिंग पर numbers पर अप्रत्यक्ष पहुंच के प्रभाव इन लाभों को खराब कर सकते हैं, इसलिए मैं इसका उपयोग करने का अंतिम निर्णय लेने से पहले डेटा की वास्तविक मात्रा पर बेंचमार्किंग की अनुशंसा करता हूं।