👖 💆🏽 😽 कैशे-सचेत बाइनरी खोज 🚺 😫 💧

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

अस्वीकरण: मैं इस समस्या का सबसे प्रभावी समाधान बनाने की कोशिश नहीं कर रहा हूँ। मैं प्रोसेसर कैश के साथ काम करने की सुविधाओं के आधार पर डेटा संरचनाओं के निर्माण के दृष्टिकोण पर चर्चा करना चाहूंगा कई, जब अनुकूलन समस्याओं को हल करते हैं, तो सिद्धांत रूप में प्रोसेसर वास्तुकला के बारे में नहीं सोचते हैं। मैं कैशे-कॉन्सियस बाइनरी सर्च के एक आदर्श कार्यान्वयन को लिखने वाला नहीं हूं, मैं इस दृष्टिकोण के प्रभाव को काफी सरल उदाहरण पर भी देखना चाहूंगा (कोड को सरल बनाने के लिए, वर्टिस की संख्या N-2 ^ K-1 के बराबर ली गई है)। मैं एक प्रोग्रामिंग भाषा के रूप में सी # का उपयोग करूंगा (समग्र प्रदर्शन हमारे लिए महत्वपूर्ण नहीं है, क्योंकि मुख्य जोर दुनिया में सबसे तेज कार्यक्रम बनाने पर नहीं है, लेकिन समस्या को हल करने के लिए अलग-अलग तरीकों की तुलनात्मक सापेक्षता पर है)। यह भी ध्यान देने योग्य है कि एल्गोरिथ्म केवल बड़े सरणियों पर प्रभावी है, इसलिए, इस दृष्टिकोण का उपयोग सभी कार्यों में नहीं किया जाना चाहिए, पहले आपको यह सुनिश्चित करने की आवश्यकता है कि यह व्यावहारिक है। यह माना जाता है कि पाठक को इस बात की बुनियादी समझ है कि प्रोसेसर कैश क्या है और यह कैसे काम करता है।

द्विआधारी खोज के शास्त्रीय कार्यान्वयन पर विचार करें: मान लें कि हमारे पास एक सॉर्ट किया गया सरणी a और कुछ तत्व x , जिसे हम इसमें देखेंगे:

 public bool Contains(int x) { int l = 0, r = N - 1; while (l <= r) { int m = (l + r) / 2; if (a[m] == x) return true; if (a[m] > x) r = m - 1; else l = m + 1; } return false; }

इस कार्यान्वयन में, एल्गोरिथ्म के पहले पुनरावृत्तियों पर, उन सरणी तत्वों के लिए अनुरोध किया जाएगा जो एक दूसरे से बहुत दूर हैं। आइए 15 तत्वों की एक सरणी के लिए खोज ट्री बनाएं:

यह आंकड़ा से देखा जा सकता है कि इस तरह के पेड़ से गुजरते समय, पहले 7 वें तत्व की अपील होगी, और फिर ( a[7]!=x के मामले में a[7]!=x ) से 3 या 11 वें तक। इतने छोटे सरणी पर, यह महत्वपूर्ण नहीं है, लेकिन एक बड़े सरणी में, ये एक्सेस प्रोसेसर कैश की विभिन्न लाइनों के अनुरूप होंगे, जो प्रदर्शन को नकारात्मक रूप से प्रभावित करेगा। आइए तत्वों को पुन: व्यवस्थित करने का प्रयास करें ताकि सरणी तक लगातार पहुंच स्मृति के निकट भागों पर हो। पहले सन्निकटन के रूप में, आप एक सरल चौड़ाई-पहली खोज के साथ एक के बाद एक वृक्ष के प्रत्येक स्तर को व्यवस्थित करने का प्रयास कर सकते हैं। हमारे परीक्षण वृक्ष पर हमें निम्नलिखित परिणाम मिलते हैं:

अब सरणी के तत्व, जिन्हें हम पहले पुनरावृत्तियों पर संबोधित करेंगे, एक दूसरे से दूर नहीं हैं। लेकिन पुनरावृति संख्या की वृद्धि के साथ, हम अभी भी बड़ी संख्या में कैश मिस-एस प्राप्त करते हैं। इस स्थिति को ठीक करने के लिए, हम अपने "बड़े" बाइनरी सर्च ट्री को छोटे उपप्रकारों में विभाजित करेंगे। ऐसा प्रत्येक उपप्रकार मूल पेड़ के कई स्तरों के अनुरूप होगा, और उप-तत्व तत्व एक-दूसरे के करीब स्थित होंगे। इस प्रकार, कैश मिस का गठन मुख्य रूप से अगले सबट्री के लिए संक्रमण के दौरान किया जाएगा। सबट्री की ऊंचाई भिन्न हो सकती है, इसे प्रोसेसर आर्किटेक्चर के अनुसार चुनें। हम अपने उदाहरण का उपयोग करके निर्माण डेटा का वर्णन करते हैं, 2 के बराबर सबट्री की ऊंचाई लेते हुए:

