क्या कोई मुझे बता सकता है कि यह GetCardinality विधि क्या कर रही है?

Question

मैं लुसीन.NET के साथ पहचाने गए खोज में देख रहा हूं, मुझे एक शानदार उदाहरण here मिला है जो इस तथ्य के अलावा एक उचित राशि बताता है कि यह उस कार्य को पूरी तरह से अनदेखा करता है जो कुछ सरणी में वस्तुओं की कार्डिनालिटी की जांच करता है।

क्या कोई मुझे यह कर रहा है कि वह क्या कर रहा है? मुख्य चीजें जिन्हें मैं समझ नहीं पा रहा हूं, क्यों बिट्ससेटएरे को इसके रूप में बनाया गया है, इसका उपयोग किस प्रकार किया जाता है और कैसे सभी बयान लूप में काम करते हैं।

यह एक बड़ा सवाल हो सकता है लेकिन मुझे यह समझना होगा कि इससे पहले कि मैं इसे अपने कोड में उपयोग करने के बारे में सोच सकूं।

धन्यवाद

public static int GetCardinality(BitArray bitArray) 
    { 
     var _bitsSetArray256 = new byte[] {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8}; 
     var array = (uint[])bitArray.GetType().GetField("m_array", BindingFlags.NonPublic | BindingFlags.Instance).GetValue(bitArray); 
     int count = 0; 

     for (int index = 0; index < array.Length; index ++) 
      count += _bitsSetArray256[array[index] & 0xFF] + _bitsSetArray256[(array[index] >> 8) & 0xFF] + _bitsSetArray256[(array[index] >> 16) & 0xFF] + _bitsSetArray256[(array[index] >> 24) & 0xFF]; 

     return count; 
    } 

Answer 1

_bitsSetArray256 सरणी मूल्यों के साथ initialised ऐसी है कि _bitsSetArray256[n]n की बाइनरी प्रतिनिधित्व में सेट बिट्स की संख्या, 0..255 में n के लिए होता है।

उदाहरण के लिए, _bitsSetArray256[13] 3 बराबर होती है, क्योंकि बाइनरी में 13 1101 जो 3 1 रों होता है।

ऐसा करने का कारण यह है कि इन मूल्यों की पूर्व-गणना करने और उन्हें स्टोर करने के बजाए उन्हें हर समय (या मांग पर) काम करने के बजाय बहुत तेज़ है। यह 13 के द्विआधारी प्रतिनिधित्व में 1 रों की संख्या की तरह नहीं है कभी, बदलने के लिए सभी :)

के बाद for पाश के भीतर जा रहा है, हम uint रों की एक सरणी के माध्यम से पाशन कर रहे हैं। एक सी # uint एक 32-बिट मात्रा है, यानी 4 बाइट्स के लिए बनाया गया है। हमारी लुकअप टेबल हमें बताती है कि बाइट में कितने बिट सेट हैं, इसलिए हमें प्रत्येक चार बाइट्स को संसाधित करना होगा। count += लाइन में बिट मैनिपुलेशन चार बाइट्स में से प्रत्येक को निष्कर्ष निकालता है, फिर लुकअप सरणी से इसकी बिट गिनती हो जाती है। सभी चार बाइट्स के लिए थोड़ी सी गणना जोड़ना पूरी तरह से uint के लिए बिट गिनती देता है।

तो दिए गए एक BitArray, इस समारोह uint[] m_array सदस्य में खोदता है, तो uint रों उसमें की बाइनरी प्रतिनिधित्व में सेट बिट्स की कुल संख्या देता है।

Answer 2

मैं बस उन लोगों के लिए एक उपयोगी लेख पोस्ट करना चाहता हूं जो Lucene.net के साथ फ़ेसटिंग के अपने संस्करण विकसित कर रहे हैं। देखें: http://dotnetperls.com/precomputed-bitcount

यह एक पूर्णांक में बिट्स की कार्डिनालिटी प्राप्त करने के लिए फास्टेट तरीके पर एक अच्छी व्याख्या है (जो उपर्युक्त कोड नमूना का एक बड़ा हिस्सा है)।

मेरे पक्षपातपूर्ण खोज में आलेख में विधि को लागू करना और कुछ अन्य सरल परिवर्तन मैं उस समय को काटने में सक्षम था जब उसने ~ 65% की गणना की थी। मतभेद जहां में:

1. _bitcount वैश्विक (इसलिए इसकी प्रति कॉल नहीं बनाया)
2. बदलने की घोषणा के लिए foreach के लिए

3. 65535 तालिका Implementening (चींटी प्रोफाइलर एक 25% लाभ यहां से पता चला है) 256 बनाम एक बार में 16 बिट्स को बदलने के बजाय 8।

   private static int[] _bitcounts = InitializeBitcounts(); 
   
   private static int GetCardinality(BitArray bitArray) 
   { 
       uint[] array = (uint[])bitArray.GetType().GetField("m_array", BindingFlags.NonPublic | BindingFlags.Instance).GetValue(bitArray); 
   
       int count = 0; 
       foreach (uint value in array) 
       { 
        count += _bitcounts[value & 65535] + _bitcounts[(value >> 16) & 65535];   
       } 
       return count; 
   } 
   
   private static int[] InitializeBitcounts() 
   { 
       int[] bitcounts = new int[65536]; 
       int position1 = -1; 
       int position2 = -1; 
       // 
       // Loop through all the elements and assign them. 
       // 
       for (int i = 1; i < 65536; i++, position1++) 
       { 
        // 
        // Adjust the positions we read from. 
        // 
        if (position1 == position2) 
        { 
         position1 = 0; 
         position2 = i; 
        } 
        bitcounts[i] = bitcounts[position1] + 1; 
       } 
       return bitcounts; 
   }