比较两个二进制向量

Question

我有两个长度为 200.000 的位数组。我需要以相同的顺序在每个列表中找到多少个 1。让我画出来：

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

所以结果应该是2。

而且我在 - 两个嵌套中进行此比较 - 大约 2000 万次 :)。

我现在使用带有 & 运算符的位数组而不是使用 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()方法解决这个问题

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 2

假设 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 3

更简洁的回答：

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


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

Answer 4

使用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++;
    }
}

更新

我想出了一个提高性能的解决方案。

将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 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);
}

比较两个二进制向量

Compare two binary vector

c#

arrays

vector

bitarray