CODEWITHSUNDEEP
c#arraysperformance
TheSorrowRaven
TheSorrowRaven

Reputation: 33

C# Faster way to filter for loop with array of int as index?

Sorry if this is a duplicate, first question here...

I wanna operate on a large array of structs called notes. But I don't wanna operate on every element of notes. I'm trying to use a filter of an int array (int[]) as to skip quite a few of it as shown in below code.

Note[] notes = new Note[]
{ 
   // Struct stuff ... 
};

int[] filter = new int[]{ 4,20,50,367... };

for (int i = 0; i < notes.Length; i++)
{
     bool flag = false;
     for (int j = 0; j < filter.Length; j++)
     {
          if (i == filter[j])
          {
               flag = true;
               break;
          }
      }

      if (flag) continue;
      // Do something on notes[i]
}

The problem is, the code will run really slow (I think) when both notes array and filter array expands. So, is there a better and faster way to do this? Note that the size of filter can be anything based on other conditions

Upvotes: 3

Views: 989

Answers (3)

Raul
Raul

Reputation: 3131

You could filter the notes using Linq like this: 

Note[] notes = new Note[]{ ...//Struct stuff };
int[] filter = new int[]{ 4,20,50,367... };

var filteredNotes = notes.ToList().Where(note => !filter.Contains(note.Id)).ToList();

foreach(var note in filteredNotes)
{
//Do something on note
}

You would need to test the performance though, as Linq tends to be slow in specific circumstances.

Upvotes: 1

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186668

We can get rid of inner loop with a help of HashSet<int> while having a better O(|filter| + |notes|) time complexity instead of initial O(|filter| * |notes|):

Note[] notes = new Note[] { 
  ... //Struct stuff 
};

int[] filter = new int[] { 
  4, 20, 50, 367... 
};

HashSet<int> toExclude = new HashSet<int>(filter);

for (int i = 0; i < notes.Length; i++) {
  if (toExclude.Contains(i)) // O(1) time complexity 
    continue;

  //Do something on notes[i] 
}

Upvotes: 2

kkica
kkica

Reputation: 4104

You can loop the filter array and create a new boolean array that has all elements you want to skip as true.

bool[] filterArray= new bool[notes.Length];
foreach(var index in filter)
{
   if(index<filterArray.Length)
       filterArray[index]=true;
}

Then you have to just check the index of this array.

for (int i = 0; i < notes.Length; i++)
{
     if(!filterArray[i]){
     //Do something on notes[i]
     }

}

The complexity of this code will be O(m+n*X) where m is the length of the filter array, n the length of the node array and X the complexity of your operation on notes[i]. Assuming mO(n*X).

Your complexity now is O(m*n*X)

Upvotes: 0

Related Questions