std :: यूनरी मैपिंग द्वारा क्रमबद्ध

Question

सी ++ मानक लाइब्रेरी एक तुलनात्मक को std::sort पर पास करने की पेशकश करती है। हालांकि, मेरे पास मेरे कोड में कई मामले हैं जहां मैं f फ़ंक्शन द्वारा T ऑब्जेक्ट्स की सूची सॉर्ट करना चाहता हूं। इस तरह एक तुलनित्र एक वैध विकल्प होगा:

bool compare(const T& a, const T& b) { 
    return f(a) < f(b); 
} 

हालांकि यह इष्टतम नहीं है। f मूल्यांकन करने में धीमा है लेकिन उसी कॉल के लिए उसी मान को उसी T ऑब्जेक्ट के साथ वापस कर देगा। तो मैं क्या करना चाहूंगा f एक बार सीमा में प्रत्येक ऑब्जेक्ट के लिए गणना करें और फिर उन परिणामों को क्रमबद्ध करने के लिए उनका उपयोग करें।

template <typename IterT, typename Transformation> 
void sort(IterT left, IterT right, Transformation f) { /* ? */ } 

इस तरह की है कि इस कॉल के बाद, अनुक्रम left में सभी iter के लिए f(*iter) <= f(*std::next(iter))right रहे हैं:

मेरा लक्ष्य इस समारोह (जो मैं ऐसा करने में सक्षम नहीं किया गया) लिखने के लिए है।

इसके अलावा, समारोह इन आवश्यकताओं को पूरा करना चाहिए:

• प्रकार T के किसी भी अतिरिक्त वस्तुओं का आवंटन नहीं करता है।
• f का मूल्यांकन std::distance(left, right) कई बार मूल्यांकन करता है।
• ओ (एन लॉग एन) की समग्र जटिलता को बनाए रखता है।
• std :: sort के संदर्भ में लागू किया जाना चाहिए। निस्संदेह मैं अपने विलय प्रकार को लागू करके इस समस्या को हल कर सकता हूं लेकिन यह कुछ है जिसे मैं टालना चाहता हूं।

(सी ++ 11 पसंद किया जाता है, सी ++ 14 भी ठीक है)

Answer 1

तो आप जो चाहते हैं वह Schwartzian transform का सी ++ कार्यान्वयन है। मेरे पास कोड की कुछ पंक्तियों में एक साधारण समाधान नहीं है, लेकिन मैंने अपनी सी ++ 14 लाइब्रेरी में Schwartzian transform utility लागू किया है। दुर्भाग्य से यह प्रॉक्सी इटरेटर्स पर निर्भर करता है, जिन्हें std::sort (कम से कम रेंज टीएस तक नहीं) द्वारा नियंत्रित किया जाता है, लेकिन आप लाइब्रेरी से किसी भी अन्य सॉर्टर का उपयोग कर सकते हैं।जब इस तरह से कहा जाता

#include <cpp-sort/adapters/schwartz_adapter.h> 
#include <cpp-sort/sorters/default_sorter.h> 

template <typename IterT, typename Transformation> 
void sort(IterT left, IterT right, Transformation f) 
{ 
    using sorter = cppsort::schwartz_adapter<cppsort::default_sorter>; 
    sorter{}(left, right, f); 
} 

, सॉर्टर [left, right) पार और std::distance(left, right) जोड़े f(*it) के लिए एक इटरेटर it जोड़ पैदा करेगा: यहाँ कैसे आप sort समारोह अपने प्रश्न में उल्लेख किया है लिख सकता है। फिर यह उपरोक्त उदाहरण में पास सॉर्टर (default_sorter का उपयोग करेगा, जो कि लेखन के समय pattern-defeating quicksort है) जोड़े के संग्रह को सॉर्ट करने के लिए। Proxy iterators हुड के तहत उपयोग किया जाता है ताकि जब भी जोड़े बदल दिए जाते हैं तो मूल संग्रह के तत्व बदल दिए जाते हैं।

मैं नहीं कहूंगा कि यह काफी आसान है, लेकिन इसे आपकी समस्या का समाधान करना चाहिए। यदि आप बाहरी पुस्तकालय पर भरोसा नहीं करना चाहते हैं, तो भी आप the soure code से प्रेरणा ले सकते हैं। यह एक अनुमोदित लाइसेंस के तहत है, इसलिए यदि आप इससे तत्वों का उपयोग करने की आवश्यकता है तो आप जो भी चाहें उतना कर सकते हैं।

वैसे भी, यह ज्यादातर satifies अपनी आवश्यकताओं को यह दिखाई देता है:

• यह (जब तक fT का एक नया उदाहरण देता है के बाद से यह f के रिटर्न मान संग्रहीत करता है) T के अतिरिक्त उदाहरण आवंटित नहीं करता है।
• यह वास्तविक सॉर्टिंग से पहले f बिल्कुल std::distance(left, right) लागू होता है।
• यदि ओ (एन लॉग एन) सॉर्टर के साथ उपयोग किया जाता है तो यह ओ (एन लॉग एन) की समग्र जटिलता को बनाए रखता है।
• यह नवीनतम गोली केवल एक ही नहीं संतुष्ट किया जा रहा है: यह प्रयोग नहीं करता है std::sort क्योंकि std::sort आज के रूप में बहुत चालाक नहीं है, लेकिन यह आप अपने खुद के लिखने के बिना बराबर एल्गोरिदम का उपयोग कर सकते हैं।

Answer 2

आप std::sort से चिपक सिर्फ एक तुलनित्र कि T के हर उदाहरण के लिए अपने फंक्शन का मान कैश लिखना चाहते हैं।

उदाहरण:

struct Foo { 
    int value; 
}; 

// Replace with your CPU time intensive f() function 
int evaluate(const Foo& foo) { 
    std::cout << "Evaluating complex function on an instance of Foo..." << std::endl; 
    return foo.value; 
} 

bool compare(const Foo& left, const Foo& right) { 
    static std::unordered_map<Foo, int> cache; 
    auto leftIt = cache.find(left); 
    auto rightIt = cache.find(right); 
    if (leftIt == cache.end()) 
     leftIt = cache.emplace(left, evaluate(left)).first; 
    if (rightIt == cache.end()) 
     rightIt = cache.emplace(right, evaluate(right)).first; 
    return (*leftIt).second < (*rightIt).second; 
} 

आप यहाँ पूर्ण उदाहरण मिल सकते हैं: https://gist.github.com/PandarinDev/ee75b095c4cc256a88496f1985bf57ba

इस तरह evaluate(const Foo&); (आपके मामले में f(T)) केवल N बार भाग गया हो जाएगा, जहां N = the number of unique instances of Foo।

संपादित करें: टिप्पणी में नीचे उल्लेख किया है, यदि नक्शे में T उदाहरणों में से प्रति आपको कोई समस्या है, तो आप एक अद्वितीय पहचानकर्ता का उपयोग कर सकते हैं - जैसे कि आपका वस्तु के पते के रूप में - के बजाय एक कुंजी के रूप में ऑब्जेक्ट ही