एल्गोरिदम?

क्या कोई कुशल (तेज़) एल्गोरिदम है जो थोड़ा विस्तार/डुप्लिकेशन करेगा?एल्गोरिदम?

1101 0101 => 11111100 01110001 11000111

जानवर बल विधि है कि प्रस्तावित किया गया है एक लुकअप तालिका बनाने के लिए है:

उदाहरण के लिए, प्रत्येक 3 से एक 8 बिट मूल्य में बिट (एक 24bit मूल्य बनाने) का विस्तार करें। भविष्य में, विस्तार मूल्य को परिवर्तनीय होने की आवश्यकता हो सकती है। यही है, उपर्युक्त उदाहरण में हम 3 तक विस्तार कर रहे हैं लेकिन किसी अन्य मूल्य (ओं) द्वारा विस्तारित करने की आवश्यकता हो सकती है। इसके लिए कई लुकअप टेबल की आवश्यकता होगी जिन्हें मैं संभव से बचाना चाहूंगा।

स्रोत

2012-01-26 jivany

यदि आप केवल 8-बिट मानों से निपट रहे हैं, तो लुकअप तालिका लगभग निश्चित रूप से सबसे अच्छा विकल्प होने जा रही है। यह बहुत कम जगह का उपयोग करता है। क्या आप अपने उपयोग के मामले पर अधिक जानकारी दे सकते हैं और आप किस परिचालन को आम होने की उम्मीद करते हैं? – templatetypedef

इनपुट एक निरंतर सीरियल बिट स्ट्रीम है। वर्तमान आवश्यकता में, डेटा का प्रत्येक हिस्सा एक समय में 8 बाइट्स आता है, जिसके बाद प्रत्येक बिट को 3 बिट तक विस्तारित करने की आवश्यकता होती है ताकि एक और बिट स्ट्रीम के रूप में भेजा जा सके। 1 9 2 बिट्स में 64 बिट्स एक भविष्य की आवश्यकता में प्रत्येक विस्तारित 8 बिट मूल्य और निश्चित रूप से बाइट सीमा तक पैडिंग से पहले "हेडर" बिट्स जोड़ना शामिल हो सकता है। LUTs जल्दी हैं लेकिन यह कितनी बार चलाने की जरूरत है, किसी भी संभावित प्रदर्शन सुधार की सराहना की जाएगी। – jivany

कई आर्किटेक्चर में ऐसे निर्देश हैं जो इस तरह के गणना को बहुत तेज कर सकते हैं। यदि आप इन निर्देशों का लाभ उठाने वाले क्रॉस-प्लेटफार्म संगतता को तोड़ने से डरते नहीं हैं तो लगभग निश्चित रूप से एक जीत है - और यदि आप इस एल्गोरिदमिक रूप से "तुच्छ" को अनुकूलित कर रहे हैं तो निम्न स्तर के अनुकूलन को चालू करना महत्वपूर्ण है। – Kaganar

अगर गणितीय गणना मेमोरी एक्सेस से कुछ कारणों से तेज है तो लुकअप टेबल से इसे तेज करने का एक मौका है। यह संभव हो सकता है यदि गणना वेक्टरकृत (पीपीसी अल्टीवीक या इंटेल एसएसई) और/या प्रोग्राम के अन्य हिस्सों को कैश मेमोरी के हर बिट का उपयोग करने की आवश्यकता हो।

विस्तार कारक = 3, केवल 7 निर्देश की जरूरत है, तो:

out = (((in * 0x101 & 0x0F00F) * 0x11 & 0x0C30C3) * 5 & 0x249249) * 7;

या अन्य वैकल्पिक, के साथ 10 के निर्देश:

out = (in | in << 8) & 0x0F00F; 
out = (out | out << 4) & 0x0C30C3; 
out = (out | out << 2) & 0x249249; 
out *= 7;

अन्य विस्तार कारकों के लिए> = 3:

unsigned mask = 0x0FF; 
unsigned out = in; 
for (scale = 4; scale != 0; scale /= 2) 
{ 
    shift = scale * (N - 1); 
    mask &= ~(mask << scale); 
    mask |= mask << (scale * N); 
    out = out * ((1 << shift) + 1) & mask; 
} 
out *= (1 << N) - 1;

या अन्य कारक, विस्तार कारकों के लिए> = 2:

unsigned mask = 0x0FF; 
unsigned out = in; 
for (scale = 4; scale != 0; scale /= 2) 
{ 
    shift = scale * (N - 1); 
    mask &= ~(mask << scale); 
    mask |= mask << (scale * N); 
    out = (out | out << shift) & mask; 
} 
out *= (1 << N) - 1;

shift और mask मान बिट स्ट्रीम प्रोसेसिंग से पहले गणना की जाने वाली बेहतर हैं।

स्रोत

2012-01-28 08:54:21

शानदार प्रतिक्रिया।मेरे सहयोगी और मैं कुछ हैंडविंग और व्हाइटबोर्ड मंथन करने के दौरान इसके करीब आ गया लेकिन यह हमारे दृष्टिकोण से कहीं अधिक कुशल है। एक बार हमारे पास शेष कोड लागू होने के बाद मुझे कुछ परीक्षण चलाना होगा और देखें कि यह कैसे किराया करता है। – jivany

क्या किसी के पीछे गणित का कोई लिंक है? मैं चारों ओर खोज कर रहा हूं लेकिन यह कैसे काम करता है इस बारे में स्पष्टीकरण के बिना जादू खोजने में कामयाब रहा है। मुझे लगता है कि जादू संख्याओं के लिए कुछ पैटर्न है लेकिन बाकी सब कुछ मुझसे बच रहा है। –

एनवीएम, मैंने इसे समझ लिया। बाइनरी लिखने और फिर पैटर्न खोजने में मदद करता है। फिर भी, विषय पर किसी भी लिंक की सराहना की जाएगी। https://gist.github.com/corytodd/056ed01228f59fee9a13d00fc25b9a62 –

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

स्रोत

2012-01-26 21:37:47 comingstorm

उत्तर

संबंधित मुद्दे