c - जल्दी से पता लगाएं कि एक सी सरणी में कोई मान मौजूद है या नहीं?




optimization assembly (10)

मेरे पास एक समय-महत्वपूर्ण आईएसआर के साथ एक एम्बेडेड एप्लिकेशन है जिसे आकार 256 (अधिमानतः 1024, लेकिन 256 न्यूनतम है) के माध्यम से पुनरावृत्त करने की आवश्यकता है और जांचें कि कोई मान सरणी सामग्री से मेल खाता है या नहीं। एक bool सत्य पर सेट किया जाएगा यह मामला है। एमसीयू एक एनएक्सपी एलपीसी 4357 है, एआरएम कॉर्टेक्स एम 4 कोर, कंपाइलर जीसीसी है। मेरे पास पहले से ही अनुकूलन स्तर 2 (3 धीमा है) और फ्लैश के बजाय फ़ंक्शन में रैम रख रहा है। मैं पॉइंटर अंकगणित और लूप के for भी उपयोग करता हूं, जो ऊपर की ओर गिनती करता है (जांच कर रहा है कि i!=0 जांच कर रहा i<256 कि i<256 ) जांच कर रहा i<256 । सब कुछ, मैं 12.5us की अवधि के साथ समाप्त होता हूं जिसे व्यवहार्य रूप से व्यवहार्य रूप से कम किया जाना चाहिए। यह अब (छद्म) कोड है जिसका उपयोग मैं करता हूं:

uint32_t i;
uint32_t *array_ptr = &theArray[0];
uint32_t compareVal = 0x1234ABCD;
bool validFlag = false;

for (i=256; i!=0; i--)
{
    if (compareVal == *array_ptr++)
    {
         validFlag = true;
         break;
     }
}

ऐसा करने का सबसे तेज़ तरीका क्या होगा? इनलाइन असेंबली का उपयोग करने की अनुमति है। अन्य 'कम सुरुचिपूर्ण' चाल भी अनुमति दी।


अन्य लोगों ने आपके टेबल को पुनर्गठित करने का सुझाव दिया है, अंत में एक सेंटीनेल वैल्यू जोड़ना है, या बाइनरी सर्च प्रदान करने के लिए इसे सॉर्ट करना है।

आप कहते हैं "मैं पॉइंटर अंकगणित और लूप के लिए भी उपयोग करता हूं, जो ऊपर की गिनती करता है (जांच कर रहा है कि i != 0 जांच कर रहा i < 256 कि i < 256 ) जांच कर रहा i < 256 ।"

मेरी पहली सलाह है: पॉइंटर अंकगणित और डाउनकाउंटिंग से छुटकारा पाएं। सामान की तरह

for (i=0; i<256; i++)
{
    if (compareVal == the_array[i])
    {
       [...]
    }
}

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

उदाहरण के लिए, उपरोक्त कोड को -256 या -255 से शून्य तक चलने वाले लूप में संकलित किया जा सकता है, इंडेक्सिंग ऑफ &the_array[256] । संभावित रूप से सामान जो वैध सी में भी स्पष्ट नहीं है लेकिन आपके द्वारा उत्पन्न की जा रही मशीन के आर्किटेक्चर से मेल खाता है।

तो microoptimize मत करो । आप सिर्फ अपने अनुकूलक के कार्यों में स्पैनर्स फेंक रहे हैं। यदि आप चालाक होना चाहते हैं, तो डेटा संरचनाओं और एल्गोरिदम पर काम करें, लेकिन उनकी अभिव्यक्ति को सूक्ष्म रूप से लागू न करें। वर्तमान कंपाइलर / आर्किटेक्चर पर नहीं, तो अगले समय पर यह आपको काटने के लिए वापस आ जाएगा।

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


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

बिल्कुल सही हैश समारोह