अब आइए व्यावहारिक अनुसंधान की ओर बढ़ें। प्रयोग की शुद्धता और सटीक परिणाम प्राप्त करने के लिए, हम बेंचमार्कडॉटनेट प्रोजेक्ट का उपयोग करके समय को मापेंगे। आइए बिना किसी अतिरिक्त अनुकूलन (स्रोत कोड GitHub पर प्रदान किए गए) के बिना विचार किए गए एल्गोरिदम के सबसे तुच्छ कार्यान्वयन पर विचार करें। हम अलग-अलग सबट्री हाइट्स के साथ क्लासिक कार्यान्वयन और कैश-सचेत कार्यान्वयन की तुलना करेंगे (CacheConsciousSearchK ऊंचाई K के साथ एक उपशीर्षक के अनुरूप है)। हम पेड़ की ऊँचाई को 24 तक ले जाते हैं। मेरी मशीन पर (Intel Core i7-3632QM CPU 2.20GHz), निम्नलिखित परिणाम प्राप्त किए गए थे (एल्गोरिथ्म प्रोसेसर आर्किटेक्चर के लिए बहुत संवेदनशील है, इसलिए आप पूरी तरह से अलग अस्थायी अनुमान प्राप्त कर सकते हैं):

 // Microsoft.NET 4.5 x64 SimpleSearch : 6725ms CacheConsciousSearch1 : 4428ms CacheConsciousSearch2 : 3963ms CacheConsciousSearch3 : 3778ms CacheConsciousSearch4 : 3774ms CacheConsciousSearch5 : 3762ms

बेंचमार्क स्रोत कोड

 public class CacheConsciousBinarySearchCompetition : BenchmarkCompetition { private const int K = 24, N = (1 << K) - 1, IterationCount = 10000000; private readonly Random random = new Random(); private Tree originalTree; private int[] bfs; protected override void Prepare() { originalTree = new Tree(Enumerable.Range(0, N).Select(x => 2 * x).ToArray()); bfs = originalTree.Bfs(); } [BenchmarkMethod] public void SimpleSearch() { SingleRun(originalTree); } [BenchmarkMethod] public void CacheConsciousSearch1() { SingleRun(new CacheConsciousTree(bfs, 1)); } [BenchmarkMethod] public void CacheConsciousSearch2() { SingleRun(new CacheConsciousTree(bfs, 2)); } [BenchmarkMethod] public void CacheConsciousSearch3() { SingleRun(new CacheConsciousTree(bfs, 3)); } [BenchmarkMethod] public void CacheConsciousSearch4() { SingleRun(new CacheConsciousTree(bfs, 4)); } [BenchmarkMethod] public void CacheConsciousSearch5() { SingleRun(new CacheConsciousTree(bfs, 5)); } private int SingleRun(ITree tree) { int searchedCount = 0; for (int iteration = 0; iteration < IterationCount; iteration++) { int x = random.Next(N * 2); if (tree.Contains(x)) searchedCount++; } return searchedCount; } interface ITree { bool Contains(int x); } class Tree : ITree { private readonly int[] a; public Tree(int[] a) { this.a = a; } public bool Contains(int x) { int l = 0, r = N - 1; while (l <= r) { int m = (l + r) / 2; if (a[m] == x) return true; if (a[m] > x) r = m - 1; else l = m + 1; } return false; } public int[] Bfs() { int[] bfs = new int[N], l = new int[N], r = new int[N]; int tail = 0, head = 0; l[head] = 0; r[head++] = N - 1; while (tail < head) { int m = (l[tail] + r[tail]) / 2; bfs[tail] = a[m]; if (l[tail] < m) { l[head] = l[tail]; r[head++] = m - 1; } if (m < r[tail]) { l[head] = m + 1; r[head++] = r[tail]; } tail++; } return bfs; } } class CacheConsciousTree : ITree { private readonly int[] a; private readonly int level; public CacheConsciousTree(int[] bfs, int level) { this.level = level; int size = (1 << level) - 1, counter = 0; a = new int[N]; var was = new bool[N]; var queue = new int[size]; for (int i = 0; i < N; i++) if (!was[i]) { int head = 0; queue[head++] = i; for (int tail = 0; tail < head; tail++) { a[counter++] = bfs[queue[tail]]; was[queue[tail]] = true; if (queue[tail] * 2 + 1 < N && head < size) queue[head++] = queue[tail] * 2 + 1; if (queue[tail] * 2 + 2 < N && head < size) queue[head++] = queue[tail] * 2 + 2; } } } public bool Contains(int x) { int u = 0, deep = 0, leafCount = 1 << (level - 1); int root = 0, rootOffset = 0; while (deep < K) { int value = a[root + u]; if (value == x) return true; if (++deep % level != 0) { if (value > x) u = 2 * u + 1; else u = 2 * u + 2; } else { int subTreeSize = (1 << Math.Min(level, K - deep)) - 1; if (value > x) rootOffset = rootOffset * leafCount * 2 + (u - leafCount + 1) * 2; else rootOffset = rootOffset * leafCount * 2 + (u - leafCount + 1) * 2 + 1; root = (1 << deep) - 1 + rootOffset * subTreeSize; u = 0; } } return false; } } }

बस मामले में, मैंने .NET फ्रेमवर्क के विभिन्न संस्करणों के तहत और विभिन्न बिट आकारों के साथ बेंचमार्क लॉन्च किया। सभी कॉन्फ़िगरेशन समान परिणाम देते हैं:

मोनो 3.3.0 के तहत, परिणाम भी समान हो गए:

आप इन चित्रों से देख सकते हैं कि क्लासिक बाइनरी खोज कार्यान्वयन कैश-कॉन्शियस कार्यान्वयन से काफी कम है। यह ध्यान देने योग्य है कि, शुरुआत में, उपशीर्षक की ऊंचाई में वृद्धि के साथ, गति बढ़ जाती है, लेकिन यह प्रवृत्ति लंबे समय तक नहीं रहती है (यदि उपशीर्षक के अंदर बड़ी संख्या में काहे की याद आती है तो उपप्रकार बहुत कम उपयोग करने लगते हैं)।

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

आप के लिए त्वरित क्षुधा!

आप इस विषय पर भी पढ़ सकते हैं:

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

कैशे-सचेत बाइनरी खोज

More articles: