एक साधारण विधि को कैसे गतिमान करें (अधिमानतः इंटरफेस या डेटा संरचनाओं को बदलने के बिना)?

Question

मैं कुछ डेटा संरचनाओं है:

• all_unordered_m एक बड़ी सभी स्ट्रिंग से युक्त वेक्टर है मैं की जरूरत है (सभी विभिन्न)
• ordered_m एक छोटे से तार का एक सबसेट (सभी विभिन्न) की अनुक्रमित युक्त वेक्टर है पूर्व वेक्टर
• position_m पहले वेक्टर से ऑब्जेक्ट्स की इंडेक्स को दूसरे स्थान पर मानचित्रित करता है।

string_after(index, reverse) विधि स्ट्रिंगall_unordered_m[index] के बाद ordered_m द्वारा संदर्भित देता है।

ordered_m परिपत्र माना जाता है, और दूसरे पैरामीटर के आधार पर प्राकृतिक या रिवर्स ऑर्डर में खोजा जाता है।

कोड निम्नलिखित की तरह कुछ है: यह देखते हुए

struct ordered_subset { 
    // [...] 

    std::vector<std::string>& all_unordered_m; // size = n >> 1 
    std::vector<size_t> ordered_m;    // size << n 
    std::tr1::unordered_map<size_t, size_t> position_m; 

    const std::string& 
    string_after(size_t index, bool reverse) const 
    { 
     size_t pos = position_m.find(index)->second; 
     if(reverse) 
      pos = (pos == 0 ? orderd_m.size() - 1 : pos - 1); 
     else 
      pos = (pos == ordered.size() - 1 ? 0 : pos + 1); 
     return all_unordered_m[ordered_m[pos]]; 
    } 
}; 

कि:

• मैं अन्य प्रयोजनों के लिए डेटा संरचनाओं के सभी की जरूरत है;
• क्योंकि मैं तार का उपयोग करने की जरूरत है मैं उन्हें बदल नहीं सकते: all_unordered_m में अपने आईडी द्वारा
  • ;
  • विभिन्न इंडेक्स_एम के अंदर उनके इंडेक्स द्वारा;
• मुझे आदेश_एम वेक्टर के अंदर एक स्ट्रिंग (पहले वेक्टर में इसकी स्थिति द्वारा पहचाना गया) की स्थिति जानने की आवश्यकता है;
• मैं अधिकांश प्रोग्राम को बदले बिना string_after इंटरफेस को नहीं बदल सकता।

मैं string_after विधि को कैसे बढ़ा सकता हूं जिसे अरबों बार कहा जाता है और निष्पादन समय के लगभग 10% को खा रहा है?

संपादित करें: मैं position_m एक unordered_map के बजाय एक vector बनाने और निम्न विधि का उपयोग छलांग से बचने के लिए कोशिश की है:

string_after(size_t index, int direction) const 
{ 
    return all_unordered_m[ordered_m[ 
     (ordered_m.size()+position_m[index]+direction)%ordered_m.size()]]; 
} 

position_m में परिवर्तन लगता है सबसे प्रभावी होने के लिए (मैं ' मुझे यकीन नहीं है कि शाखाओं को खत्म करने से कोई फर्क पड़ता है, मैं यह कहने के लिए प्रेरित हूं कि कोड अधिक कॉम्पैक्ट है लेकिन उस संबंध के साथ समान रूप से कुशल है)।

Answer 1

vector लुकअप तेजी से चमक रहे हैं। size() कॉल और सरल अंकगणित तेजी से चमक रहे हैं। map लुकअप, तुलनात्मक रूप से, उसकी पीठ पर कंक्रीट के एक ब्लॉक के साथ एक मृत कछुए के रूप में धीमी हैं। मैंने अक्सर देखा है कि इस तरह के अन्यथा सरल कोड में वे बाधा बन जाते हैं।

आप TR1 या C++ 0x (के ड्रॉप-इन हैशटेबल प्रतिस्थापन) के बजाय unordered_map को आजमा सकते हैं और देख सकते हैं कि इससे कोई फर्क पड़ता है या नहीं।

Answer 2

ठीक है, ऐसे मामलों में (प्रत्येक छोटे कार्य जिसे अक्सर कहा जाता है) प्रत्येक शाखा बहुत महंगा हो सकती है। दो चीजें हैं जो दिमाग में आती हैं।

1. क्या आप reverse पैरामीटर छोड़ सकते हैं और इसे दो अलग-अलग तरीकों से बना सकते हैं? यह केवल तभी समझ में आता है जब यह कॉलिंग कोड पर if -स्टेटमेंट को धक्का नहीं देता है।
2. pos की गणना के लिए निम्न का प्रयास करें: pos = (pos + 1) % ordered_m.size() (यह आगे के मामले के लिए है)। यह केवल तभी काम करता है यदि आप सुनिश्चित हैं कि pos इसे बढ़ाने पर कभी बहती नहीं है।

सामान्य रूप से, ऐसे मामलों में अंकगणितीय परिचालनों वाली शाखाओं को प्रतिस्थापित करने का प्रयास करें, इससे आपको पर्याप्त गति मिल सकती है।