3

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

Improve this question
2
  • Typo? Do you mean if (notes[i] == filter[j]) instead of if (i == filter[j])? Commented Apr 24, 2019 at 7:45
  • @DmitryBychenko no not typo, I'm using the index to filter notes[i], but if it's if (notes[i] == filter[j]) shouldn't it cause an error since (struct == int)?? Commented Apr 24, 2019 at 7:53

3 Answers 3

Reset to default
2

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] 
}
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Do you really claim HashSet.Contains() has a complexity of O(1)? It will only perform better on larger sets, it will still trend somewhere towards log n
@Raul Sebastian: it depends on GetHashCode implementation; Microsoft one is good enough if items are random in filter. Sure an adversary can such items such that we have a lot of hash collistions and inefficient toExclude.Contains
@Dmitry Bychenko Thanks for making me look it up. It really seems that HashSet lookups complexity stays constant, while in worst case it would be linear.
1

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.

Improve this answer

4 Comments

Ermm, actually, this is exactly the opposite I want to do since my filter means "skip this"
Sorry, but it seams that we should iterate all indexes, but filter (i.e. 0, 1, 2, 3, 5,...19, 21, ...). Please, note if (flag) continue; in the code provided
@TheSorrowRaven sorry, I misunderstood you then. Let me edit it
Final materialization .ToList() is redundant: foreach will do with IEnumerable<Node>
0

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)

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.