संगत सेट/स्पष्ट बिट्स के लिए बिट-सरणी खोजने के लिए तेज़ कोड?

Question

क्या वहां कुछ उचित तेज़ कोड है जो मुझे तुरंत शून्य या एक बिट्स के रनों के लिए एक बड़े बिटमैप (कुछ मेगाबाइट्स) की खोज करने में मदद कर सकता है?

"उचित रूप से तेज़" से मेरा मतलब कुछ ऐसा है जो मशीन शब्द आकार का लाभ उठा सकता है और एक बार में पूरे शब्दों की तुलना कर सकता है, बिट-बाय-बिट विश्लेषण करने की बजाय जो क्षैतिज रूप से धीमा है (जैसे कोई vector<bool> के साथ करता है)।

यह उदाहरण के लिए बहुत उपयोगी है मुक्त स्थान के लिए वॉल्यूम के बिटमैप को खोजना (डीफ्रैग्मेंटेशन आदि के लिए)।

Answer 1

विंडोज़ में RTL_BITMAP डेटा संरचना है जो इसके एपीआई के साथ उपयोग कर सकती है।

लेकिन मैं इस कुछ समय पहले के लिए कोड की जरूरत है, और इसलिए मैं इसे यहाँ लिखा था (चेतावनी, यह एक छोटे बदसूरत है):
https://gist.github.com/3206128

मैं केवल आंशिक रूप से यह परीक्षण किया है, तो यह अभी भी हो सकता है बग (विशेष रूप से reverse पर)। लेकिन एक हालिया संस्करण (केवल इस से थोड़ा अलग) मेरे लिए उपयोग करने योग्य लग रहा था, इसलिए यह एक कोशिश के लायक है।

पूरे बात के लिए मौलिक संचालन करने में सक्षम किया जा रहा है - जल्दी - बिट्स की एक रन की लंबाई ज्ञात:

long long GetRunLength(
    const void *const pBitmap, unsigned long long nBitmapBits, 
    long long startInclusive, long long endExclusive, 
    const bool reverse, /*out*/ bool *pBit); 

बाकी सब कुछ इस पर निर्माण करने के लिए आसान होना चाहिए, इसकी बहुमुखी प्रतिभा को देखते हुए।

मैंने कुछ एसएसई कोड शामिल करने का प्रयास किया, लेकिन यह प्रदर्शन में उल्लेखनीय रूप से सुधार नहीं हुआ। हालांकि, सामान्य रूप से, कोड बिट-बिट-बिट विश्लेषण करने से कई गुना तेज होता है, इसलिए मुझे लगता है कि यह उपयोगी हो सकता है।

यदि आप vector<bool> के बफर को किसी भी तरह पकड़ सकते हैं तो परीक्षण करना आसान होना चाहिए - और यदि आप विजुअल सी ++ पर हैं, तो एक ऐसा फ़ंक्शन है जिसमें मैंने शामिल किया है जो आपके लिए करता है। अगर आपको बग मिलती है, तो मुझे बताने में संकोच न करें।

Answer 2

मुझे नहीं पता कि स्मृति शब्द पर सीधे कैसे किया जाए, इसलिए मैंने एक त्वरित समाधान बनाया है जो बाइट्स पर काम कर रहा है; सुविधा के लिए, आइगोरिदम को संगत करने के लिए एल्गोरिदम स्केच करें:

आकार 256 के दो तालिकाओं का निर्माण करें जहां आप 0 और 255 के बीच प्रत्येक संख्या के लिए लिखेंगे, शुरुआत में और बाइट के अंत में पीछे की संख्या 1 की संख्या। उदाहरण के लिए, संख्या 167 (बाइनरी में 10100111) के लिए, पहली तालिका में 1 और दूसरी तालिका में 3 डालें। आइए पहली टेबल बीबीईजी और दूसरी टेबल बीन्ड को कॉल करें। फिर, प्रत्येक बाइट बी के लिए, दो मामले: यदि यह 255 है, तो अपने वर्तमान संगत सेट के वर्तमान योग में 8 जोड़ें, और आप किसी के क्षेत्र में हैं। अन्यथा, आप बीबीईजी [बी] बिट्स के साथ एक क्षेत्र समाप्त करते हैं और बीन्ड [बी] बिट्स के साथ एक नया शुरू करते हैं। आप जो जानकारी चाहते हैं उसके आधार पर, आप इस एल्गोरिदम को अनुकूलित कर सकते हैं (यह एक कारण है कि मैं यहां कोई कोड नहीं डालता, मुझे नहीं पता कि आप कौन सा आउटपुट चाहते हैं)।

एक दोष है कि यह शामिल नहीं किये जाते (छोटे) एक बाइट के अंदर लोगों से सटे सेट ...

इस एल्गोरिथ्म के अलावा, एक दोस्त मुझसे कहता है कि अगर यह डिस्क संपीड़न के लिए है, बस बाइट्स अलग देखने के लिए 0 (खाली डिस्क क्षेत्र) और 255 (पूर्ण डिस्क क्षेत्र) से। यह आपके लिए संकुचित करने वाले ब्लॉक के मानचित्र का निर्माण करने के लिए एक त्वरित ह्युरिस्टिक है। शायद यह इस विषय के दायरे से बाहर है ...

Answer 3

ऐसा लगता है कि यह उपयोगी हो सकता है:

http://www.aggregate.org/MAGIC/#Population%20Count%20%28Ones%20Count%29 और http://www.aggregate.org/MAGIC/#Leading%20Zero%20Count

आप कहते हैं कि नहीं करते हैं तो आप RLE किसी प्रकार का करना चाहता था या बस में बाइट्स शून्य गिनती करने के लिए और एक बिट (जैसे 0b1001 को 1x1 2x0 1x1 वापस करना चाहिए)।

तेजी से जांच के लिए एक लुकअप टेबल प्लस SWAR एल्गोरिदम आपको वह जानकारी आसानी से दे सकता है। इस तरह यह है कि:

byte lut[0x10000] = { /* see below */ }; 
for (uint * word = words; word < words + bitmapSize; word++) { 
    if (word == 0 || word == (uint)-1) // Fast bailout 
    { 
     // Do what you want if all 0 or all 1 
    } 
    byte hiVal = lut[*word >> 16], loVal = lut[*word & 0xFFFF]; 
    // Do what you want with hiVal and loVal 

lut के अपने इच्छित एल्गोरिथ्म के आधार पर निर्माण किया जा करना होगा। आप शब्द में सन्निहित 0 और 1 की संख्या की गणना करना चाहते हैं, तो आप इसे इस तरह बनाया जाएगा:

for (int i = 0; i < sizeof(lut); i++) 
    lut[i] = countContiguousZero(i); // Or countContiguousOne(i) 
    // The implementation of countContiguousZero can be slow, you don't care 
    // The result of the function should return the largest number of contiguous zero (0 to 15, using the 4 low bits of the byte, and might return the position of the run in the 4 high bits of the byte 
    // Since you've already dismissed word = 0, you don't need the 16 contiguous zero case.