c# - ブール配列内の false 要素のすべてのインデックスを取得する最速の方法は何ですか?

Question

次のブール配列があるとします。 {false, true, false, false, true, true, ...}

(たとえば) false 要素のインデックスを取得する最も簡単な (最も最適化された) 方法は何ですか? この場合は0 2 3？

Answer 1

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

これにより、余分なメモリ割り当てが回避されます。

Answer 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);

Answer 3

経験的な証拠が得られるまで、可能な解決策の中で何が最速かはわかりません。for次のコードは、LINQ とループ アプローチの計算速度比較のリファレンスとして使用できます。

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

Answer 4

私もいくつかのタイミングを計りましたが、人々が言っ​​ていることが正しいことを示しています。ポインターを使用しても、単純なループよりも大幅に高速ではありません。

結果リストにデータを入力するだけで、最大の時間が費やされているのではないかと思います。

次のテストプログラムから取得した時間は次のとおりです。

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