CODEWITHSUNDEEP
c#arraysloops
drai29
drai29

Reputation: 161

Given an bool array, how to make these loops more performant?

If you have: 

bool[] arrayExample = {false, true, false, false, true, true, false, false, true, true, true};

Given an n value, I am looping through the array to find which index has a True value.

For example: if n = 1: I want to return all index's that have 1 True value. Therefore the return list would be {1, 4, 5, 8, 9, 10}

if n = 2: I want to return list to have the index's where there is 2 True values in a row: {4, 8, 9}

Also, I would like to do this for n=3?

Is there a cleaner/more performant way to run this code? 

List<int> indices = new List<int>();
bool counter = false;

if (n == 1)
{
    for (int i = 0; i < arrayExample.Length; ++i)
    {
        if (arrayExample[i])
        {
            indices.Add(i);
        }
    }
}
else if (n == 2)
{
    for (int i = 0; i < arrayExample.Length; ++i)
    {
        if (counter == true && arrayExample[i] == false)
        {
            counter = false;
        }
        if (arrayExample [i])
        {
            if (counter == false)
            {
                counter = true;
            }
            else
            {
                indices.Add(i);
                counter = false;
            }
         }
     }
}

Upvotes: 0

Views: 136

Answers (5)

Olivier Jacot-Descombes
Olivier Jacot-Descombes

Reputation: 112602

The speed of your code is probably okay; however, you can simplify the algorithm

const bool F = false, T = true;
bool[] arrayExample = { F, T, F, F, T, T, F, F, T, T, T };

var indices = new List<int>();
int count = 0;
int n = 2;
int delta = n - 1;

for (int i = 0; i < arrayExample.Length; i++) {
    if (arrayExample[i]) {
        count++;
        if (count >= n)
            indices.Add(i - delta);
    } else
        count = 0;
}

This works for any n. Count how many succeeding true values you encountered and add an index whenever this count is a least equal to the required sequence length. Since you want the index of the first index in your sequence, you must subtract n - 1.

This algorithm directly yields the indices in ascending order, does not need a temporary array and has no nested loops. I.e., it has a time performance of O(n) (here n stands for the length of the input).

Upvotes: 2

DeuxAlpha
DeuxAlpha

Reputation: 395

Just figured I'd throw my code in the mix (never quick enough to actually provide any useful insights, anyhow):

public static IEnumerable<int> TrueIndicesCounter(int counter, List<bool> booleans)
{
    if (counter <= 0) return new List<int>();
    var truths = new List<int>();
    for (var booleanIndex = 0; booleanIndex < booleans.Count; booleanIndex++)
    {
        var boolean = booleans[booleanIndex];
        if (boolean != true) continue;
        if (counter == 1)
        {
            truths.Add(booleanIndex);
            continue;
        }
        var counterIndex = 1;
        var counterSatisfied = false;
        while (counterIndex <= counter)
        {
            var targetBoolean = booleans.ElementAtOrDefault(booleanIndex + counterIndex);
            if (targetBoolean != true) break;
            counterIndex++;
            if (counterIndex != counter) continue;
            counterSatisfied = true;
            break;
        }
        if (counterSatisfied)
            truths.Add(booleanIndex);
    }
    return truths;
}

Upvotes: 0

AbdelAziz AbdelLatef
AbdelAziz AbdelLatef

Reputation: 3744

You can try the idea given by @Dennis_E like this:

int i, j;
int[] rep = new int[arrayExample.Length];
if (rep[arrayExample.Length - 1])
    rep[arrayExample.Length - 1] = 1;
for (i = arrayExample.Length - 2; i >= 0; i--)
    if (arrayExample[i])
        rep[i] = rep[i + 1] + 1;
for (i = 0 ; i < arrayExample.Length; i++)
    if (count == n)
        indices.Add(i);

Upvotes: 0

Nehorai Elbaz
Nehorai Elbaz

Reputation: 2452

How about:

static void Main(string[] args)
{
   bool[] arrayExample = { false, true, false, false, true, true, false, false, true, true, true };
   List<int> result = Foo(1, arrayExample);
   foreach(var num in result)
      Console.WriteLine(num);
   Console.ReadKey();
}
static List<int> Foo(int num,bool[] arr)
{
    List<int> indices = new List<int>();
    int count = 0;
    for (int i = 0; i < arr.Length; i++)
    {
       if(arr[i])
       {
           for (int j = 0; j < num; j++)
           {
               if(!arr[i+j])
               {
                     count = 0;
                     break;
               }
                  count++;
           }
                    if (count > 0)
                        indices.Add(i);
       }
   }
  return indices;
}

Upvotes: 0

Dennis_E
Dennis_E

Reputation: 8894

Here's an idea:
Take your example array: [F,T,F,F,T,T,F,F,T,T,T]
Go from end to start, and mark how many True values you have encountered at each position: [0,1,0,0,2,1,0,0,3,2,1].
Now you can get the answer for any n: return every index where array[index] >= n

Upvotes: 4

Related Questions