比較兩個二進制向量

Question

我有兩個bitarrays，每個長度爲200.000。我需要在相同的順序中找到每個列表中有多少個1。讓我畫出來：

1 0 
**1 1** 
0 0 
0 1 
0 0 
**1 1** 
1 0 
0 1 
.. .. 

所以結果應該是2

和我做的 - 兩個這種比較嵌套換約20萬次:)。

我現在用bitarray與&運算符比使用popCount方法找到結果。

那麼你對這類問題有什麼建議。你會在哪裏儲存這些載體，以及如何以我想要的方式比較它們？我需要速度。

更新： 我已經做了760長度的數組，這與我的方法花了5秒。在評論中提出的每種方法花費了> 1分鐘（我停止了該計劃） 因此，我猜它是我必須回答的。我簡化了我的代碼。

 for(i<761) 
    var vector1 = matris[getvectorthing]; 
      for(j=i+1<761) 
     { 
    var vector2 = matris[getvectorthing]; 
      var similarityResult = vector1Temp.And(vector2); 
      var similarityValuePay = popCount(similarityResult); 
    //similarityValuePay is result that i want 
     } 
    } 

     private static int popCount(BitArray simRes) 
      { 
       Int32[] ints = new Int32[(simRes.Count >> 5) + 1]; 
       simRes.CopyTo(ints, 0); 
       Int32 count = 0; 
       // fix for not truncated bits in last integer that may have been set to true with SetAll() 
       ints[ints.Length - 1] &= ~(-1 << (simRes.Count % 32)); 

       var tempInt = ints.Where(k => k != 0).ToArray(); 

       for (Int32 i = 0; i < tempInt.Length; i++) 
       { 
        Int32 c = tempInt[i]; 
        // magic (http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel) 
        unchecked 
        { 
         c = c - ((c >> 1) & 0x55555555); 
         c = (c & 0x33333333) + ((c >> 2) & 0x33333333); 
         c = ((c + (c >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; 
        } 
        count += c; 
       } 
       return count; 
      } 

我問了一下，因爲可能有很多切肉刀方法或簡單的調整來提高性能。例如：

var tempInt = ints.Where(k => k != 0).ToArray(); 

這個ToArray（）似乎是我需要修復的一部分。等

Answer 1

使用And方法和計數true，我覺得這是比其他答案更快。

var bit1 = new BitArray(new bool[]{true, false, ...}); 
var bit2 = new BitArray(new bool[]{false, false, ...}); 
var and = bit1.And(bit2); 

var result = 0; //Total count I think you want. 
for (int i = 0; i < and.Length; i++) 
{ 
    if (and[i]) 
    { 
     result++; 
    } 
} 

UPDATE

我想出了性能提升的解決方案。

更換popCount這樣：

private static int popCount(BitArray simRes) 
{ 
    Int32[] ints = new Int32[(simRes.Count >> 5) + 1]; 
    simRes.CopyTo(ints, 0); 
    Int32 count = 0; 
    // fix for not truncated bits in last integer that may have been set to true with SetAll() 
    ints[ints.Length - 1] &= ~(-1 << (simRes.Count % 32)); 

    for (Int32 i = 0; i < ints.Length; i++) 
    { 
     Int32 c = ints[i]; 
     if (c == 0) 
     { 
      continue; 
     } 
     // magic (http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel) 
     unchecked 
     { 
      c = c - ((c >> 1) & 0x55555555); 
      c = (c & 0x33333333) + ((c >> 2) & 0x33333333); 
      c = ((c + (c >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; 
     } 
     count += c; 
    } 
    return count; 
} 

在我的機器，當simRes.Length > 16000000，if(c == 0){...}塊提供了良好的性能。但是當simRes.Length < 16000000,if(c == 0){...}塊應該被刪除。

Answer 2

則可以通過使用該方法And()

BitArray ba = new BitArray(new bool[] { true, true, false, false, false, true, true, false }); 
BitArray ba2 = new BitArray(new bool[] { false, true, false, true, false, true, false, true }); 

int result = ba.And(ba2).Cast<bool>().Count(x => x); //2 

Answer 3

假設a和b具有相等Length解決這個問題。

int[] a = new[] {1,0,1, ...}; 
int[] b = new[] {0,0,1, ...}; 
int c = 0; 
for (int i = 0; i < a.Length; i++) 
    c += a[i] == 1 && b[i] == 1 ? 1 : 0; 

簡單。時間複雜度爲O（n）其中n是數組中的一些元素。

Answer 4

更簡潔的回答：

 bool[] A = ...; 
     bool[] B = ...; 


     var result = A.Where((val, ix)=>val && B[ix]).Count(); 

Answer 5

static void Main() 
{ 
     var a = new BitArray(new bool[]{true, false,true}); 
     var b = new BitArray(new bool[]{false, false,true}); 
     int result = 0; 
     int size = Math.Min(a.Length, b.Length); //or a.Length or 200000 
     for (int i = 0; i < size ; i++) 
     { 
      if (a[i] == true && b[i] == true) 
      { 
       result++; 
      } 
     } 
     Console.WriteLine("{0}",result); 
}