सी कोड स्मृति पहुँच/पूर्वक्रय

Question

मैं कोड का एक टुकड़ा जिसमें एक डेटा लिखा है। पूर्व: temp [4096]; अस्थायी [0] = बफ [0] + बफ [1] + बफ [2]; ... 4096

फिर एक हिस्टोग्राम कोड का उपयोग कर अस्थायी के परिणामों से उत्पन्न होता है जब तक:

for(i = 0; i < 4096; i++) 
counter[temp[i]]++; 

हिस्टोग्राम क्रमबद्ध किया जाता है (बुलबुला तरह) और फिर शीर्ष 8 सबसे आवर्ती मूल्यों लिया जाता है। कोड लिनक्स कर्नेल में चलाया जाता है (2.6.35)

समस्या का सामना करना पड़ रहा हूँ कि अगर मैं छँटाई हिस्से को हटाने, बार कोड निष्पादित करने के लिए ले जाया बहुत तेजी से (6 माइक्रोसेक अपने लैपटॉप का उपयोग कर मापा पर है gettimeofday func)। लेकिन सॉर्टिंग शुरू करने के बाद, प्रक्रिया काफी हद तक धीमी हो जाती है (44 माइक्रोसॉसी)। सॉर्टिंग फ़ंक्शन में 20 माइक्रोसॉक्स लगते हैं, मैं समझ नहीं पा रहा हूं कि समय इतना बढ़ रहा है। मैंने कैशग्रींड का उपयोग करके एक मेमोरी विश्लेषण किया, परिणाम सामान्य हैं और मैंने प्रीपेशन को अक्षम करने का भी प्रयास किया है लेकिन अभी भी यह कोई फर्क नहीं पड़ता है। अगर कोई यहां मेरी मदद कर सकता है। धन्यवाद!

Answer 1

बबल सॉर्ट धीमा है ... ओ (एन^2) जटिलता ... यदि आप तेज प्रदर्शन चाहते हैं, तो एक ढेर की तरह डेटा-संरचना का उपयोग करें, या अपने सरणी पर त्वरित-क्रमबद्ध एल्गोरिदम चलाएं, जिनमें से दोनों सॉर्टिंग प्रक्रिया के लिए आपको ओ (एन लॉग एन) जटिलता प्रदान करेगी। इसके अलावा, दोनों विधियां निश्चित-लंबाई वाले सरणी पर अच्छी तरह से काम करेंगे।

Answer 2

बबल प्रकार धीमा है, यह तुलना करता है और आपके मूल्यों को 4096 * 4096 = 16,777,216 बार तक बदल देता है। यदि आपको केवल 8 सर्वोत्तम मूल्यों की आवश्यकता है, तो 1 स्वीप चयन निश्चित रूप से तेज़ी से है। उस तरह कुछ।

const uint_t n = 8; 
uint_t best[n] = {0}; 
uint_t index[n] = {0}; 
uint_t j; 

for(uint_t i=0; i<4096; i++) { 

    if(counter[i] > best[n-1]) { 
    for(j=n-2; j && counter[i] > best[j]; j--);   /* Find the insertion position, as our value might be bigger than the value at position n-1. */ 
    memmove(&best [j+1], &best[j] , (n-1 -j) * sizeof best[0]);  /* Shift the values beyond j up 1 */ 
    memmove(&index[j+1], &index[j], (n-1 -j) * sizeof index[0]); 
    best[j] = counter[i];         /* Put the current best value at the top */ 
    index[j] = i;           /* Store the index in the second array to know where the best 
    } 

मूल्य था। */ } }

इसी के साथ

, आप केवल एक बार अपने मूल्यों की तुलना और memmove की लागत नगण्य है क्योंकि अपने चयन सरणी छोटा है। सरणी सॉर्ट करने के लिए कोई ज़रूरत नहीं, इस algo हे (एन) है, सबसे अच्छा प्रकार ओ (n.log2 एन)

संपादित होगा: मैं सूचकांक के लिए सरणी गयी। EDIT2: पहली बार मौलिक बग को सही करने के लिए दूसरा परिचय दिया गया। EDIT3: टिप्पणी: memmove आकार 0 के साथ अनुमति है और मूल रूप से एक एनओपी है।