गैर-शून्य न्यूनतम

Question

निर्धारित करने का सबसे तेज़ तरीका उदाहरण 4 पूर्णांक के लिए एक सरणी होने के बाद यह सबसे तेज़ तरीके से न्यूनतम शून्य निर्धारित कैसे कर सकता है?

Answer 1

इस समस्या का एक समानांतर समाधान है, लेकिन शायद यह प्रयास के लायक नहीं है।

पहले हम एक सरणी से अधिक एक ऑपरेशन xchg(m, n) परिभाषित एक:

xchg(m, n) => ((a[m] > a[n] && a[n] != 0) || a[m] == 0) ? swap(a[m],a[n]) 

इस आपरेशन आरोही क्रम में दो तत्वों 'm' सॉर्ट करता और 'एन' अगर वे दोनों ग़ैर शून्य मान, या स्वैप शामिल अगर 'एम' तत्व में मान शून्य है।

अगला हम इस तरह के पांच संचालन का एक सेट पर अमल इस प्रकार है:

xchg(0,2) xchg(1,3) 
xchg(0,1) xchg(2,3) 
xchg(1,2) 

बनती xchg संचालन, समानांतर में क्रियान्वित किया जा सकता एक सख्ती से अनुक्रमिक निष्पादन से अधिक 40% द्वारा समय लागत को कम करने। जब हम समाप्त कर लेंगे, तो सरणी में मौजूद गैर-शून्य तत्व आरोही क्रम में क्रमबद्ध किए जाएंगे। सबसे छोटा मूल्य तत्व [0] में होगा। यदि वह मान शून्य है, तो सरणी में कोई शून्य-शून्य मान नहीं हैं।

यह समाधान निहित छँटाई नेटवर्क (http://en.wikipedia.org/wiki/Sorting_network) द्वारा प्रदान की समानांतरवाद का लाभ लेता है, लेकिन 4 तत्वों की एक अनुक्रमिक स्कैन भी तीन से अधिक तुलना संचालन का उपयोग करता है, और महत्वपूर्ण बात के रूप में कई भंडारण आधा आवश्यकता औसतन लिखते हैं:

अनुक्रमिक स्कैन

int v = a[0] 
for (n = 1; n < 4; n++) { 
    if ((a[n] < v && a[n] != 0) || v == 0) v = a[n] 
} 

Answer 2

इनपुट पर निर्भर करता है। यदि सरणी क्रमबद्ध नहीं है, तो आपको पूर्ण सरणी के माध्यम से लूप करना होगा। यदि सरणी को सॉर्ट किया गया है, तो आपको केवल तब तक लूप की आवश्यकता है जब तक कि आपको कुछ ऐसा न हो जो शून्य नहीं है - यह बहुत छोटा है।

Answer 3

जब तक आप न्यूनतम मान रखते हैं, तत्वों के रूप में तत्वों को सरणी में जोड़ा जाता है, या आप सरणी क्रमबद्ध क्रम में रखते हैं - मुझे कोई अन्य समाधान नहीं दिखता है, लेकिन प्रत्येक सदस्य को न्यूनतम मान निर्धारित करने के लिए पुन: स्थापित करने के लिए।

प्रत्येक सदस्य का परीक्षण करने का कोई 'तेज़' तरीका नहीं है।

आम तौर पर मेरा सुझाव है कि जब तक यह वास्तव में धीमा साबित न हो जाए तब तक कुछ अनुकूलित न करें। आपके प्रोग्राम का पुराना नियम आमतौर पर सत्य के 10% कोड में 9 0% खर्च करता है। ऐसे में नियम हैं कि प्रोग्रामर 99.99% कोड को अनुकूलित करने की संभावना रखते हैं जो कि 10% में नहीं है।

प्रोफाइल अपने कोड - अपने कोड प्रोफ़ाइल - अपने कोड

Answer 4

खैर यह std::min({a,b,c,d}) है कोड करने के लिए सबसे तेज़ तरीका है प्रोफ़ाइल।

एक और गंभीर नोट पर: यदि आप कम से कम मूल्यों को लेने की तरह कुछ पर बाधा डाल रहे हैं, तो बेहतर समाधान हो सकता है कि उस न्यूनतम खोज कार्य को भागों में विभाजित करने और GPU को भेजने के लिए एक बेहतर समाधान हो सकता है (या कई धागे), जो एक ही समय में कई न्यूनतम खोज गणना संचालित कर सकते हैं।

समांतरता असेंबली में न्यूनतम कार्य लिखने की कोशिश करने से अधिक मददगार होगी।

Answer 5

हम सूक्ष्म अनुकूलन के बारे में सोच रहे हैं, तो संभवतः यह क्योंकि कम अनुक्रमिक निर्भरता का एक आधुनिक बाहर के आदेश प्रोसेसर पर min(min(a,b),min(c,d)) बजाय min(min(min(a,b),c),d) गणना करने के लिए, तेजी से हो सकता है: पूर्व में प्रोसेसर की गणना कर सकता min(a,b) और min(c,d) समानांतर में स्वतंत्र रूप से, यदि इसमें पर्याप्त निष्पादन इकाइयां उपलब्ध हैं। यह माना जा रहा है कि प्रोसेसर में एक सशर्त चाल निर्देश है, ताकि कंप्यूटिंग min को शाखाकरण की आवश्यकता नहीं है।