3

我需要创建一个布尔值数组，其规模可能为 100,000 甚至数百万个条目。它还需要超快，因此每次迭代的每一毫秒都很重要。

在开始循环时，我已经知道数组中有多少条目。问题是，预先创建一个 bool 数组并按索引填充值会更快（这是随机访问 - 可能很慢？），还是我应该创建一个List<bool>，继续向列表中添加条目，然后在结束返回.ToArray()？

换句话说：

选项1

var array = new bool[size];
for (var n=0; n<size; n++)
  array[n] = GetValue(n);
return array;

选项 2

var list = new List<bool>();
for (var n=0; n<size; n++)
  list.Add(GetValue(n));
return list.ToArray();

或者也许有更快的第三种方式？

4

4 回答 4

5

使用 aSystem.Collections.BitArray并且不用担心速度。

你上面的建议只会浪费你的记忆。这对速度和大小都进行了优化，并且会bool很好地打包您的值（每个字节 8 个，正如神所希望的那样：）。

回复下面的评论：如果你使用 a BitArray，一开始一切都将是零。仅设置您拥有的那些位GetValue == true。

于 2012-07-23T08:39:29.650 回答
2

以下代码似乎（至少对我而言）显示了本页讨论的方法，bool[]使用循环的简单分配是最快的。

该代码似乎还告诉我，除非GetValue(n)在计算上微不足道，否则分配字节的开销不是我希望优化的过程的一部分。

希望这在某种程度上有所帮助。

编辑：添加运行结果（在我的机器上）

--  187ms    BitArray
--  171ms    List<bool>().ToArray 
--  168ms    bool[] set only if true
--  130ms    bool[] always set
--11460ms    bool[] always set with 'complex' GetValue()

class Program
{
    static void Main(string[] args)
    {
        BitArray bitArray = new BitArray(10000000);
        bool[] boolArray = new bool[10000000];

        Stopwatch sw1 = new Stopwatch();

        sw1.Start();

        for (int i = 0; i < 10000000; i++)
        {
            bitArray[i] = GetMod2(i);
        }

        Console.WriteLine(sw1.ElapsedMilliseconds);

        sw1.Restart();

        var list = new List<bool>();
        for (int i = 0; i < 10000000; i++)
            list.Add(GetMod2(i));
        var boolArray2 = list.ToArray();

        Console.WriteLine(sw1.ElapsedMilliseconds);

        sw1.Restart();

        for (int i = 0; i < 10000000; i++)
        {
            bool nextVal = GetMod2(i);

            if (nextVal)
                bitArray[i] = true;
        }

        Console.WriteLine(sw1.ElapsedMilliseconds);

        sw1.Restart();


        for (int i = 0; i < 10000000; i++)
        {
            boolArray[i] = GetMod2(i);
        }

        Console.WriteLine(sw1.ElapsedMilliseconds);

        sw1.Restart();

        for (int i = 0; i < 10000000; i++)
        {
            boolArray[i] = GetRand(i);
        }

        Console.WriteLine(sw1.ElapsedMilliseconds);

        Console.ReadLine();
    }

    static bool GetMod2(int i)
    {
        return (i % 2) == 1;
    }

    static bool GetRand(int i)
    {
        return new Random().Next(2) == 1;
    }
}
于 2012-07-23T09:18:37.153 回答
2

和第一个一起去。这可能是唯一的原因。“慢”是指它是否保留来自处理器缓存外部的分页数据。

该列表将具有完全相同的问题，除了它还需要执行多个内存分配和复制。

于 2012-07-23T08:43:02.570 回答
0

现在这是一个有趣的老东西。受@paul 的启发，我自己对 10,000,000 个布尔值进行了这些基准测试。鉴于对这个问题的评论中的讨论，结果（以毫秒为单位）非常令人惊讶：

位数组：517

BitArray + CopyTo（数组）：536

列表 + ToArray(): 455

布尔数组：483

这些书的投票率多么高！尽管List<Bool>每次都插入一条新记录，而bool[]and在每条记录上BitArray都初始化为false，并且我只在值应该是true的地方更新了它们，但List<bool>始终排在首位，甚至包括.ToArray()调用。

另一个实际应用比教科书知识更好的案例，似乎...... :)

于 2012-07-23T09:42:25.790 回答