c++ - यकत - स्कूलों समावेशी बनाने के लिए रणनीति




यह निर्धारित करने का सबसे तेज़ तरीका है कि एक पूर्णांक मूल्यों के ज्ञात सेट के साथ दो पूर्णांक(समावेशी) के बीच है (4)

क्या एक पूर्णांक दो पूर्णांक के बीच है या नहीं, यह जांचने के लिए x >= start && x <= end सी या सी ++ में x >= start && x <= end से तेज तरीका है?

अद्यतन : मेरा विशिष्ट मंच आईओएस है। यह एक बॉक्स ब्लर फ़ंक्शन का हिस्सा है जो किसी दिए गए वर्ग में पिक्सेल को किसी मंडली में प्रतिबंधित करता है।

अद्यतन : स्वीकार्य उत्तर की कोशिश करने के बाद, मुझे सामान्य x >= start && x <= end way करने पर कोड की एक पंक्ति पर परिमाण गतिशीलता का क्रम मिला।

अद्यतन : एक्सकोड से असेंबलर के साथ कोड के बाद और पहले कोड यहां दिया गया है:

नया रास्ता

// diff = (end - start) + 1
#define POINT_IN_RANGE_AND_INCREMENT(p, range) ((p++ - range.start) < range.diff)

Ltmp1313:
 ldr    r0, [sp, #176] @ 4-byte Reload
 ldr    r1, [sp, #164] @ 4-byte Reload
 ldr    r0, [r0]
 ldr    r1, [r1]
 sub.w  r0, r9, r0
 cmp    r0, r1
 blo    LBB44_30

पुराना तरीका

#define POINT_IN_RANGE_AND_INCREMENT(p, range) (p <= range.end && p++ >= range.start)

Ltmp1301:
 ldr    r1, [sp, #172] @ 4-byte Reload
 ldr    r1, [r1]
 cmp    r0, r1
 bls    LBB44_32
 mov    r6, r0
 b      LBB44_33
LBB44_32:
 ldr    r1, [sp, #188] @ 4-byte Reload
 adds   r6, r0, #1
Ltmp1302:
 ldr    r1, [r1]
 cmp    r0, r1
 bhs    LBB44_36

बहुत आश्चर्यजनक है कि शाखाओं को कम करने या समाप्त करने से ऐसी नाटकीय गति मिल सकती है।


ऐसे छोटे पैमाने पर कोड के लिए महत्वपूर्ण अनुकूलन करने में सक्षम होना दुर्लभ है। बड़े प्रदर्शन लाभ उच्च स्तर से कोड को देखने और संशोधित करने से आते हैं। आप पूरी तरह से श्रेणी परीक्षण की आवश्यकता को खत्म करने में सक्षम हो सकते हैं, या ओ (एन ^ 2) के बजाय उनमें से केवल ओ (एन) कर सकते हैं। आप परीक्षणों को फिर से व्यवस्थित करने में सक्षम हो सकते हैं ताकि असमानता का एक पक्ष हमेशा निहित हो। यहां तक ​​कि यदि एल्गोरिदम आदर्श है, तो लाभ देखने की संभावना अधिक होती है जब आप देखते हैं कि यह कोड 10 मिलियन बार रेंज परीक्षण कैसे करता है और आपको उन्हें बैच करने और समानांतर में कई परीक्षण करने के लिए एसएसई का उपयोग करने का तरीका मिलता है।


केवल एक तुलना / शाखा के साथ ऐसा करने के लिए एक पुरानी चाल है। चाहे यह वास्तव में गति में सुधार करे, प्रश्न के लिए खुला हो सकता है, और यहां तक ​​कि अगर ऐसा होता है, तो शायद यह ध्यान देने या देखभाल करने के लिए बहुत कम है, लेकिन जब आप केवल दो तुलनाओं से शुरू कर रहे हैं, तो बड़े सुधार की संभावना बहुत दूर है। कोड इस तरह दिखता है:

// use a < for an inclusive lower bound and exclusive upper bound
// use <= for an inclusive lower bound and inclusive upper bound
// alternatively, if the upper bound is inclusive and you can pre-calculate
//  upper-lower, simply add + 1 to upper-lower and use the < operator.
    if ((unsigned)(number-lower) <= (upper-lower))
        in_range(number);

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

ध्यान दें कि एक सामान्य मामले में, आप एक (अनुमानित) लूप के बाहर upper-lower को पूर्व-गणना कर सकते हैं, ताकि सामान्य रूप से कोई महत्वपूर्ण समय न हो। शाखा निर्देशों की संख्या को कम करने के साथ-साथ यह (आमतौर पर) शाखा भविष्यवाणी में सुधार करता है। इस मामले में, एक ही शाखा ली जाती है कि संख्या नीचे के अंत से नीचे या सीमा के शीर्ष छोर से ऊपर है या नहीं।

यह कैसे काम करता है, मूल विचार बहुत सरल है: एक ऋणात्मक संख्या, जब एक हस्ताक्षरित संख्या के रूप में देखा जाता है, वह सकारात्मक संख्या के रूप में शुरू होने वाली किसी भी चीज़ से बड़ा होगा।

अभ्यास में यह विधि उत्पत्ति के बिंदु पर number और अंतराल का अनुवाद करती है और जांच करती है कि number अंतराल [0, D] , जहां D = upper - lower । यदि नीचे की number नीचे की सीमा है: नकारात्मक , और यदि ऊपरी सीमा से ऊपर है: D से बड़ा


यह इस बात पर निर्भर करता है कि आप एक ही डेटा पर कितनी बार परीक्षण करना चाहते हैं।

यदि आप एक बार परीक्षण कर रहे हैं, तो शायद एल्गोरिदम को गति देने का एक सार्थक तरीका नहीं है।

यदि आप इसे मूल्यों के बहुत सीमित सेट के लिए कर रहे हैं, तो आप एक लुकअप टेबल बना सकते हैं। इंडेक्सिंग करना अधिक महंगा हो सकता है, लेकिन यदि आप पूरे टेबल को कैश में फिट कर सकते हैं, तो आप कोड से सभी शाखाओं को हटा सकते हैं, जो चीजों को गति देना चाहिए।

आपके डेटा के लिए लुकअप टेबल 128 ^ 3 = 2,097,152 होगा। यदि आप तीन चरों में से एक को नियंत्रित कर सकते हैं तो आप उन सभी उदाहरणों पर विचार करें जहां एक समय में start = N , फिर कार्य सेट का आकार 128^2 = 16432 बाइट्स तक गिर जाता है, जो कि अधिकांश आधुनिक कैश में अच्छी तरह से फिट होना चाहिए।

आपको अभी भी वास्तविक कोड को बेंचमार्क करना होगा ताकि यह देखने के लिए कि कोई शाखा रहित लुकअप टेबल स्पष्ट तुलना से पर्याप्त तेज़ है या नहीं।


यह उत्तर स्वीकृत उत्तर के साथ किए गए परीक्षण पर रिपोर्ट करना है। मैंने सॉर्ट किए गए यादृच्छिक पूर्णांक के बड़े वेक्टर पर एक बंद रेंज परीक्षण किया और मेरे आश्चर्य की बात है कि (निम्न <= num && num <= high) मूलभूत विधि वास्तव में ऊपर दिए गए स्वीकृत उत्तर से तेज़ है! परीक्षण एचपी मंडप जी 6 (एएमडी ए 6-3400APU पर 6 जीबी रैम के साथ किया गया था। यहां परीक्षण के लिए इस्तेमाल किया गया कोर कोड है:

int num = rand();  // num to compare in consecutive ranges.
chrono::time_point<chrono::system_clock> start, end;
auto start = chrono::system_clock::now();

int inBetween1{ 0 };
for (int i = 1; i < MaxNum; ++i)
{
    if (randVec[i - 1] <= num && num <= randVec[i])
        ++inBetween1;
}
auto end = chrono::system_clock::now();
chrono::duration<double> elapsed_s1 = end - start;

निम्नलिखित के मुकाबले ऊपर स्वीकृत उत्तर है:

int inBetween2{ 0 };
for (int i = 1; i < MaxNum; ++i)
{
    if (static_cast<unsigned>(num - randVec[i - 1]) <= (randVec[i] - randVec[i - 1]))
        ++inBetween2;
}

ध्यान दें कि रैंडवैक एक क्रमबद्ध वेक्टर है। मैक्सनम के किसी भी आकार के लिए पहली विधि मेरी मशीन पर दूसरी बार धड़कता है!






math