यदि आपके 256 "मान्य" मान स्थैतिक हैं और संकलन समय पर ज्ञात हैं, तो आप एक परिपूर्ण हैश फ़ंक्शन का उपयोग कर सकते हैं। आपको एक हैश फ़ंक्शन ढूंढना होगा जो आपके इनपुट मान को श्रेणी 0 .. n में किसी मान पर मैप करता है, जहां आपके सभी महत्वपूर्ण मानों के लिए कोई टकराव नहीं है। यही है, एक ही आउटपुट मान के लिए कोई भी "वैध" मान हैश नहीं है। एक अच्छा हैश फ़ंक्शन खोजते समय, आपका लक्ष्य है:

  • हैश फ़ंक्शन को तेज़ी से तेज़ रखें।
  • न्यूनतम करें। सबसे छोटा आप 256 (न्यूनतम परिपूर्ण हैश फ़ंक्शन) प्राप्त कर सकते हैं, लेकिन डेटा के आधार पर यह संभवतः हासिल करना मुश्किल है।

कुशल हैश फ़ंक्शन के लिए नोट, n अक्सर 2 की शक्ति होती है, जो कम बिट्स (और ऑपरेशन) के बिटवाई मास्क के बराबर होती है। उदाहरण हैश फ़ंक्शन:

  • इनपुट बाइट्स के सीआरसी, मॉड्यूल एन
  • ((x << i) ^ (x >> j) ^ (x << k) ^ ...) % n (जितना आवश्यक हो, i , j , k , ... को बाएं या दाएं बदलाव के साथ)

फिर आप एन प्रविष्टियों की एक निश्चित तालिका बनाते हैं, जहां हैश तालिका में इंडेक्स में इनपुट मानों को मैप करता है। मान्य मानों के लिए, तालिका प्रविष्टि में वैध मान होता है। अन्य सभी टेबल प्रविष्टियों के लिए, सुनिश्चित करें कि इंडेक्स की प्रत्येक प्रविष्टि में मेरे पास कुछ अन्य अमान्य मान है जो i के लिए हैश नहीं है।

फिर आपके इंटरप्ट रूटीन में, इनपुट एक्स के साथ:

  1. इंडेक्स I के लिए हैश एक्स (जो 0 0 एन में है)
  2. तालिका में प्रविष्टि को देखो और देखें कि इसमें मान x है या नहीं

यह 256 या 1024 मानों की रैखिक खोज से कहीं अधिक तेज़ होगा।

मैंने उचित हैश फ़ंक्शंस खोजने के लिए कुछ पायथन कोड लिखा है।

द्विआधारी खोज

यदि आप 256 "वैध" मानों की अपनी सरणी को सॉर्ट करते हैं, तो आप एक रैखिक खोज के बजाय बाइनरी खोज कर सकते हैं। इसका मतलब है कि आप केवल 8 चरणों ( log2(256) ) में log2(256) -प्रविष्टि तालिका, या 10 चरणों में 1024-प्रविष्टि तालिका में खोज करने में सक्षम होना चाहिए। फिर, यह 256 या 1024 मानों की रैखिक खोज से कहीं अधिक तेज़ होगा।


इसे अनुकूलित करने के लिए एक चाल है (मुझे इसे नौकरी साक्षात्कार पर एक बार पूछा गया था):

  • यदि सरणी में अंतिम प्रविष्टि उस मान को रखती है जिसे आप ढूंढ रहे हैं, तो सत्य लौटें
  • वह मान लिखें जिसे आप सरणी में अंतिम प्रविष्टि में ढूंढ रहे हैं
  • सरणी को तब तक घुमाएं जब तक आप उस मूल्य का सामना न करें जिसे आप ढूंढ रहे हैं
  • यदि आपको सरणी में अंतिम प्रविष्टि से पहले इसका सामना करना पड़ा है, तो सत्य वापस आएं
  • विवरण झूठा है
bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t i;
    uint32_t x = theArray[SIZE-1];
    if (x == compareVal)
        return true;
    theArray[SIZE-1] = compareVal;
    for (i = 0; theArray[i] != compareVal; i++);
    theArray[SIZE-1] = x;
    return i != SIZE-1;
}

यह प्रति पुनरावृत्ति के दो शाखाओं के बजाय प्रति पुनरावृत्ति एक शाखा पैदा करता है।

अद्यतन करें:

यदि आपको सरणी को SIZE+1 आवंटित करने की अनुमति है, तो आप "अंतिम प्रविष्टि स्वैपिंग" भाग से छुटकारा पा सकते हैं:

bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t i;
    theArray[SIZE] = compareVal;
    for (i = 0; theArray[i] != compareVal; i++);
    return i != SIZE;
}

आप इसके बजाय निम्न का उपयोग करके, theArray[i] में एम्बेडेड अतिरिक्त अंकगणित से छुटकारा पा सकते हैं:

bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t *arrayPtr;
    theArray[SIZE] = compareVal;
    for (arrayPtr = theArray; *arrayPtr != compareVal; arrayPtr++);
    return arrayPtr != theArray+SIZE;
}

यदि संकलक पहले से ही इसे लागू नहीं करता है, तो यह फ़ंक्शन निश्चित रूप से ऐसा करेगा। दूसरी तरफ, यह लूप को अनलॉक करने के लिए अनुकूलक पर कठिन बना सकता है, इसलिए आपको जेनरेट किए गए असेंबली कोड में यह सत्यापित करना होगा ...


एक हैश सेट का प्रयोग करें। यह ओ (1) लुकअप समय देगा।

निम्नलिखित कोड मानते हैं कि आप मान 0 को 'खाली' मान के रूप में आरक्षित कर सकते हैं, यानी वास्तविक डेटा में नहीं हो रहा है। समाधान को ऐसी स्थिति के लिए विस्तारित किया जा सकता है जहां यह मामला नहीं है।

#define HASH(x) (((x >> 16) ^ x) & 1023)
#define HASH_LEN 1024
uint32_t my_hash[HASH_LEN];

int lookup(uint32_t value)
{
    int i = HASH(value);
    while (my_hash[i] != 0 && my_hash[i] != value) i = (i + 1) % HASH_LEN;
    return i;
}

void store(uint32_t value)
{
    int i = lookup(value);
    if (my_hash[i] == 0)
       my_hash[i] = value;
}

bool contains(uint32_t value)
{
    return (my_hash[lookup(value)] == value);
}

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


तालिका क्रमबद्ध क्रम में रखें, और बेंटले की अनियंत्रित बाइनरी खोज का उपयोग करें:

i = 0;
if (key >= a[i+512]) i += 512;
if (key >= a[i+256]) i += 256;
if (key >= a[i+128]) i += 128;
if (key >= a[i+ 64]) i +=  64;
if (key >= a[i+ 32]) i +=  32;
if (key >= a[i+ 16]) i +=  16;
if (key >= a[i+  8]) i +=   8;
if (key >= a[i+  4]) i +=   4;
if (key >= a[i+  2]) i +=   2;
if (key >= a[i+  1]) i +=   1;
return (key == a[i]);

मुद्दा ये है,

  • यदि आप जानते हैं कि तालिका कितनी बड़ी है, तो आप जानते हैं कि कितने पुनरावृत्तियों होंगे, ताकि आप इसे पूरी तरह से अनलॉक कर सकें।
  • फिर, प्रत्येक पुनरावृत्ति पर == मामले के लिए कोई बिंदु परीक्षण नहीं है क्योंकि, अंतिम पुनरावृत्ति को छोड़कर, उस मामले की संभावना इसके लिए व्यय समय परीक्षण को उचित ठहराने के लिए बहुत कम है। **
  • अंत में, तालिका को 2 की शक्ति में विस्तार करके, आप सबसे अधिक तुलना में जोड़ते हैं, और अधिकतर दो स्टोरेज का एक कारक जोड़ते हैं।

** यदि आप संभावनाओं के संदर्भ में सोचने के लिए उपयोग नहीं किए जाते हैं, तो प्रत्येक निर्णय बिंदु में एक एन्ट्रॉपी होती है , जो कि इसे निष्पादित करके सीखने वाली औसत जानकारी होती है। >= परीक्षणों के लिए, प्रत्येक शाखा की संभावना लगभग 0.5 है, और -log2 (0.5) 1 है, इसका मतलब है कि यदि आप एक शाखा लेते हैं तो आप 1 बिट सीखते हैं, और यदि आप दूसरी शाखा लेते हैं तो आप एक बिट सीखते हैं, और औसतन उस शाखा की संभावना प्रत्येक शाखा समय पर आप जो भी सीखते हैं उसका योग है। तो 1*0.5 + 1*0.5 = 1 , इसलिए >= test की एन्ट्रॉपी 1*0.5 + 1*0.5 = 1 है। चूंकि आपके पास सीखने के लिए 10 बिट हैं, इसमें 10 शाखाएं होती हैं। यही कारण है कि यह तेज़ है!

