5

我正在做一个项目，在某个时刻我需要展示一个月哪些日子仍然可用。有一个函数可以计算哪些天可用。我的同事说：“哦，我们知道，你应该返回一个BitVector32。这是处理布尔列表时最有效的方法。” 我会使用一个List<bool>或类似的东西。在我看来，当您实际使用位时， ABitVector32似乎是低级的东西。

所以，问题是。您是否应该BitVector32在需要一些少于 32 个项目的布尔值列表时使用它，还是应该只将它用于低级别的东西？

4

2 回答 2

5

使用列表很容易扩展到其他时间段。假设您想一次显示两个月。哦，这比 32 大。我需要更改返回类型以及使用它的任何地方。伟大的！BitVector32甚至没有IEnumerable<T>实现.

除非它处于紧密循环中，可读性和可维护性最高。并且列表分配的开销并没有那么大，除非您每秒执行一百万次。

所以我同意你的观点，你应该只将 BitVector32 用于低级代码。

于 2011-02-23T17:18:58.780 回答
3

BitVector32 是围绕 c# 的位操作的包装器（或者您可以将其称为抽象）。例如，以下两个语句返回相同的结果：

  • 1 << 1
  • BitVector32.CreateMask(1)

假设有一个包含一些重复数字的整数数组。我们要查找所有重复项。当然，您可以简单地使用 Linq 中的 GroupBy 函数，但假设我们没有 Linq。

  1. 第一个选项是蛮力方法，其中每个元素将与给定数组中的每个元素进行比较：

    foreach(int i in list) 
{
    foreach(int j in list)
    {
        if (i == j) 
        {
            // print this or store it in the result list
        }
    }
}

  2. 由于蛮力方法将导致 N 平方运行时间，这非常低效，我们可以考虑使用 HashSet 它将提供恒定的查找时间或 O(1)

    HashSet<int> hashSet = new HashSet<int>();

foreach(int i in list)
{    
    if (hashSet.Contains(i))
    {
        // print the duplicate or add it to the result list
    }
    else
    {
        hashSet.Add(i);
    }
}

这种方法将导致线性运行时间或 O(n)。但是，它需要 n * 4 字节的额外内存（假设我们谈论的是 32 位整数）

  1. 第三种方法类似于使用哈希集，只是它使用布尔数组需要更少的内存

    bool[] masks = new bool[list.Length];

for (int i = 0; i < list.length; i++) 
{
    if (masks[list[i]])
    {
        // print or add to the result list
    }
    else
    {
        masks[list[i]] = true;
    }
}

它使用布尔数组而不是 HashSet。它具有相同的运行时间，即 O(n)，但需要 1/4 的内存量，因为 bool 类型占用 1 个字节（8 位），而整数占用 4 个字节（32 位）

  1. 最后，我们可以使用 BitVector32 类或原生位移操作来解决这个问题。

    int check = 0;
for (int i=0; i < list.Length; i++)
{
    int mask = 1 << list[i];
    if (check & mask == mask) 
    {
        // print or add list[i] to the result list
    }
    else
    {
        check = check | mask;
    }
}

它还将导致总共只有 32 位内存的线性运行时间。所以内存使用量是 n/32。当然，如果数组中的最大值大于 32，这将不起作用。我们可以使用 64 位无符号整数来增加掩码中的槽数，但它仍然有一个非常短的限制。在这种情况下，如果您创建一个BitVectory32数组，并且您可以将该位移动到该数组的下一个索引中的BitVector32对象。例如，代码将如下所示

BitVector32[] bitVectorArray = new BitVector32[maxValue / 32];
bitVectorArray[list[i] / 32] = 1 << list[i] % 32;

这样，您不必受限于 32 位大小的限制。只要内存容量允许，您可以无限增加大掩码的大小。所以，把所有东西放在一起：

// This code assumes you know the range of the number in the array
BitVector32[] bitVectorArray = new BitVector32[maxValue / 32];

for (int i=0; i < list.Length; i++)
{
    int mask = 1 << list[i] % 32;

    if (bitVectorArray[(list[i] - 1)/32][i] & mask == mask) 
    {
        // print or add list[i] to the result list
    }
    else
    {
        bitVectorArray[(list[i] - 1)/32] = bitVectorArray[list[i] / 32] | mask;
    }
}
于 2012-07-08T21:58:05.080 回答