4

假设我有一个布尔数组： {false, true, false, false, true, true, ...}

获取（例如）错误元素的索引的最快方法（最优化）是什么？在这种情况下0 2 3？

4

7 回答 7

13

for 循环可能是最快的方法：

List<int> indices = new List<int>();
for (int i=0;i < theArray.Length; ++i)
{
   if (theArray[i])
   {
       indices.Add(i);
   }
}

请注意，通过预分配以下内容，您可能会以额外内存为代价获得一点速度List<int>：

List<int> indices = new List<int>(theArray.Length);

这将避免额外的内存分配。

于 2013-06-06T19:47:59.347 回答
5

对于多达 32 个元素：

int mask = 0;
for (int i = 0; i < arr.Length; i++)
{
    if (!arr[i]) mask += 1 << i;
}

掩码将是一个 32 位掩码，如果该位索引处的元素为假，则每个位为 1，如果该元素为真，则为 0。它是数组的另一种表示形式，如果您愿意的话，使用四个字节而不是每个布尔值一个字节。对于最多 64 个元素，您可以改用该long类型。但是，据我记得，int您可以将 anenum正确地转换为位掩码。

涉及的总字节数：四个用于掩码，一个用于数组的每个元素，四个用于循环中的索引。完成的总分配：两个（如果我们不计算数组的分配）。

于 2013-06-06T19:50:59.370 回答
2

这可能不是最快的方法，但它会产生一个仅包含真实索引的 IEnumerable。对我来说似乎有点乱。我想知道它是否可以简化？for 循环可能是最好的。但对于它的价值：

var bools = new bool[] {true, false, true, true, false, false, true, false, true};
var falseIndices = bools.Select((b, i) => new { Index = i, Value = b })
                        .Where(o => !o.Value)
                        .Select(o => o.Index);
于 2013-06-06T20:50:51.547 回答
1

在您获得经验证据之前，您永远不会知道最快的解决方案是什么。您可以使用下一个代码作为 LINQ 和for循环方法的计算速度比较的参考：

var r = new Random();
bool[] vals = new bool[100000000];

//initializing
for (int i = 0; i < vals.Length; i++)
{
    vals[i] = r.Next(2)==0;
}
var watch = Stopwatch.StartNew();

//for loop benchmark
List<int> indices = new List<int>(vals.Length);
for(int i = 0; i < vals.Length; ++i)
{
    if(!vals[i])
        indices.Add(i);
}
Console.WriteLine ("for loop: {0} ms", watch.ElapsedMilliseconds);

watch.Restart();

//LINQ benchmark
List<int> falseIndices = vals.Where(flag => !flag)
                             .Select((flag, index) => index)
                             .ToList();

Console.WriteLine ("LINQ: {0} ms", watch.ElapsedMilliseconds);

打印一些东西：

for loop: 600 ms
LINQ: 2072 ms
于 2013-06-06T19:58:28.313 回答
0

最快的方法可能包括使用fixed. 但是结果代码的可读性不是很好。

您应该确保“找到false元素的索引”确实是您的应用程序的瓶颈，并且找到“最快的方法”确实可以改善它。可读性和可维护性也是相当重要的方面。

正如其他人所建议的那样，一个简单的 for 循环具有良好的性能并且非常易读。Linq 解决方案不会慢很多。

如果数组包含很多true而不是很多，false你可以考虑使用Array.IndexOf()for eachfalse直到你发现不再出现。它可能比每个元素的方法更快。

于 2013-06-06T19:50:56.730 回答
0

尝试以下操作：

    BlockingCollection<int> indexes = new BlockingCollection<int>(x.Length);
    Parallel.For(0, x.Length, i =>
    {
        if (x[i])
        {
            indexes.Add(i);
        }
    });
于 2013-06-06T20:08:44.767 回答
0

我也做了一些计时，它表明人们所说的是正确的：使用指针并不比简单循环快得多。

我怀疑仅填充结果列表会占用最多的时间。

这是我从以下测试程序中得到的时间：

Unsafe took 00:00:06.6450271
Safe   took 00:00:06.7691818

测试代码如下...

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace Demo
{
    class Program
    {
        void Run()
        {
            int size = 10000000;
            bool[] array = new bool[size];

            for (int i = 0; i < size - 1; ++i)
                array[i] = true;

            int count = 100;

            time(() => UnsafeCountSetFlags(array), "Unsafe", count);
            time(() => SafeCountSetFlags(array),   "Safe",   count);
        }

        void time(Action action, string title, int count)
        {
            var sw = Stopwatch.StartNew();

            for (int i = 0; i < count; ++i)
                action();

            Console.WriteLine(title + " took " + sw.Elapsed);
        }

        List<int> UnsafeCountSetFlags(bool[] array)
        {
            unsafe
            {
                fixed (bool* parray = array)
                {
                    List<int> result = new List<int>();

                    for (bool* p = parray, end = parray + array.Length; p != end; ++p)
                        if (*p)
                            result.Add((int)(p-parray));

                    return result;
                }
            }
        }

        List<int> SafeCountSetFlags(bool[] array)
        {
            List<int> result = new List<int>();

            for (int i = 0; i < array.Length; ++i)
                if (array[i])
                    result.Add(i);

            return result;
        }

        static void Main()
        {
            new Program().Run();
        }
    }
}
于 2013-06-06T20:19:05.163 回答