दूसरी ओर, यदि आपका पहला परीक्षण है if (key == a[i+512) ? सत्य होने की संभावना 1/1024 है, जबकि झूठी संभावना 1023/1024 है। तो यदि यह सच है तो आप सभी 10 बिट्स सीखते हैं! लेकिन अगर यह गलत है तो आप सीखेंगे -log2 (1023/1024) = .00141 बिट्स, व्यावहारिक रूप से कुछ भी नहीं! इसलिए उस परीक्षा से आप जो औसत राशि सीखते हैं वह 10/1024 + .00141*1023/1024 = .0098 + .00141 = .0112 बिट्स है। थोड़ा सा सौवां। वह परीक्षण अपना वजन नहीं ले रहा है!


मान लें कि आपका प्रोसेसर 204 मेगाहट्र्ज पर चलता है जो एलपीसी 4357 के लिए अधिकतम लगता है, और यह भी मानते हुए कि आपका समय परिणाम औसत केस (सरणी के आधे भाग का आधा) दर्शाता है, हमें मिलता है:

  • सीपीयू आवृत्ति: 204 मेगाहट्र्ज
  • चक्र अवधि: 4.9 एनएस
  • चक्र में अवधि: 12.5 μs / 4.9 एनएस = 2551 चक्र
  • चक्र प्रति पुनरावृत्ति: 2551/128 = 1 9.9

तो, आपका खोज लूप प्रति पुनरावृत्ति के लगभग 20 चक्र खर्च करता है। यह भयानक नहीं लगता है, लेकिन मुझे लगता है कि इसे तेज़ी से बनाने के लिए आपको असेंबली को देखने की जरूरत है।

मैं इंडेक्स को छोड़ने और इसके बजाय पॉइंटर तुलना का उपयोग करने और सभी पॉइंटर्स const बनाने की सलाह const

bool arrayContains(const uint32_t *array, size_t length)
{
  const uint32_t * const end = array + length;
  while(array != end)
  {
    if(*array++ == 0x1234ABCD)
      return true;
  }
  return false;
}

यह कम से कम परीक्षण के लायक है।


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

bool theArray[MAX_VALUE]; // of which 1024 values are true, the rest false
uint32_t compareVal = 0x1234ABCD;
bool validFlag = theArray[compareVal];

संपादित करें

मैं आलोचकों की संख्या से आश्चर्यचकित हूं। इस धागे का शीर्षक है "मैं कैसे जल्दी से यह पता लगा सकता हूं कि एक सी सरणी में कोई मान मौजूद है या नहीं?" जिसके लिए मैं अपने जवाब से खड़ा रहूंगा क्योंकि यह ठीक से जवाब देता है। मैं तर्क दे सकता हूं कि इसमें सबसे तेज़ कुशल हैश फ़ंक्शन है (पता === मान के बाद)। मैंने टिप्पणियां पढ़ी हैं और मुझे स्पष्ट चेतावनी के बारे में पता है। निस्संदेह उन चेतावनियों को हल करने के लिए उपयोग की जा सकने वाली समस्याओं की सीमा को सीमित कर सकते हैं, लेकिन, उन समस्याओं के लिए जो यह हल करता है, यह बहुत कुशलतापूर्वक हल करता है।

इस जवाब को पूरी तरह से अस्वीकार करने के बजाय, इसे इष्टतम प्रारंभिक बिंदु के रूप में मानें जिसके लिए आप गति और प्रदर्शन के बीच बेहतर संतुलन प्राप्त करने के लिए हैश फ़ंक्शंस का उपयोग कर विकसित कर सकते हैं।


यदि आपकी तालिका में स्थिरांक का सेट अग्रिम में जाना जाता है, तो आप यह सुनिश्चित करने के लिए सही हैशिंग का उपयोग कर सकते हैं कि तालिका में केवल एक ही पहुंच हो। परफेक्ट हैशिंग एक हैश फ़ंक्शन निर्धारित करता है जो एक अद्वितीय स्लॉट के लिए हर रोचक कुंजी को मैप करता है (वह तालिका हमेशा घनी नहीं होती है, लेकिन आप यह तय कर सकते हैं कि आप कितनी गहन टेबल ले सकते हैं, कम घने तालिकाओं के साथ आमतौर पर सरल हैशिंग फ़ंक्शन का कारण बनता है)।

आमतौर पर, कुंजी के विशिष्ट सेट के लिए सही हैश फ़ंक्शन गणना करने के लिए अपेक्षाकृत आसान है; आप नहीं चाहते कि यह लंबा और जटिल हो क्योंकि वह समय के लिए प्रतिस्पर्धा करता है शायद कई जांच करने में बेहतर खर्च करता है।

परफेक्ट हैशिंग एक "1-जांच अधिकतम" योजना है। कोई इस विचार के साथ विचार को सामान्यीकृत कर सकता है कि किसी को हैश कोड की गणना करने की सादगी का व्यापार करना चाहिए, जिसमें के जांच करने के लिए समय लगता है। आखिरकार, लक्ष्य "देखने के लिए कम से कम कुल समय" है, कम से कम जांच या सरल हैश फ़ंक्शन नहीं है। हालांकि, मैंने कभी भी किसी के-प्रोब-मैक्स हैशिंग एल्गोरिदम का निर्माण नहीं देखा है। मुझे संदेह है कि कोई ऐसा कर सकता है, लेकिन यह संभवतः शोध है।

एक अन्य विचार: यदि आपका प्रोसेसर बेहद तेज़ है, तो एक परिपूर्ण हैश से स्मृति की जांच संभवतः निष्पादन समय पर हावी है। यदि प्रोसेसर बहुत तेज़ नहीं है, तो के> 1 जांच से व्यावहारिक हो सकता है।


I'm a great fan of hashing. The problem of course is to find an efficient algorithm that is both fast and uses a minimum amount of memory (especially on an embedded processor).

If you know beforehand the values that may occur you can create a program that runs through a multitude of algorithms to find the best one - or, rather, the best parameters for your data.

I created such a program that you can read about in this post and achieved some very fast results. 16000 entries translates roughly to 2^14 or an average of 14 comparisons to find the value using a binary search. I explicitly aimed for very fast lookups - on average finding the value in <=1.5 lookups - which resulted in greater RAM requirements. I believe that with a more conservative average value (say <=3) a lot of memory could be saved. By comparison the average case for a binary search on your 256 or 1024 entries would result in an average number of comparisons of 8 and 10, respectively.

My average lookup required around 60 cycles (on a laptop with an intel i5) with a generic algorithm (utilizing one division by a variable) and 40-45 cycles with a specialized (probably utilizing a multiplication). This should translate into sub-microsecond lookup times on your MCU, depending of course on the clock frequency it executes at.

It can be real-life-tweaked further if the entry array keeps track of how many times an entry was accessed. If the entry array is sorted from most to least accessed before the indeces are computed then it'll find the most commonly occuring values with a single comparison.


This is more like an addendum than an answer.

I've had a simillar case in the past, but my array was constant over a considerable number of searches.

In half of them, the searched value was NOT present in array. Then I realized I could apply a "filter" before doing any search.

This "filter" is just a simple integer number, calculated ONCE and used in each search.

It's in java, but it's pretty simple:

binaryfilter = 0;
for (int i = 0; i < array.length; i++)
{
    // just apply "Binary OR Operator" over values.
    binaryfilter = binaryfilter | array[i]; 
}

So, before do a binary search, I check binaryfilter:

// check binaryfilter vs value with a "Binary AND Operator"
if ( (binaryfilter & valuetosearch) != valuetosearch) 
{
    // valuetosearch is not in the array!
    return false;
}
else
{
    // valuetosearch MAYBE in the array, so let's check it out
    // ... do binary search stuff ...

}

You can use a 'better' hash algorithm, but this can be very fast, specially for large numbers. May be this could save you even more cycles.






arm